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

 

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

  • 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}.

  • 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:

  • Only consists of 2 collinear points
  • 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.

    插图

    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).

    Here is a solution which might help you : -

  • Find intersections between lines that are sides of polygons.
  • Make a directed graph containing interections and vertices with directed edges as sides of polygons
  • Do DFS and maintain another stack to put visited vertices. When visited vertex is revisited in DFS then pop the separate stack till that vertex. The vertices popped are a vertices of a polygon. The number times you encounter a visited vertex is the number of polygons formed and popped vertices are in that order the sides of the polygons.

    • Time complexity : - 

    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 complexity: - O(NlogN)

    链接地址: http://www.djcxy.com/p/18724.html

    上一篇: 将IEnumerable <dynamic>转换为DataTable

    下一篇: 如何计算2D中点序列形成的多边形数量？