- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
平面上有很多2D点。首先,我通过两种方法得到了一张图:
执行 Delaunay 三角剖分,然后删除每个三角形的最长边;
通过代码NGL获取相对邻居图:http://www.ngraph.org/
上述两种方法的结果似乎相似。 但现在,我有一个问题。如何从上面的相对邻域图中获取所有多边形?也就是说,这些多边形内部永远不会包含其他边。我想从图中获取所有子区域,因此我可能会先找到所有多边形。
有人知道怎么做吗?
最佳答案
首先,您提到的两个图表实际上是不同的图表类型:
Relative Neighbourhood Graph包含一条边ij
在没有另一个顶点的情况下k
满意dist(i,k) < dist(i,j)
和dist(j,k) < dist(i,j)
.
Urquhart Graph通过从 Delaunay Triangulation 中的每个三角形中删除最长的边而形成,正如你所提到的。
虽然这些图表通常相似,并且在某些情况下可能相同,但它们通常是不同的。
您的评论似乎表明您确实正在构建厄克特图 U
来自 Delaunay 三角测量 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
中的那些边。 - 这些是与不同多边形中的三角形相邻的边。
希望这有帮助。
关于graph - 如何从相对邻域图中获取闭合多边形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17926029/
我是一名优秀的程序员,十分优秀!