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

 

正如你可以看到下面的示例图片，我的问题是如何确定由一系列点形成的多边形。

  • 在左图中，点的序列是{A，B，C，D，E，A}，所以它只形成1个多边形{A，B，C，D，E}。

  • 在图片的右侧，点系列是{A，B，C，D，E，F，A}。 它创建2个多边形{A，F， G }和{B，C，D，E， G }，其中G是AB和FE的交点。

    • 我不仅对多边形的数量感兴趣，而且我也想知道从它创建的多边形信息（多边形的一系列点）。

    这些算法将在移动设备中实时使用，因此它必须足够快以进行计算。 哦，一系列点将由用户的拖动触点生成。

    假设：

  • 只包含2个共线点
  • 它并不总是闭合链多边形。 例如，从右边的图片可以看出，一系列的点是{A，B，C，D，E，F}，没有边缘FA。

    • 我一直在考虑解决方案，并且为了查看交叉点，我坚持O（N ^ 2）解，N =边数。 我可以做的优化是维护一些区域内的线条集合，所以我只是最小化可以相互计算的总线。

    至于提取多边形形成的解决方案，我仍然陷入困境。

    插图

    首先，找到所有分段交叉的点，并在那里创建新分段，以便不再有分段交叉（除了它们的末端）。 然后将其视为一个图，并删除每个1度的顶点，直到所有这些都消失。

    将所有细分市场的所有方面都标为未访问。 对于每段未被访问的S段(A, B)步行A, B, C, ..., A总是进行S侧最多的转弯（角度排序最小或最大）。 你刚刚找到一个多边形。 这会给你一个额外的多边形，这是“所有在飞机上休息”。

    总体复杂度O（n ^ 2）。

    这是一个可以帮助你的解决方案：

  • 找到多边形的边线之间的交点。
  • 制作一个有向图，其中包含具有有向边的交点和顶点作为多边形的边
  • 做DFS并维护另一个堆栈以放置已访问的顶点。 当访问顶点在DFS中重新访问时，弹出单独的堆栈直到该顶点。 弹出的顶点是多边形的顶点。 您遇到访问顶点的次数是形成的多边形的数量，并且弹出的顶点按顺序排列在多边形的边上。

    • 时间复杂度： - 

    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

    总复杂度： - O(NlogN)

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

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

    下一篇: render multiple responses in one action