1

Lets consider the following problem:

We have a 4 Points {a,b,c,d} and want to check if the ways [a;b] and [c;d] would cross each other if we connect the points by lines on a paper.

The point is defined as (x|y) so it can be drawn into a 2-dimensional coordinate system.

How can I check this in O(1)?

Mr. Perfectionist
  • 2,605
  • 2
  • 24
  • 35
Coder55
  • 559
  • 5
  • 17
  • 1
    the c++ is irrelevant. this is basic geometry: http://www.wikihow.com/Algebraically-Find-the-Intersection-of-Two-Lines – Marc B Jul 10 '15 at 17:00
  • @Marc B, the question was about two line **segments** not two lines. So getting the answer from the link you posted would be beyond the math skills of many programmers. The answer is much more obvious in this link https://en.wikipedia.org/wiki/Intersection_%28Euclidean_geometry%29#Two_line_segments – JSF Jul 10 '15 at 17:07

1 Answers1

2

There is effective method to check whether two line segment intersect: AB and CD intersect, if C and D points lie in different semi-planes relative to AB line, and C and D lie in different semi-planes relative to CD line. Here is concise Python implementation:

def ccw(A,B,C):
    return (C.y-A.y)*(B.x-A.x) > (B.y-A.y)*(C.x-A.x)

def intersect(A,B,C,D):
        return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

Thorough treatment of special cases (collinearity, coincidence) is described here

MBo
  • 77,366
  • 5
  • 53
  • 86
  • This is quite another question. Gavin's answer here: http://stackoverflow.com/a/1968345/844416 gives good practical implementaion of intersection point calculation – MBo Jul 13 '15 at 08:45