如何判断德劳内三角形是内三角形还是外三角形？
我正在编写一个程序，需要实现中轴提取，其中 Delaunay 三角测量是其中的一个步骤。 外部中轴是不需要的，因此相应的外部三角形应被删除。 幸运的是，我发现了一个页面用了很多图，还提示了一种确定内、外Delaunay三角形的方法（“基于折线周长”），但只是提示，没有详细解释。 有人知道算法吗？
编辑：我忘记提到初始点是从闭合多边形的边界采样的，我的目的是确定每个 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
此解决方案假设您有一个数据结构，使用“虚拟无限 Delaunay 顶点”表示 Delaunay 三角剖分，方式为 CGAL 是吗（在此处查看详细信息）。
其思想是找到边界Delaunay边：连接两个连续样本点的边； 然后通过Delaunay三角剖分“泛洪”，对Delaunay面进行分类。 人们知道无限顶点是外部的，因此只要不跨越边界边，就可以将其邻居（以及邻居的邻居等）分类为外部。 如果到达边界边缘，则可以简单地将相邻三角形标记为内部并以类似方式继续。
输入：对封闭形状边界进行密集采样的点集，甚至可以包含孔
输出：形状内部的 Voronoi 图（形状中轴的近似值）
将t分类为f
的反义词
对于这样的输入
可以计算以下中轴近似值：
您可以使用免费窗口查看该中轴近似在实践中的表现Mesecina 的二进制文件。 源代码此处。
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)
classify t as the opposite of f
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.
您是否考虑过使用不创建外部三角形的不同形式的三角测量？ 我曾经上过一门课程，花了很多时间讨论多边形三角剖分的理论方面。 也许浏览一下课程网站会给您一些见解？ http://cgm.cs.mcgill.ca/~ godfried/teaching/cg-web.html#triangulation
编辑：实际上，我只是想到了别的东西。 如果您已经有了要进行三角测量的多边形，则可以使用格林定理。 格林定理使用多边形的周长来计算其面积！ 更重要的是，在这种情况下，您可以通过查看面积符号来确定点是否位于直线的一侧或另一侧。 对于多边形，格林定理可以解决一个简单的减法问题。 因此，取您知道的多边形内部的任何点，并计算多边形每条边的面积。 这告诉您您的点需要位于每条线的哪一侧。 现在只需在每个三角形内取一个点并执行相同的操作。 如果任何一个符号是错误的，那么就有一个外三角形。 （注意：根据多边形的形状，这实际上可能不起作用。它对于凸多边形应该可以很好地工作，但凹面可能会带来额外的复杂性。）
Have you considered using a different form of triangulation that doesn't create external triangles? I once took a course that spent a great deal of time discussing the theoretical aspects of polygon triangulation. Maybe skimming through the course site will give you some insight? http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html#triangulation
Edit: Actually, I just thought of something else. If you already have the polygon that you are trying to triangulate, you could use Green's theorem. Green's theorem uses a polygon's perimeter to compute its area! More importantly, in this case, you can determine whether a point is on one side of a line, or another, by looking at the sign of area. On polygons, Green's theorem works out to a simple subtraction problem. So take any point that you KNOW is inside the polygon, and compute the area against each edge of the polygon. This tells you on which side of each line your point needs to be. Now simply take a point inside each triangle and do the same thing. If any of the signs are wrong, then you have an external triangle. (Note: depending on the shape of your polygon this might not actually work. It should work fine for convex polygons, but concavities could introduce additional complications.)
也许我在这里做了太多假设，但听起来你有一个由一堆点组成的多边形，并且你正在对这些点进行三角测量。 然后你想丢弃所有落在多边形之外的三角形，对吧？
为什么不直接对多边形进行三角剖分（使用单调分解或类似的方法），这样就永远不会创建任何外部三角形？ 我想这可能会增加运行时间（首先在 O(nlogn) 时间内进行三角剖分，然后在 O(n^2) 时间内创建 delaunay 三角剖分），但可能有更快的方法。
Perhaps I'm making too many assumptions here, but it sounds like you have a polygon that consists of a bunch of points, and that you are triangulating those points. You then want to discard all the triangles that fall outside of the polygon, right?
Why not just triangulate the polygon (using monotone decomposition or something similar) so that you never create any external triangles? I suppose this might increase the running time (triangulate first in O(nlogn) time and then create a delaunay triangulation in O(n^2) time) but there might be a faster way of doing it.
他们提出的算法看起来有点问题，正如他们在一张图中所示，这可能是谷歌学术搜索中似乎没有任何有用引用的原因。
在非-凸多边形表明它并不总是恢复实际的三角测量。 http://www.cc.kyoto-su.ac.jp/~atsushi/Jun/Topics/Teddy/images/example2_2.jpg
The algorithm that they present looks like it is a bit broken, as they show in one of their figures, and this may be the reason that there don't appear to be any useful citations in Google Scholar.
Using their proposed algorithm on a non-convex polygon shows that it does not always recover an actual triangulation. http://www.cc.kyoto-su.ac.jp/~atsushi/Jun/Topics/Teddy/images/example2_2.jpg