Given a non self-intersect polygon and a line. How can I calculate the total length of parts of line which are inside the polygon? I need an O(NlogN) or faster algorithm, where N is the number of vertices of polygon.
For example, below is the polygon ABCDEFGH.
With line y = 0, no parts inside the polygon.
With line y = 2, the parts inside the polygon are IJ and KL, and the total length is 2.5.
With line y = 3, the part inside the polygon is BC, which has length 1,
I'm looking for your answers. Thanks for your help.