How to determine polygon based on point lists?

Question

I have several lists of interconnected points. They are ordered so I can connect them together. Using these interconnected points I'd like to find the different points and intersection points that form a polygon. I imagine it's something often done in video game but I struggle to find a clear explanation.

Thanks for your help and guidance.

Original point set:

After having connected the points:

Desired polygon to find:

Answer 1

A possible solution is to cull points that you are certain that are not part of the polygon.

Start with a definition of the polylines:

List<point> polyline = new List<point>(); //I use a list versus array so 
                                          //it is easier to insert/remove 
                                          //points later.

polyline[0] = {P00, P01} //Red
polyline[1] = {P10, P11, P12} //Green
polyline[2] = {P20, P21, P22, P23} //Blue

Next, find the intersection points (a linesegment-linesegment intersection loop). Insert the found point in these polylines.

This results in:

polyline[0] = {P00, X02, X01, P01} //Red
polyline[1] = {P10, X03, P11, X01, P12} //Green
polyline[2] = {P20, X02, P21, P22, X03, P23} //Blue

If a polyline has no intersections, it is either completely outside of the polygon or completely inside the polygon. These lines may be removed.

Also if a polyline has only one intersection, one endpoint is inside the polygon and the other endpoint outside the polygon. Such line can also be removed. Keep in mind there may be an edge case where an intersection and a polyline vertex overlap.

You should now have a set of polylined that share part of the polygon.

Now cull the endpoints of the polylines if they do not share a common point (so if the point exists in another polyline it is also a polygon vertex. Repeat until the endpoints of the polylines are shared points.

This results in points bound by the polygon.

polyline[0] = {X02, X01} //Red
polyline[1] = {X03, P11, X01} //Green
polyline[2] = {X02, P21, P22, X03} //Blue

Using the shared endpoints you can reconstruct the polygon. You may need to reorder the polyline (example; righthand endpoint X01 of the Red line is connected to the righthand endpoint X01 of the green polygon, so you need to reverse the green line).

polygon = {X02, X01, P11, X03, P22, P21, X02} 

Again it might be required to reverse the polygon to keep clockwise notation.

A few points to note:

• Polylines can have shared endpoints to begin with (in the Green and Blue lines P10 could be the same as P23).
• If multiple polygons are possible (P20 lies below line P11-P12) it will work, but the result may not be what you are looking for.
• Keep rounding and floating point errors in mind when checking if a point is equal to another point. Prevent calculating the same intersection twice.