intersection of closed polygonal chain and line

Question

I need to find algorithms that find 2 intersection points of closed polygonal chain and line. My polygonal chain is defined as a set points coordinate (x,y) and I have also equation of the line.

To be precise, please look at the picture below. My input is equation of the line and P1...Pn. I would like to find coordinates of the points X1 and X2.

Answer 1

The original question was: Given a set of points in a closed polygonal chain and the equation for a line, find all points of intersection.

We must take care in devising an algorithm to solve this as we make no assumptions on whether: * the equation for the line has a real and non-zero slope, or * the polygonal chain is simple or self-intersecting, and whether it bounds to a concave or convex polygon.

Consider, for instance, the special case where the equation for the line is x = a, meaning it has a slope of ∞, i.e., it is parallel to the y-axis:

Here, we cannot test for intersection by plugging in P_i and P_i+1 into the line equation (they give the same value!).

Additionally, this example also illustrates the reason why we cannot solve for the point of intersection, X_i, by rearranging the linear equations if either line is vertical.

A naive algorithm that would provide a solution that accounts for all cases would involve clipping the line by a bounding box for the polygon and solving for the intersection between the resulting line segment and each edge of the polygon.

Algorithm:

Let V be a set of n points of a closed polygonal chain, P₁, ..., P_n, in two-dimensional Euclidean space (R²) and L be a line, also in R², described by the linear equation of the form:

Where a, b and c are known real scalars, with a and b not both zero.

1. Compute a bounding box of P₁, ..., P_n. Note: The axis-aligned minimum bounding box is the most trivial and can be computed easily:

   Let X = the set of x components of the points in V and Y = the set of y components of the points in V.

   The closed polygonal chain defining the vertices of the axis-aligned minimum bounding box is: (min(X), min(Y)), (max(X), min(Y)), (max(X), max(Y)), (min(X), max(Y)), (min(X), min(Y))

2. Clip the line L by the bounding box we just calculated to produce the line segment, L', described by the pair of vectors u and v and scalar t:

To find u and v, we must calculate where our line intersects with each edge of the bounding box:

Let B = the closed polygonal chain defining the vertices of the axis-aligned rectangular bounding box we just calculated, with B(i) = the i-th point in the chain.

For i = 1 to 4:
    Let j = i + 1. Then:
        xi = the x component of Bi
        yi = the y component of Bi
        xj = the x component of Bj
        yj = the y component of Bj

    If xi == xj: # The edge is vertical
        Let xk = xi.

        If b != 0:
            yk = (c - a * xk) / b # Calculate the y component of the line at xk

            If (yi <= yk AND yk <= yj) OR (yj <= yk AND yk <= yi):
                The line intersects at (xk, yk)!

        Else: # b == 0, implying a vertical line
            If xk == c / a:
                The vertical line is at xk, so define two intersecting points as the ends of the line segment:
                (xk, yi) and (xk, yj)

    Else If yi == yj: # the edge is horizontal
        Let yk = yi.

        If a != 0:
            xk = (c - b * yk) / a # Calculate the x component of the line at yk

            If (xi <= xk AND xk <= xj) OR (xj <= xk AND xk <= xi):
                The line intersects at (xk, yk)!

        Else: # a == 0, implying a horizontal line
            If yk == c / b:
                The horizontal line is at yk, so define two intersecting points as the ends of the line segment:
                (xi, yk) and (xj, yk)

Note: This is a trivial algorithm for detecting the intersecting points of the simple axis-aligned minimum bounding box as described in step 1. For other quadrilaterals, a more complex generalization will be needed to account for the case where xi != xj AND yi != yj.

After running this loop you will have 0, 1 or 2 intersecting points between the line and the bounding box.

• If 0 intersecting points are found, the line will not intersect the polygon and the algorithm finishes.
• If 1 intersecting point is found, the line intersects one of the vertices of the bounding box tangentially. Check if the point is also in the set V. If so, it is the only intersecting point between your line and the polygon.

• If 2 intersecting points are found, the compute u and v as follows:

  Let the two intersecting points be defined as (xa, ya) and (xb, yb). Then:

  u = (xa, ya) and v = (xb - xa, yb - ya)

Finally, we have clipped our line to the line segment with ends u and u + v.

3. Now, to calculate all possible intersecting points, simply find the intersecting points between this line segment and the line segment defined by each pair of points in the set of vertices V of our polygon:

Define V(k) as the k-th point in V, P_k.

For i = 1 to n - 1:
    Let p = V(i) and
        q = V(i + 1) - V(i),
    such that p and q are the end points of the edge/line segment between vertices i and i + 1.

    With u and v from the last step, find any intersecting points between the line segments:
        u + t * v, and
        p + s * q,
    where s is a scalar and 0 <= s <= 1.

Finding the intersection between the line segments is easily done when they are in parametric form. Essentially, the two line segments are orthogonally projected onto each other and special cases are checked.

An algorithm for finding the intersecting points between a pair of line segments was described here on SO previously.

For a more in-depth explanation, this website goes into more detail on the line segment intersection algorithm.

Answer 2

Given the equation of that line as a*x+b*y+c=0, you can find out on which side of that line each point is, just plug the x,y coordinates of the point P_k into that expression:

S_k = a*x_k + b*y_k + c

For points on the line the result S_k is 0 (it obeys the line equation). For points on one side of the line the result will be > 0, for points on the other side the result will be < 0. Do this sequentially for each point, until the sign switches: S_k * S_{k-1} < 0. The line crosses between P_k and P_{k-1}.