How to calculate number of polygons that are formed by sequence of points in 2D?

Question

As you can see the example picture below, my question is how to determine the polygons that are formed by series of point.

1. On the left picture, the series of point is {A, B, C, D, E, A}, so it just forms 1 polygon {A, B, C, D, E}.

2. On the right side of the picture, the series of point is {A, B, C, D, E, F, A}. It creates 2 polygons {A, F, G} and {B, C, D, E, G}, where G is intersect point from line AB and FE.

I am not only interested in the number of polygons, but i also want to know the polygon information (polygon's series of points) that are created from it.

This algorithms will be used in mobile device, in real time, so it must be fast enough to compute. Oh, and the series of points will be generated by user's drag touch points.

Assumptions:

1. Only consists of 2 collinear points
2. It is not always closed chain polygonal. For example from picture on the right, the series of points is {A, B, C, D, E, F}, there is no edge FA.

I have been thinking the solution, and for looking the intersections points, I am stuck with the O(N^2) solution, N = number of edges. The optimization that I can do from this, is maintaining the sets of lines within some regions, so I just minimize the total lines that can be calculated each other.

As for the solution to extract what polygons are formed, I am still stuck.

Answer 1

First, find all points where segments cross and create new segments ending there, so that no segments cross any more (except for their ends). Then think of it as a graph, and remove each vertex of degree 1 until all such are gone.

Mark all sides of all segments as not visited. For each not visited side S of segment (A, B) walk A, B, C, ..., A always taking the turn which is most on your S side (angle sort minimum or maximum). You just found a polygon. This will give you one additional polygon, which is "all the rest on plane".

Overall complexity O(n^2).