/prog/ - Line - Line Intersection Algorithms

Name
Email
Subject
Comment *
File	Select/drop/paste files here
* = required field	[▶ Show post options & limits] Confused? See the FAQ.

Embed	(replaces files and can be used instead)
Options	Do not bump (you can also write sage in the email field) Spoiler images (this replaces the thumbnails of your images with question marks)
Password	(For file and post deletion.)
Allowed file types:jpg, jpeg, gif, png, webm, mp4, pdf Max filesize is 8 MB. Max image dimensions are 10000 x 10000. You may upload 1 per post.

Line - Line Intersection Algorithms Anonymous 08/21/15 (Fri) 05:04:37 380530 No.3095

So needed an algorithm to detect if 2 lines intersect

SAT doesnt work to well for lines, so i decided to see if i could figure out something myself

Remembered from Geometry class that if a quadrilateral is convex, then its diagonals must intersect, and if its concave, then they dont

So i thought: "if quad(line1point1,line2point1,line1point2,line2point2) is convex, then the lines intersect, otherwise no"

But then i thought: "but wouldnt the 'convex-test' algorithm itself need to test if the diagonals intersect?

Aka:

Line intersection algorithm needs a function to determine whether a quad is concave or not

Concave-test algorithm needs a line intersection algorithm to determine if the quads diagonals intersect

Its a paradox

CPU murdering recursion

Help me

Anonymous 08/21/15 (Fri) 09:31:48 04d4ae No.3098

>>3095

You need to project your lines to the X and Y axis and then check if both projections are intersecting.

That's the most simple method that I know of.

Anonymous 08/21/15 (Fri) 09:37:17 04d4ae No.3099

>>3098

It just came to me that that method *is* the SAT.

>>3095

Why do you think it's not working for lines?

Besides there's one more idea. You can check if the lines intersect analytically i.e. build a standard equations of form y=kx+b for both lines and then check if they have equal results for some x. This can in fact be done without iteration methinks.

Anonymous 08/21/15 (Fri) 18:48:33 4da99e No.3101

3d space or 2d space? Do you actually mean lines or line segments?

If 2d space, just check the slope. They intersect if they aren't parallel.

In 3d space, calculate their closest points. They intersect if their closest point is equal.

Anonymous 11/29/15 (Sun) 02:21:22 7141f1 No.3660

>>3095

something something vectors.

https://www.cs.utah.edu/~jsnider/SeniorProj/BSP1/default.html

has some code that might help you, such as methods that determine wether a point is in front of or behind a plane.

Anonymous 12/03/15 (Thu) 03:24:34 1e9695 No.3671

>>3095

https://web.stanford.edu/~liszt90/acm/notebook.html#file8