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

Question

As you can see in the image below, my question is how to determine the polygons formed by a series of points.

• In the left figure, the sequence of points {A, B, C, D, E, A}, therefore, it simply forms 1 polygon {A, B, C, D, E}.

• On the right side of the figure is a sequence of points {A, B, C, D, E, F, A}. It creates 2 polygons {A, F, G } and {B, C, D, E, G }, where G is the intersection point from the line AB and FE.

I'm not only interested in the number of polygons, but I also want to know information about the polygons (polygonal rows of points) that are created from it.

These algorithms will be used in the mobile device in real time, so it must be fast enough to calculate. Oh, and a series of points will be created by custom touch points.

Assumptions:

• Only consists of 2 collinear points
• This is not always a closed polygonal chain. For example, from the figure on the right, a number of points are {A, B, C, D, E, F}, there is no edge FA.

I was thinking about a solution, and looking at the intersection points, I was stuck with a solution O (N ^ 2), N = number of edges. The optimization that I can make of this is to maintain sets of strings in some regions, so I just minimize the total strings that can be computed by each other.

As for the solution for extracting those polygons, I'm still stuck.

Answer 1

First, find all the points where the segments intersect, and create new segments ending with them so that the segments do not intersect (except for their ends). Then think of it as a graph and delete each vertex of degree 1 until all such vertices disappear.

Mark all sides of all segments as not visited. For each side S segment (A, B) not visited (A, B) walk A, B, C, ..., A , the queue that is most on your side S (minimum or maximum sorting angle) is always executed. You just found a training ground. This will give you another polygon, which is "everything else on the plane."

The total complexity is O (n ^ 2).

Answer 2

Here is a solution that can help you: -

• Find intersections between lines that are sides of polygons.
• Make a directed graph containing intertexts and vertices with directed edges in the form of sides of polygons
• Make DFS and save another stack to place the visited peaks. When a visited vertex is reviewed in DFS, then place a separate stack up to that vertex. The vertices found are the vertices of the polygon. the number of times you encounter the visited vertex, the number of polygons formed and the pop-up vertices are in this order, the sides of the polygons.

Difficulty of time: -

 1. Finding all intersections take O(NlogN) if efficient algorithms are used 2. O(N) for making graph out of intersections and vertices. 3. O(N) for DFS 

Total difficulty: - O(NlogN)