从Delaunay三角剖分计算alpha形状的边界多边形 [英] Calculate bounding polygon of alpha shape from the Delaunay triangulation

问题描述

给定平面中的一组点，对于给定的正数α，α形的概念通过找到Delaunay三角剖分并删除至少一个边缘的长度超过α的任何三角形来定义。以下是使用d3的示例：

http：// bl.ocks.org/gka/1552725

问题是，当有数千个点时，简单地绘制所有的内部三角形太慢了一个交互式可视化，所以我想只找到边界多边形。这不是那么简单，因为从这个例子中可以看到有时可能有两个这样的多边形。

作为简化，假设已经执行了一些聚类确保对于每个三角测量具有唯一的边界多边形。找到这个边界多边形的最佳方法是什么？特别地，边缘必须一致地排序，并且必须支持孔的可能性（认为环形或环形形状 - 这在GeoJSON中是可表达的）。

解决方案

1. 创建一个图形，其中节点对应于Delaunay三角形，并且两个三角形之间有一个图形边界，顶点。




2. 计算图的连接分量。




3. ，找到具有少于三个相邻节点的所有节点（即，具有度0，1或2的那些节点）。这些对应于边界三角形。我们将不与另一个三角形共享的边界三角形的边界定义为该边界三角形的边界边。

例如，我在您的示例问号Delaunay三角剖分中突出显示了这些边界三角形：

根据定义，每个边界三角形最多相邻两个边界三角形。边界三角形的边界形成循环。您可以简单地遍历这些周期，以确定边界的多边形形状。如果您在实施过程中牢记这些多边形，这也适用于带有空格的多边形。

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.

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).

解决方案

1. 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.

2. Compute the connected components of the graph.

3. 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.

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屋！