计算阿尔法形状的边界多边形的Delaunay三角 [英] Calculate bounding polygon of alpha shape from the Delaunay triangulation

问题描述

给定一组点在平面上，α-形状的概念，对于给定的正数的α，通过找到Delaunay三角和删除的量的至少一个边缘超过α的长度的任何三角形定义。下面是一个使用D3例如：

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

的问题是，当有几千点，只需绘制所有的内部三角形是一个交互式可视化速度太慢，所以我想只要找到边界的多边形。事实并非如此简单，因为你可以从这个例子看到，有时可能有两个这样的多边形。

作为一种简化，假设一些聚类已经执行，使得还有的保证是一个独特的边界多边形的每个三角测量。什么是找到这个边界多边形的最好方法是什么？特别是，边缘必须相容次序和它必须支持的洞的可能性。（认为环面或环形形状 - 这是在GeoJSON前pressible）

解决方案

1. 创建在其中节点对应于德洛奈三角形的曲线图，并且其中有两个三角形之间的曲线边缘，当且仅当它们共享两个顶点

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三角的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！