How to find list of line segments inside a polygon

Question

I have a line and a polygon . The line can be partially inside and partially outside the polygon . The line can intersect the polygon at a single point or at multiple points. The example lines are shown as below

Please refer the picture . For horizontal red colored line I would like to get list of line segments . The desired output is (A-B) (C-D) (E-F) and for vertical line I want to get line segments 1-2 .

I went through how to detemine if a line segment is inside of a polygon? and other questions of stack overflow .

but could not get most optimized algorithm to get a list of line segments inside the polygon.

I went through the following link also https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm but my question is there more optimized algorithm to find line segments within the polygon ?

Answer 1

I am answering in the case that no preprocessing is allowed, i.e. you have a single line segment (or a few) to process for a given polygon. The polygon is general (and can be with holes).

Rotate the line to make it horizontal, and simultaneously rotate the polygon vertices.

Then a side of the polygon intersects the supporting line of the segment if the endpoints have ordinates of a different sign. In this case, you can compute the location of the intersection.

The subsegments inside the polygon are made from the ordered intersection points found between the segment endpoints.