Algorithm to find all line segment intersections given n lines

Question

I'm looking for a algorithm to find all the intersection points given n line segments. Below is the pseudo code from http://jeffe.cs.illinois.edu/teaching/373/notes/x06-sweepline.pdf

The input S[1 .. n] is an array of line segments. label[i] is the label of the ith leftmost endpoint.

sort the endpoints of S from left to right
create an empty label sequence
for i ← 1 to 2n
    line ← label[i]
    if isLeftEndPoint[i]
        Insert(line)
        if Intersect(S[line], S[Successor(line)])
            return TRUE
        if Intersect(S[line], S[Predecessor(line)])
            return TRUE
    else
        if Intersect(S[Successor(line)], S[Predecessor(line)])
            return TRUE
        Delete(label[i])

return FALSE

Apply the algorithm to the line set below, only one intersection point is checked. What should I do to know the existence of the other 2 intersection points?

line[1] enters
line[2] enters, intersection between line[1] and line[2] is checked.
line[3] enters, intersection between line[2] and line[3] is checked.
line[4] enters, intersection between line[4] and line[1] is checked. Intersection A is found.
line[4] leaves, nothing is checked.
line[1] leaves, nothing is checked.
line[2] leaves, nothing is checked.
line[3] leaves, nothing is checked.

I think the described algorithm only checks whether a set of lines intersect or not. It doesn't find intersection points nor does it count intersections. — M Oehm, Nov 20 '15 at 07:29
see [brute force lines/lines intersections algorithm with area subdivision](http://stackoverflow.com/a/18739791/2521214) — Spektre, Nov 20 '15 at 08:01
@MOehm I think you are correct. I wrongfully assumed that the algorithm was meant to find ALL the intersection points. — Tik-Un, Nov 20 '15 at 08:54
You state to be looking for an `algorithm to find all the intersection points given n line segments` - lets assume in 2D. You present a procedure, omitting its name (AnyIntersections). `5.` to `8.` are not going to happen, as AnyIntersections terminates with `4.`, returning TRUE. _What is your question?_ — greybeard, Nov 20 '15 at 11:12
After finding the intersection A, you need to treat the lines segments around it as new lines. — Eyal, Dec 14 '17 at 05:05

Hans Blanco · Answer 1 · 2015-11-23T07:45:49.640

Standard line equation Ax+By=C

The slope(m) of a line defined by the standard line of equation is

m = -(A/B)

Point-slope line equation y-y1=m(x-x1)

Substituting m = (-A/B) in the point-slope line equation y2-y1 = (A/-B)*(x2-x1)

(y2-y1)/(x2-x1) = A/-B

thus:

A = y2-y1
B = x1-x2 C = Ax+By

x = (C-By)/A

y = (C-Ax)/B

Given two lines with equation A1x1+B1y1=C1 and A2x2+B2y2=C2.
Then the point of intersection between the lines is specified by the points that make
A1x+B1y-C1 = A2x+B2y-C2

A1x+B1y=C1
A2x+B2y=C2

A1B2x+B1B2y=B2C1 (multiply the first equation by B2)
A1B2x+B1B2y-B2C1=0

A2B1x+B1B2y=B1C2 (multiply the second equation by B1)
A2B1x+B1B2y-B1C2=0

Equating the two equations
A1B2x+B1B2y-B2C1=A2B1x+B1B2y-B1C2
A1B2x+B1B2y-B2C1-A2B1x-B1B2y+B1C2=0
A1B2x-B2C1-A2B1x+B1C2=0
A1B2x-A2B1x=B2C1-B1C2
x(A1B2-A2B1)=B2C1-B1C2

x = (B2C1-B1C2)/A1B2-A2B1

A1x+B1y=C1
A2x+B2y=C2

A1A2x+A2B1y=A2C1 (multiply the first equation by A2)
A1A2x+A2B1y-A2C1=0

A1A2x+A1B2y=A1C2 (multiply the second equation by A1)
A1A2x+A1B2y-A1C2=0

Equating the two equations

A1A2x+A2B1y-A2C1=A1A2x+A1B2y-A1C2
A1A2x+A2B1y-A2C1-A1A2x-A1B2y+A1C2=0
A1C2-A2C2=A1B2y-A2B1y
A1B2y-A2B1y=A1C2-A2C2
y(A1B2-A2B1)=A1C2-A2C1
y(A1B2-A2B1)=A1C2-A2C1
y = (A1C2-A2C1)/(A1B1-A2B1)

the denominator in y and in x are the same so denominator = A1B1-A2B1

thus:

x = (B2C1-B1C2)/denominator
y = (A1C2-A2C1)/denominator

These are the x and y coordinates of the intersection of two lines with points (x1, y1), (x2, y2)
and (x3, y3), (x4, y4)

Now for a line segment it's the same but we need to check that the x or y coordinate is in both segments. That means between the x coordinate of both segments with lesser value and the x coordinate of both segments with greater value

This is a C++ program that returns true if the segments intersect and returns false if they don't. If the segments intersect it stores the point of intersection in a variable i.

struct Point
{
    float x, y;
};

//p1 and p2 are the points of the first segment
//p3 and p4 are the points of the second segment
bool intersection(Point p1, Point p2, Point p3, Point p4, Point &i)
{
    float max1; //x-coordinate with greater value in segment 1
    float min1; //x-coordinate with lesse value in segment 1
    float max2; //x-coordinate with greater value in segment 2
    float min2; //x-coordinate with lesser value in segment 2
    float A1 = p2.y - p1.y;
    float B1 = p1.x - p2.x;
    float C1 = A1 * p1.x + B1 * p1.y;
    float A2 = p4.y - p3.y;
    float B2 = p3.x - p4.x;
    float C2 = A2 * p3.x + B2 * p3.y;
    float denom = A1 * B2 - A2 * B1;

if (denom == 0.0) //When denom == 0, is because the lines are parallel
    return false; //Parallel lines do not intersect

i.x = (C1 * B2 - C2 * B1) / denom;
i.y = (A1 * C2 - A2 * C1) / denom;

if (p1.x > p2.x)
{
    max1 = p1.x;
    min1 = p2.x;

}
else
{
    max1 = p2.x;
    min1 = p1.x;
}

if (p3.x > p4.x)
{
    max2 = p3.x;
    min2 = p4.x;

}
else
{
    max2 = p4.x;
    min2 = p3.x;
}

//check if x coordinate is in both segments
if (i.x >= min1 && i.x <= max1 &&
    i.x >= min2 && i.x <= max2)
    return true;
return false; //Do no intersect, intersection of the lines is not between the segments

}

Now you just need to compare on a loop all the segments and store the intersection point on array.

(Does the first edit `find all the intersection points given n line segments`?) How many pairs do you need to check? (For one pair of segments, I'd do the simpler "range overlap test" first.) — greybeard, Nov 23 '15 at 07:45

Algorithm to find all line segment intersections given n lines

1 Answers1