Overlapping line segments in 2D space

Question

I need to find whether two lines overlap each other. I have the intersection code which returns 0, if two lines are parallel. But then I need to know if these two parallel lines overlap.

Edit:

A                    C       B                D
-----------------------------------------------

Line 1: A-B

Line 2: C-D

I need to find if Line 1 overlaps Line 2, but both lines can have a slope > 0.

Answer 1

You can compare to find if there is no over lap. you will have less comparisons in this way thus very efficient. Do following comparisons

D < A

B < C

If either case is true the lines are not overlapping. otherwise there must an overlap. You will make least number of comparisons to determine if they are not overlapping. Otherwise there will be more comparisons to make.

Answer 2

Since you know they're both parallel, then just check whether line segment CD contains either of the endpoints of the first line (point A and point B).

Answer 3

For two co-linear line segments that are not necessarily axis-aligned:

1. Sort the vertices in clockwise order around the origin.
2. The lines overlap if the ordered vertices alternate between the two segments, e.g. Line1.Point1, Line2.Point1, Line1.Point2, Line2.Point2.

Answer 4

It is sufficient to calculate the areas of triangles ACB and CBD. If the area is 0, then the points are collinear, and if both areas are zero then the lines are overlapping.

You can calculate the area of a triangle ABC by this formula:

2*Area(ABC)= (bx – ax)(cy – ay) – (cx – ax)(by – ay);

Answer 5

Line equation is direction of line in infinite, by finding slope or intercept you wont be able do anything with them(even though horizontal line doesn't have slope), i suggest use point on line. so AB is your line [(x,y),(x,y)] and C is on of the point (x,y) and then you need to check if point on the line.
Check Point On a Line

Answer 6

We are given two line segments

AB = line segment from (A_x,A_y) to (B_x,B_y)
CD = line segment from (C_x,C_y) to (D_x,D_y)

with the same slope.

• Order the endpoints E₁ < E₂ < E₃ < E₄ such that E_i,x ≤ E_i+1,x and E_i,y ≤ E_i+1,y if E_i,x = E_i+1,x
• If E₁ and E₂ are from different segments, the overlap is the segment from E₂ to E₃.

There are some degenerate cases:

• A < B = C < D
• A < C = D < B
• A < B = C = D
• A = B = C = D

These result in a single point of intersection. I'm not sure if any of those can occur in your system, but if so you'll have to decide whether or not you consider that "overlap" and add special case checks.

Answer 7

The characteristic of two segments of being in the same lines is called collinearity and can be tested calculating the area of the 2 triangles formed by one segment endpoints and, respectively, the endpoints of the other segment. If the area is zero or close to zero below a threshold the segments are collinear.

    public static bool AreSegmentsCollinear(Segment a, Segment b, double epsilon)
    {
        return IsPointCollinear(a, b.Left, epsilon) && IsPointCollinear(a, b.Right, epsilon);
    }

    public static bool IsPointCollinear(Segment a, Vector2D p, double epsilon)
    {
        return Math.Abs(GetSignedTriangleArea2(a, p)) <= epsilon;
    }

    /// <returns>The squared signed area of the triangle formed with endpoints
    /// of segment a and point p</returns>
    public static double GetSignedTriangleArea2(Segment a, Vector2D p)
    {
        return (p - a.Left) ^ (a.Right - a.Left);
    }

   /// <summary>Cross product of vectors in 2D space. NB: it returns a
   /// magnitude (scalar), not a vector</summary>
   /// <returns>The area of the parallelogram formed with u, v as the edges</returns>
   public static Double operator ^(Vector2D u, Vector2D v)
   {
       return u.X * v.Y - u.Y * v.X;
   }

Answer 8

Just to be clear since there seems to be some confusion in the answers, the question being asked is as follows. Given two 2D line segments A and B how do I determine if both of the following are true:

1. A and B are colinear.
2. A and B intersect.

Note that there are tolerances involved in both questions i.e. how close to parallel and how near each other do A and B need to be to be considered colinear? How much do they need to overlap to be considered overlapping?

I think to handle such tolerances robustly the best algorithm is to treat the line segments as thin rectangles, where the thickness of the rectangles is a tolerance parameter t1. Let t2 be another tolerance parameter on slopes that are considered parallel. Then the algorithm becomes

1. If the slope of A and the slope of B are not within t2 of each other return false. To handle vertical lines cleanly, slope can be represented as a unit vector and the test can be on whether the Euclidean distance between the two unit vectors is smaller than t2.

2. Represent A and B as (non-axis-aligned) rectangles R1 and R2. Where R1 encloses A in the obvious way, i.e. it is length(A) + t1 units long and is t1 units wide with A centered inside it, and R2 analogously encloses B.

3. Determine if R1 and R2 intersect each other. This can be done relatively efficiently by treating each rectangle as the union of two triangles and testing for triangle-triangle intersections across all combinations of A triangles and B triangles. If there is an intersection return true; otherwise return false.

Answer 9

With lines l1 and l2 given in the following form [x1, y1, x2, y2] the following python code will give the intersection for collinear line segments with any slope.

intersection = line_intersect(l1, l2)

def line_intersect(l1, l2):
    """Find the intersection of two line segments"""
    
    x1, y1, x2, y2 = l1
    x3, y3, x4, y4 = l2
    
    x_inter = component_intersect(x1, x2, x3, x4)
    y_inter = component_intersect(y1, y2, y3, y4)
    
    return math.sqrt(x_inter**2 + y_inter**2)
    
def component_intersect(c1, c2, c3, c4):
    """Calculate intersection in one dimension/component"""
    
    # find left endpoints
    cl1 = min(c1, c2)
    cl2 = min(c3, c4)
    
    # find right endpoints
    cr1 = max(c1, c2)
    cr2 = max(c3, c4)
    
    # find endpoints of intersection
    c_inter_l = max(cl1, cl2)
    c_inter_r = min(cr1, cr2)
    # calcuate intersection
    c_inter = c_inter_r - c_inter_l
    c_inter = max(c_inter, 0)
    
    return c_inter