Wikipedia:Reference desk/Archives/Mathematics/2009 December 25

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 25

Easy way of deciding if two lines cross?

I am writing a computer program where many lines are stored as a pair of x.y coordinates. I would like to be able to decide if two lines cross. What would be the easiest way to program this please? I can think of changing the lines into y=mx+c format, doing a simultaneous equation (I think) to find the point of intersection, and then checking that this intersection point is within each line segment. But is there any easier way please? (I am not fluent with matrices and the language I am using has no matrix commands). Maybe something regarding the angles between the four points - I'm guessing. A simple way to find the x.y coordinate of the point of intersection would also be useful. Thanks 92.24.44.4 (talk) 14:52, 25 December 2009 (UTC)

Just determine whether or not they are parallel. If they're parallel, then either they never intersect or they're the same line. If they're not parallel, then they must intersect at exactly one point. No need to determine the point of intersection. I'll leave it as an exercise to you to figure out how to determine if they're parallel, and to explain why this technique doesn't work in 3 dimensions. --COVIZAPIBETEFOKY (talk) 16:58, 25 December 2009 (UTC)

Sorry, I should have made clearer than the lines are not infinate. They can be non-parallel and still not cross. 78.146.194.118 (talk) 17:07, 25 December 2009 (UTC)

Your method sounds best to me. You should first check they aren't the same line (if they are you just need to check the order of the endpoints to see if they overlap) then that they aren't parallel (if they are and they aren't the same line, they won't intersect) and then you can find the point of intersection and see if it is in both lines. To get the intersection point from two equations, y=mx+c and y=nx+d, you can just do x=(d-c)/(m-n) (to derive that just put mx+c=nx+d and rearrange) and then plug that into y=mx+c to get y. --Tango (talk) 17:37, 25 December 2009 (UTC)

I'm wondering if the four end points of the two lines would always make a polygon with a concave part in it if they do not cross? 78.146.194.118 (talk) 17:49, 25 December 2009 (UTC)

One way you could do it is that if the segment from A to B and from C to D don't cross then either (B-A)×(C-A) and (B-A)×(D-A) will have the same sign or (D-C)×(A-C) and (D-C)×(B-C) will have the same sign. Here × is the cross product, A×B = x_Ay_B - x_By_A. There might be some more efficient way to get to that though.

For the intersection point, I think it should be A + (((C-A)×(D-C))/((B-A)×(D-C)))(B-A) if I didn't screw anything up. You could also use that intersection point to decide if the segments cross, although I think this way is more computationally intensive unless you need the intersection point anyway. Rckrone (talk) 21:23, 25 December 2009 (UTC)

(Answering 78.*)... No, they do not make a concave polygon. This is a common homework or quiz question in algorithms programming. Nothing in the question assume that the direction of the lines is from the Y axis towards infinity. One may be right-to-left. The other may be left-to-right. This creeps in again in processor/ALU design. Division is a very nasty time consumer. Comparison is not. So, using less-than/greater than, you can sort the points to form a concave polygon. Then, if you go around the four points in a clockwise manner, you can detect that each turn is a right turn by only using subtraction (which is actually a very cheap addition process inside the computer). -- kainaw™ 21:47, 25 December 2009 (UTC)

I forgot to mention that some student always comes up with the idea of just comparing the endpoints. It is a bit trivial to come up with an example that nullifies anything that depends solely on comparing endpoints. -- kainaw™ 21:50, 25 December 2009 (UTC)

See also Wikipedia:Reference desk/Archives/Mathematics/2009 October 4#Best way to calculate if a line crosses another line, or a polygon.. Is there an article to point to on this?--RDBury (talk) 21:59, 25 December 2009 (UTC)

To the OP: please do look at the link that RDBury gives, and the explanation that RDBury and BenRG give there. Intuitively, if we wish to check whether AB and CD cross, we check whether A and B are on opposite sides of the line CD, and whether C and D are on opposite sides of AB. To check which side of a line that a point is on, we compute the appropriate cross product (or equivalently, the signed area of the triangle the three points form). BenRG provides code in C++; while I haven't checked it myself, it looks correct.

Don't use methods that involve computing intersection points, because these are generally more difficult to code correctly (with special cases like infinite slope, etc.), not numerically stable, and slower (although speed is unlikely to be a concern either way). Although there is nothing mathematically wrong with this approach (and this is a mathematics reference desk, after all), from a programming perspective it is not preferred. Eric. 131.215.159.171 (talk) 23:54, 25 December 2009 (UTC)

The formula: (x₂-x₁)(y₃-y₁)-(y₂-y₁)(x₃-x₁) :is commonly referred to as "turn" in computer programming - mainly in graphics. Going from point 1, to point 2, to point 3, if the value is positive, you made a left turn. If it is negative, you made a right turn. If it is zero, the three points are on a line (note: it could be a 180 degree turn). Calculating turn comes in handy in a lot of graphics programming. -- kainaw™ 02:25, 26 December 2009 (UTC)

I didn't know that... in the context of computational geometry I've only heard it referred to as the "signed area". Eric. 131.215.159.171 (talk) 08:25, 26 December 2009 (UTC)

To answer the OP and my own question, we have an article, Line segment intersection in this topic but it's in dire need of expansion. I get the impression that mathematicians look at the problem and see the main issue as determining whether two line segments intersect; multiple line segments are just a matter of applying the solution multiple times. While to people in computer science, the problem of whether two line segments intersect is simple algebra and the real issue is to organize the problem so you don't have to test all possible pairs of segments. It seems to me that the article should cover both points of view and right now it just gives an outline of the second. I found lectures notes [1]] which give a pretty good introduction to the subject except they are not self-contained. (For example pseudocode calls a function CCW whose implementation is not given.)--RDBury (talk) 12:16, 26 December 2009 (UTC)

Thanks, as the OP is there any consensus on what the easiest way to check if two lines cross or not, given that I am only fluent in an old version of BASIC and that my maths education stopped when I was 16 years old? 89.240.110.255 (talk) 16:28, 26 December 2009 (UTC)