graph - How to check if the connections between points are crossing each other? -

lets consider following problem:

we have 4 points {a,b,c,d} , want check if ways [a;b] , [c;d] cross each other if connect points lines on paper.

the point defined (x|y) can drawn 2-dimensional coordinate system.

how can check in o(1)?

there effective method check whether 2 line segment intersect: ab , cd intersect, if c , d points lie in different semi-planes relative ab line, , c , d lie in different semi-planes relative 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) , ccw(a,b,c) != ccw(a,b,d) 

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