Line Intersection

Robert P. Munafo, 2023 Feb 21.

Determining the intersection of two lines is a common algebra problem with many applications. For exploring the Mandelbrot set in particular, it is useful to use the Jordan Curve Theorem to locate mu-atoms within a rectangle of interest. That can be facilitated by the determining if arbitrary edges (of e.g. a quadrilateral) intersect the real axis, and if so computing the real value at which it intersections.

Formally, if the endpoints of the line segment are (a, b) and (c, d) then one can first look at the Y values to see if they are the same or different.

If both Y values (b and d) are positive, or if both are negative, then the line segment does not intersect the real axis.

If both Y values are zero then the entire line segment is on the real axis. (There is an intersection, but for purposes of the Jordan Curve Theorem it means that the point of interest is on the boundary of the polygon, so it doesn't matter if we count this edge or not.)

If just b is zero, an intersection exists and the corresponding X value is a.

If just d is zero, the line segment is considered to not intersect the real axis (this is to avoid an erroneous double-intersection when considering a closed polygon with the Jordan Curve Theorem).

Otherwise, the line segment crosses the real axis at one point that is not either endpoint, and the real coordinate i (point of intersection) is computed as follows:

p = -b/(d-b)
i = a + p(c-a)

or as a single expression:

i = a - b*(c-a)/(d-b)

The denominator (d-b) will not be zero because we already determined that one of the values d or b is positive and the other negative.

Example

The coordinates are (a, b) = (1, 7) and (c, d) = (3, -2). Find the X value where the line segment crosses the real axis.

(1,7) . . . . ______________________ . . (3,-2)

Compute p: -b/(d-b) = -7/(-2-7) = 7/9. This tells us that the intersection occurs 7/9 of the way along the line segment.

The answer is a + p(c-a) = 1 + (7/9)*(3-1) = 1 + 14/9 = 23/9 or about 2.556.

If we exchange the endpoints (i.e. swap the values of a and c, and of b and d) then the calculation is different but yields the same answer:

p = -b/(d-b) = -(-2)/(7+2) = 2/9
i = a + p(c-a) = 3 + (2/9)*(1-3) = 3 - 4/9 = 23/9.

revisions: 20230220 first version; 20230221 intersection when b=0 but not when d=0

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2023 Feb 21.

s.27