Compute length of segment intersecting a polygon in 2D

Question

Given a segment S and a polygon P, is there a fast algorithm that returns the total length of the subsegments of S crossing polygon P?

Note: P is defined by a closed LineString (i.e.: an array of points where the first and last one are equal). P does not have any "holes", but can be concave and/or self-intersecting.

Note: the final goal is the total length of all the intersecting subsegments, and if this can be done faster without retrieving an explicit array of all of them, all the better.

Bonus points: a Java implementation for said algorithm. Using libraries like JTS is ok, as long as the resulting solution is fast.

A simple solution using JTS already exists but does not support self-intersecting polygons and, I believe, is not the fastest. This solution involves creating a Polygon object (for P), a 2-point LineString object (for S), and getting the length of the resulting intersection.

Here is the code that does that:

    GeometryFactory fact = new GeometryFactory();
    WKTReader wktRdr = new WKTReader(fact);

    String wktP = "POLYGON((40 100, 40 20, 120 20, 120 100, 60 40, 40 100))";
    String wktS = "LINESTRING(20 60, 160 60)";
    Geometry pl = wktRdr.read(wktP);
    Geometry ls = wktRdr.read(wktS);
    Geometry in = pl.intersection(ls);
    System.out.println("P = " + pl);
    System.out.println("S = " + ls);
    System.out.println("P intersection S = " + in);
    System.out.println("S length = " + ls.getLength());
    System.out.println("P intersection S length = " + in.getLength());

EDIT: a consideration on self-intersecting polygons: a solution, although maybe not the fastest, could involve pre-processing a self-intersecting polygon by splitting it into multiple non-self-intersecting ones.

Some explanations and some pseudo-code on this matter are here: Algorithm to split self-intersected Path2D into several not self-intersected paths?

Answer 1

Finding the intersection length of non-self-intersecting polygons in O(n*log n).

Pseudo-code:

function intersecting_segment_length(set P, segment S):
  let starting_point = the bottom-most, left-most point in P.
  let E1, E2 = the edges of starting_point

  let intersections = new array.
  do:
     while E1 != E2 and E1 does not cross S:
        E1++ //move E1 "clockwise" around P
     while E2 != E1 and E2 does not cross S:
        E2-- //move E2 "counterclockwise" around P
     if E1 != E2:
        p1 = the intersection of E1 and S
        p2 = the intersection of E2 and S
        intersections.add(new line segment from p1 and p2)
  until E1 == E2.

  return sweepline(intersections)

Sweepline pseudo-code:

function sweepline(array segments):
  let points = start and end points of all segments
  sort points as they intersect S

  let last_point = points.first()
  let num_segments = 0 //num segments intersected by sweepline
  let length = 0

  for each point p in points - last_point:
     if p is the leading point in p.owning_segment:
        num_segments++
     else: //trailing point
        num_segments--
        if num_segments % 2 == 0: //I think
           length += distance between p and last_point
     last_point = p

  return length

Complexity:

• Walking edges in P: O(n), where n is the number of edges/vertices in P.
• Sort intersection points: O(m*log m), where m is the number of intersections of P with S.
• Using a sweepline to find total length: O(m).
• Unfortunately, we can construct a "comb-shaped polygon" with O(n) intersections with S, so the total complexity is O(n*log n) in the worst case.

Note:

• If you can determine the self-intersections of P (for example, while you're walking around P), you can inject those events into the sweepline and modify it's algorithm accordingly. The result can probably be done in O(n*log n).
• For a sample sweepline implementation (less pseudo-code), you can look at this answer.