25

I need a fast algorithm for checking if two non-infinite lines are crossing. Have to be fast because it'll run on a cell phone a lot.

The algorithm do only have to return yes or no, it does not have to find out exactly where the lines cross!

I have looked here: How do you detect where two line segments intersect? But that thread is a jungle, people keep saying that "this is the answer" but then two other guys say that it is incorrect because of this-and-that bug.

Please help me find a good and working algorithm for this.

Just to be clear: I need a function that you give...
lineApointAx
lineApointAy
lineApointBx
lineApointBy
lineBpointAx
lineBpointAy
lineBpointBx
lineBpointBy
...and that returns true or false depending on if the two lines cross or not.

I would appreciate if you answered with (pseudo-)code, not formulas.

Community
  • 1
  • 1
Mike
  • 301
  • 1
  • 4
  • 5
  • 1
    possible duplicate of [Determining if two line segments intersect?](http://stackoverflow.com/questions/4977491/determining-if-two-line-segments-intersect) – Ray Hayes Aug 15 '11 at 19:19
  • Conceptually duplicate: http://stackoverflow.com/questions/3461453/determine-which-side-of-a-line-a-point-lies – zw324 Aug 15 '11 at 19:31
  • Premature Optimization at its finest! –  Aug 15 '11 at 20:27
  • 5
    "Premature Optimization at its finest!". Oh yeah? On average 30 intersection checks will have to be done each frame at 60 fps, while rendering and tons of other calculations also should have room to be executed in those ~16 ms between each frame. Taken into account that I also want to support budget mobile phones that are at most two years old I'd say that wanting to optimize my code everywhere I can is something that is understandable. Especially since even more calculations will be added in the future. But maybe you're right, but hey fast code is never wrong. – Mike Aug 15 '11 at 20:41
  • Stack Overflow is not intended to be a place to come along and ask the community to supply complete solutions. – Kev Aug 15 '11 at 21:01
  • 2
    This is not premature optimization, it is algorithmic optimization. Optimization is only premature if a compiler could be reasonably expected to perform the optimization, regardless of whether it actually will. A compiler might be able to intelligently change a division by two into a bitwise operation (whereas doing that by hand is a premature optimization), but a compiler will never be able to convert, say, an Insertion Sort algorithm into a Quick Sort algorithm. At least, not as long as compilers just compile our instructions and don't actually collaborate on the programming. – meustrus Dec 15 '14 at 19:38
  • 2
    @RayHayes I don't understand why this was closed. Most simple computer geometry questions like this have a single accepted "best way" or "least expensive" algorithm. I came here because I'm in a hurry and wanted to grab the algorithm rather than sit down and think through a bunch of formulas. It would be very helpful to have the answer he was looking for here (similar to http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect, but simplified) marked as accepted, and modded up. – M Conrad Jun 15 '16 at 00:05
  • and in fact I just sat down and banged it out, and would like to post it here, but can't. https://gist.github.com/nrdvana/fe002742e45ed4ff58031eb32f99c6f8 – M Conrad Jun 15 '16 at 01:12

2 Answers2

49

It is necessary and sufficient that the two ends of one segment are on different sides of the other segment, and vise-versa. To determine which side a point is on, just take a cross-product and see whether it's positive or negative:

(Bx - Ax)(Py - By) - (By - Ay)(Px - Bx)

EDIT:
To spell it out: suppose you're looking at two line segments, [AB] and [CD]. The segments intersect if and only if ((A and B are of different sides of [CD]) and (C and D are on different sides of [AB])).

To see whether two points, P and Q, are on different sides of a line segment [EF], compute two cross products, one for P and one for Q:

(Fx - Ex)(Py - Fy) - (Fy - Ey)(Px - Fx)

(Fx - Ex)(Qy - Fy) - (Fy - Ey)(Qx - Fx)

If the results have the same sign (both positive or both negative) then forget it, the points are on the same side, the segments do not intersect. If one is positive and the other negative, then the points are on opposite sides.

Beta
  • 96,650
  • 16
  • 149
  • 150
  • Are you sure that this works? Take, for example, one line segment to be the line from (0, 0) to (0, 1) and the other segment from (-1, 2) to (+1, 2). Then the point (-1, 2) is on one side of the line segment from (0, 0) to (0, 1), while the point (+1, 2) is on the other side, but the two segments don't overlap. – templatetypedef Aug 15 '11 at 19:33
  • @templatetypedef: note that I said "and vise-versa". (0,0) and (0,1) are both on the same side of the second segment. – Beta Aug 15 '11 at 19:40
  • @Beta- Ah, my apologies, I didn't see that. Although I believe you, do you have a proof of this? (By the way, I'm not the downvoter) – templatetypedef Aug 15 '11 at 19:45
  • To check if two point are on opposite sides, the scalar product of the two cross products will be negative. So you'll end up with 4 cross products (C1-C4) so then you can write: if ( (C1*C2)<0 and (C3*C4)<0 ) they intersect, else they don't. – phkahler Aug 15 '11 at 19:56
  • @templatetypedef: A proof? How about this: if *those* points are on different sides of *this* line, then the intersection is in *that* segment; repeat the other way. (And I don't sweat a downvote in a case like this-- I figure somebody just made a mistake.) – Beta Aug 15 '11 at 19:57
  • @phkahler: true, but if you're *really* looking for speed, (c1<0)xor(c2<0) might be faster than multiplication. – Beta Aug 15 '11 at 20:01
  • I'm having some trouble implementing this because, well, it's math. Could you perhaps post the algoritm in its full, preferably as a ready function? Am I correct in understanding that I have to calculate "(Bx - Ax)(Py - By) - (By - Ay)(Px - Bx)" four times and two times it should be positive and two times negative? I'm having some trouble puzzling together your clue towards the solution that I seek. – Mike Aug 15 '11 at 20:53
  • I've taken the liberty of adding a description of what we're taking the cross product of and why it works. – SigmaX Nov 15 '13 at 15:39
  • @Beta cross products are between vectors and result in a vector. confused because: a) you seem to be suggesting to take a cross product between a line segment (no direction; therefore, not a vector) and a point (definitely not a vector). b) the result is a scalar. Please help me understand if my 26-yr memory is off or is this just loosie-goosie terminology. I would love to use this but my confidence level could use a boost. – juanchito Mar 09 '14 at 01:55
  • @mayonesa: To be precise, I am suggesting taking a cross product between two vectors, **(B-A)** and **(P-B)**, and considering only the z-component of the result. (The x and y components will be zero.) – Beta Mar 09 '14 at 02:40
  • this algorithm does not work for [codeeval's bay bridges](https://www.codeeval.com/open_challenges/109/). I am willing to bet that it's too flimsy to handle some of the more extraneous intersect cases or perhaps it's just not mathematically sound (it certainly does not sound like it is). By just changing the intersect algorithm to a different one, I go from fail to 100%. – juanchito Mar 10 '14 at 00:27
  • @mayonesa: You are mistaken. – Beta Mar 10 '14 at 01:18
  • if you have time, try the codeeval challenge and let me know how it works for you. maybe I just transcribed it wrongly into my program (it does have a lot of terms). However, I double and triple-checked it. – juanchito Mar 10 '14 at 01:49
  • @mayonesa: There are 6 line segments in that challenge; 15 pairs of lines, 120 choices of three points to test. Do you think that my formula misjudges left/right for some set of 3 points -- and if so, which 3? -- or that that formula works but the algorithm incorrectly judges whether a certain pair of lines crosses -- and if so, which pair? Since you say that my algorithm "certainly does not sound" mathematically sound, I will venture to say that the fault is in your code. – Beta Mar 10 '14 at 03:15
  • I used your logic and it worked for the sample data offered in the write-up. However, when I submitted that sol'n it failed against the hidden, actual data. Here it is `boolean intersects(final Bridge b2) { float b1x = westShoreEnd.x - eastShoreEnd.x; float b1y = westShoreEnd.y - eastShoreEnd.y; float b1_X_b2WestShoreEnd = b1x * (b2.westShoreEnd.y - westShoreEnd.y) - b1y * (b2.westShoreEnd.x - westShoreEnd.x); float b1_X_b2EastShoreEnd = b1x * (b2.eastShoreEnd.y - westShoreEnd.y) - b1y * (b2.eastShoreEnd.x - westShoreEnd.x); return (b1_X_b2WestShoreEnd > 0) ^ (b1_X_b2EastShoreEnd > 0); }` – juanchito Mar 11 '14 at 00:36
  • @mayonesa: If you can't provide a failure case ("an online judge rejected my implementation" does *not* qualify), then you shouldn't claim that the algorithm is flawed. The algorithm is correct; I don't know why the judge rejected your code. – Beta Mar 11 '14 at 03:43
  • Per your request, [37.713875, -122.383267], [37.432856, -122.174125] and [37.545285, -122.206471], [37.552586, -122.236614] when plugged in to the OP "cross-products" result in 0.003791 and -0.003152 which incorrectly identifies them as intersecting. – juanchito Mar 11 '14 at 21:03
  • @mayonesa: What about the other cross-products, the "vise-versa" part? My algorithm says that these two line segments do *not* intersect, since the other two cross-products are -0.0144238 and -0.00747998. Do you mean that you apply your `intersects(...)` only once? That explains the mystery. You tried to implement the algorithm without understanding it (which is almost impossible), missed a vital part (despite double- and triple-checking) and submitted a solution with a bug (in the part of the code you *didn't* show here) to the online judge. – Beta Mar 11 '14 at 22:38
  • Show your calculations because `(Fx - Ex)(Py - Fy) - (Fy - Ey)(Px - Fx), (Fx - Ex)(Qy - Fy) - (Fy - Ey)(Qx - Fx)` doesn't lend itself to 1 result but 2. You're claiming a vice-versa on 2 results which would make it altogether 4 but you're only showing 2. If you can come up w/ a more congruent answer, you may be able to make an argument to what seems a pretty contrived sol'n. – juanchito Mar 11 '14 at 23:30
  • After reading many answers on SO, I see that between a mathematical explanation and a working line intersection code, there is a huge difference. Nearly none of the provide implementations here work. This is really a shame. The mathematical explanation alone does not help, there are so many corner cases, which are visible when looking at working code (E.g from the book Computational Geometry in C) – AlexWien Nov 25 '14 at 19:33
  • 2
    @AlexWien: Yes, writing code can be hard work. – Beta Nov 25 '14 at 23:35
  • 1
    Hmm... so... I'm just confused with something minor... I see you are taking the cross product `(B - A) x (P - B)`. I don't understand the reason - shouldn't you fix "A" as the origin, and then take the cross product `(B - A) x (P - A)`? Will the algorithm still work if I do this way? Notice Murphy Law in full action making both my formulas break through 2 lines. Damn. – MaiaVictor Dec 05 '14 at 00:06
  • 7
    Note: for future readers, if this is true, you can use my inlined JavaScript implementation here: http://jsfiddle.net/ytr9314a/4/ – MaiaVictor Dec 05 '14 at 00:48
  • 2
    @Viclib: The algorithm will still work if you do it that way. The choice of A or B (or any point between) is arbitrary. – Beta Dec 05 '14 at 05:46
  • @Beta, does this method take into account colinearity? – MarcoM Jun 07 '22 at 15:09
  • @MarcoM: Sorry, but I'm no longer answering questions on this comment thread that *anyone could answer by taking the time to understand the short and simple solution I posted.* – Beta Jun 08 '22 at 05:16
  • @Beta: got it. Anyhow the cross product can be positive, negative OR be zero. I'll take my time to dig deeper. – MarcoM Jun 08 '22 at 05:56
9

If you're two given points are (X1,Y1) and (X2,Y2), imagine both are infinite lines, not just segments:

  1. Determine the formula for both (see: http://en.wikipedia.org/wiki/Linear_equation#Two-point_form)

  2. Determine the intersection point for the two lines (see: http://zonalandeducation.com/mmts/intersections/intersectionOfTwoLines1/intersectionOfTwoLines1.html)

  3. If X1 < intersectionX < X2 and Y1 < intersectionY < Y2, then yes, the segments intersect.

Jonathan M
  • 17,145
  • 9
  • 58
  • 91
  • I think the point is that he wants a faster way to do this, which to me means a way that doesn't involve finding the intersection point. The only problem with that is, well, that finding the intersection point and checking it - like you suggest - is actually pretty quick. – Patrick87 Aug 15 '11 at 19:29
  • 1
    Yeah, I'm not sure what faster means. Faster than what? He just said "fast". – Jonathan M Aug 15 '11 at 19:32
  • Still, this is useful for those of us coming later who want to know *where* the segments cross. – Mar Mar 26 '12 at 21:13
  • For those coming even later: this is not a stable algorithm, you will have to have special handling for pairs of lines close to coincide with each other as well as for lines coming cloes to being parallel with the coordinate axes. – Franz Jul 19 '18 at 08:22
  • @Franz, can you give an example? – Jonathan M Jul 20 '18 at 18:40