从 Delaunay 三角剖分计算 alpha 形状的边界多边形 [英] Calculate bounding polygon of alpha shape from the Delaunay triangulation
问题描述
给定平面中的一组点，对于给定的正数 alpha，alpha 形状的概念是通过找到 Delaunay 三角剖分并删除至少一条边长度超过 alpha 的任何三角形来定义的.这是使用 d3 的示例:
Given a set of points in the plane, a notion of alpha-shape, for a given positive number alpha, is defined by finding the Delaunay triangulation and deleting any triangles for which at least one edge exceeds alpha in length. Here's an example using d3:
http://bl.ocks.org/gka/1552725
问题是，当有数千个点时，简单地绘制所有内部三角形对于交互式可视化来说太慢了，所以我只想找到边界多边形.这并不那么简单，因为正如您从该示例中看到的那样，有时可能有两个这样的多边形.
The problem is that, when there are thousands of points, simply drawing all the interior triangles is too slow for an interactive visualization, so I'd like to just find the bounding polygons. This isn't so simple, because as you can see from that example sometimes there might be two such polygons.
作为一个简化，假设已经执行了一些聚类，以便保证每个三角剖分都有一个唯一的边界多边形.找到此边界多边形的最佳方法是什么?特别是，边缘必须一致排序，并且必须支持洞"的可能性(想想圆环或甜甜圈形状——这在 GeoJSON 中可以表达).
As a simplification, suppose some clustering has been performed so that there's guaranteed to be a unique bounding polygon for each triangulation. What's the best way to find this bounding polygon? In particular, the edges have to be ordered consistently and it must support the possibility of "holes" (think a torus or donut shape--this is expressible in GeoJSON).
推荐答案
创建一个图，其中的节点对应于 Delaunay 三角形，并且当且仅当它们共享两个顶点时，两个三角形之间存在图边.
Create a graph in which the nodes correspond to Delaunay triangles and in which there is a graph edge between two triangles if and only if they share two vertices.
计算图的连通分量.
对于每个连通分量，找出所有相邻节点少于三个的节点(即，度数为 0、1 或 2 的节点).这些对应于边界三角形.我们将不与另一个三角形共享的边界三角形的边定义为该边界三角形的边界边.
For each connected component, find all of the nodes that have less than three adjacent nodes (that is, those that have degree 0, 1, or 2). These correspond to the boundary triangles. We define the edges of a boundary triangle that are not shared with another triangle to be the boundary edges of that boundary triangle.
例如，我在您的问号"Delaunay 三角剖分示例中突出显示了这些边界三角形:
As an example, I have highlighted these boundary triangles in your example "question mark" Delaunay triangulation:
根据定义，每个边界三角形最多与两个其他边界三角形相邻.边界三角形的边界边形成循环.您可以简单地遍历这些循环以确定边界的多边形形状.如果您在实现中牢记它们，这也适用于带孔的多边形.
By definition, every boundary triangle is adjacent to at most two other boundary triangles. The boundary edges of boundary triangles form cycles. You can simply traverse those cycles to determine polygon shapes for the boundaries. This will also work for polygons with holes if you keep them in mind in your implementation.
这篇关于从 Delaunay 三角剖分计算 alpha 形状的边界多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
