How can I check if two segments intersect?

python math geometry
aneuryzm picture aneuryzm · Oct 1, 2010 · Viewed 121.2k times · Source

How can I check if 2 segments intersect?

I've the following data:

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ]

I need to write a small algorithm in Python to detect if the 2 lines are intersecting.


alt text

Answer

Grumdrig picture Grumdrig · Apr 3, 2012

User @i_4_got points to this page with a very efficent solution in Python. I reproduce it here for convenience (since it would have made me happy to have it here):

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

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

Related questions

How can you determine a point is between two other points on a line segment?

Let's say you have a two dimensional plane with 2 points (called a and b) on it represented by an x integer and a y integer for each point. How can you determine if another point c is on the line …

Read More
Evenly distributing n points on a sphere

I need an algorithm that can give me positions around a sphere for N points (less than 20, probably) that vaguely spreads them out. There's no need for "perfection", but I just need it so none of them are bunched together. …

Read More
Calculate angle of triangle Python

I'm trying to find out the angle of the triangle in the following, I know it should be 90 degrees, however I don't know how to actually calculate it in the following: Here's what I've tried: angle = math.cos(7/9.899) angleToDegrees = math.…

Read More