如何确定是否一个德洛奈三角形是内部或外部的？ [英] How to determine if a Delaunay triangle is internal or external?

问题描述

我写一个程序所要求的实施中轴提取，其中Delaunay三角是一个循序渐进的。外部中轴是不希望的，以便在相应的外部三角形旨在被除去。幸运的是，我来到页有很多图表，也有方法的提示，以确定内部和外部德洛奈三角形（基于虚线边界），但它只是一个提示，没有详细解释。任何人都知道的算法？

编辑：我忘了提初始点从一个封闭的多边形的边界采样，我的目的是要确定每个德洛奈三角形是否在多边形内

解决方案

该解决方案假定您有重新presents使用虚拟无限德洛奈顶点的方式，Delaunay三角的数据结构的 CGAL 做它（<一href="http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Section_25.2"相对=nofollow>详情请参阅这里）。

的想法是找到边界德洛奈边：连接两个连续的采样点的边缘;然后洪水通过Delaunay三角分类德劳内面。人知道无限的顶点是外部的所以可以邻国（和邻居的邻居等）外，只要归类为一个不跨越边界边。如果一个人到达边界边可以简单地标记邻居三角形内，继续与此类似。

输入：设定点封闭形状的边界密集采样，甚至可以包含孔
的 输出：在形状的内部Voronoi图（该形状的中轴近似）

1. 计算您的积分的德劳内三角
2. 标记的德劳内边缘而连接两个连续的采样点。 （见本文4-5页你如何能做到这对每一个德劳内缘本地测试）
3. 分类所有无限德洛奈面临的外面，他们推到一个队列的问：的
4. 在问：的是不为空
   1. 在德劳内面f =从弹出的问：的
   2. 对于每一个生产型的邻居三角形的F的 T 的
      • 如果德劳内边缘通过的 T 的共享和 F 的标记， 分类的 T 的是相反的 F 的
      • 在其他分类的 T 的同样喜欢的 F 的
      • 推的 T 的到的问：的
5. 对于每一个德劳内边缘的电子的
   • 如果在两个相邻的德劳内三角形的 D1 的 D2 的都被归类为室内，输出连接的 D1 的外心段和 D2 的

对于这样
输入
下面中轴近似可以计算：

您可以检查出使用的 Mesecina 。这里来源$ C ​​$ C 。

I am writing a program that requires a implementation of Medial Axis extraction, of which Delaunay triangulation is a step. External medial axis is unwanted so the corresponding external triangles are intended to be removed. Luckily I came upon a page with a lot of diagrams, also a hint of a method to determine internal and external Delaunay triangles ("based on the broken line perimeter"), but it's just a hint, without detailed explanation. Anybody know the algorithm?

EDIT: I forgot mentioning the initial points are sampled from the boundary of a closed polygon, my intention is to determine whether each Delaunay triangle is inside the polygon.

解决方案

This solution assumes that you have a data structure that represents the Delaunay triangulation using a "virtual infinite Delaunay vertex" the way CGAL does it (see details here).

The idea is to find the boundary Delaunay edges: the edges connecting two consecutive sample points; and then "flood" through the Delaunay triangulation to classify the Delaunay faces. One knows that the infinite vertex is exterior so one can classify its neighbors (and neighbors' neighbors, etc.) as exterior as long as one does not cross boundary edges. If one reaches a boundary edge one can simply mark the neighbor triangle as interior and continue similarly.

Input: set of points densely sampling of the boundary of a closed shape, which can even contain holes
Output: Voronoi diagram in the interior of the shape (approximation of the medial axis of the shape)

1. Compute the Delaunay triangulation of your points
2. Mark the Delaunay edges which connect two consecutive sample points. (See page 4-5 of this paper how you can do this with a local test on every Delaunay edge)
3. Classify all infinite Delaunay faces as OUTSIDE and push them to a queue Q.
4. While Q is not empty
   1. Delaunay face f = Pop from Q
   2. For every unclassified neighbor triangle t of f
      • if the Delaunay edge shared by t and f is marked, classify t as the opposite of f
      • else classify t the same like f
      • push t to Q

5. For every Delaunay edge e
   • if the two neighbor Delaunay triangles d1, d2 are both classified as INTERIOR, output the segment connecting the circumcenter of d1 and d2.

For an input like this

the following medial axis approximation can be computed:

You can check out how this medial axis approximation behaves in practice using the free windows binary of Mesecina. Source code here.

这篇关于如何确定是否一个德洛奈三角形是内部或外部的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！