/prog/ -Line - Line Intersection Algorithms

Name
Email
Subject	REC STOP
Comment *
File	Select/drop/paste files here
Password	(Randomized for file and post deletion; you may also set your own.)
Archive	Archive [500 char limit]
* = required field	[▶Show post options & limits] Confused? See the FAQ.

Options	Do not bump (you can also write sage in the email field)
Allowed file types:jpg, jpeg, gif, png, webp,webm, mp4, mov Max filesize is16 MB. Max image dimensions are15000 x15000. You may upload5 per post.

Line - Line Intersection Algorithms Anonymous 08/21/15 (Fri) 05:04:37 f16dfd 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

____________________________

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

Anonymous 08/21/15 (Fri) 09:31:48 f16dfd 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.

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

Anonymous 08/21/15 (Fri) 09:37:17 f16dfd 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.

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

Anonymous 08/21/15 (Fri) 18:48:33 f16dfd 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.

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

Anonymous 11/29/15 (Sun) 02:21:22 f16dfd 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.

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

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

>>3095

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

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

Anonymous 12/08/15 (Tue) 00:39:23 f16dfd No.3685

Think of it like back in highschool algebra.

y=mx+b

if line 1 line 2

collision == true

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

Anonymous 12/09/15 (Wed) 23:52:34 f16dfd No.3688

>>3685

what about vertical lines?

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.