graph - 如何从相对邻居图中获取封闭多边形

Question

平面上有很多二维点。首先，我通过两种方法得到了一个图形：

1. 执行Delaunay三角剖分，然后删除每个三角形的最长边；

2. 通过代码NGL获取相对邻居图：http ://www.ngraph.org/

上述两种方法的结果似乎相似。 但现在，我有一个问题。如何从上述相对邻居图中获取所有多边形？也就是说，这些多边形永远不会包括内部的其他边。我想从图中获取所有子区域，所以我可能会先找到所有多边形。

有人知道怎么做吗？

Answer 1

首先，您提到的两个图表实际上是不同的图表类型：

1. 相对邻域图在没有另一个满足和ij的顶点的情况下包含一条边。kdist(i,k) < dist(i,j)dist(j,k) < dist(i,j)

2. 正如您所提到的，Urquhart Graph是通过从Delaunay Triangulation中的每个三角形中移除最长边而形成的。

虽然这些图通常相似，并且在某些情况下可能相同，但它们通常是不同的。

您的评论似乎表明您确实在U从 Delaunay Triangulation构建 Urquhart Graph T，因此，您可以更改边缘去除算法，以便在构建时也构建一组不相交的多边形U。

只需注意，当从三角剖分中删除一条边时，T您还会合并与该边相邻的两个多边形。最初，每个内部边缘将与两个三角形相邻，但随着边缘移除的进行，边缘将变得与更复杂的多边形相邻。

算法可以如下进行：

// Data-structures:
// S: a set of polygons - each polygon is a list of triangles
// P: a pointer to the parent polygon for each triangle
// Triangulation should give O(1) access to edge-adjacent triangles

S <- push each triangle as it's own initial polygon
P <- mark each triangle as it's own initial parent

while (removing edges)
    ij <- edge to be removed from U

    ti <- 1st tria adjacent to edge ij
    tj <- 2nd tria adjacent to edge ij

    pi <- P(ti); // poly containing ti
    pj <- P(tj); // poly containing tj

    // merge pi and pj into single poly
    S(pi) <- S(pj) // push triangles from pj onto pi
    P(S(pj)) = pi  // mark pi as parent for trias
                   // from pj
    S(pj) <- 0     // poly pj is now null
endwhile

结果将是一组不相交的多边形作为三角形列表。

形成多边形区域边界的边将是图中出现的那些边U——这些边是与不同多边形中的三角形相邻的边。

希望这可以帮助。