查找多边形的层次结构

Question

我需要一种算法来确定多边形的层次结构。例如，

我只有顶点的闭环，其中多边形具有 CCW 顶点顺序，孔具有 CW 顶点顺序。我想创建一个结构来包含这种多边形和孔的层次结构。

using Loop = std::vector<Point>;

class PolygonHierarchy
{
public:
    PolygonHierarchy(const std::vector<Loop>& loops);
    ~PolygonHierarchy();

private:
    class Polygon
    {
    public:
        std::vector<Point> vertices;
        std::vector<Polygon*> childPolygons;
        bool isCCWOrder;
    }

    std::vector<Polygon*> polygonHierarchies;
}

谁能解释一下如何找到子多边形并形成这样的树？（无需提供代码）。

Answer 1

根据@YvesDaoust 在评论中所说，对于每个 polygon/hole，您可以找到包含它的 all 和 polygons/holes。

这会给你一个有向图。在此图中，对于每个节点，您可能有多个传入边。例如，像这样：

1 (a)
|\
| \
|  2 (b)
3 /

在这里，1 和 2 都知道 3，但理想情况下只有 2 应该知道。在这里，1 是 2 的父级。如果您概括这一点，因为不会有任何相交的多边形，如果您有两个冲突节点 a 和 b，并且如果 a 是 [=13 的祖先=]，你可以丢弃a（否则丢弃b），你可以继续这样，直到每个节点只剩下一个输入边，

查找多边形的层次结构

Finding a hierarchy of polygons

c++

algorithm

math

computational-geometry