如何确定德劳内三角形是内部三角形还是外部三角形? [英] How to determine if a Delaunay triangle is internal or external?

问题描述

我正在编写一个程序，该程序需要实现中轴提取，其中 Delaunay 三角剖分是其中的一个步骤.外部中轴是不需要的，因此打算移除相应的外部三角形.幸运的是，我遇到了 .源代码这里.

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