logo标签列表

如何确定Delaunay三角形是内部的还是外部的？

algorithmgeometrycomputational-geometrymedial-axis
11

我正在编写一个程序，需要实现中轴线提取，其中Delaunay三角剖分是其中的一步。外部中轴线是不需要的，因此相应的外部三角形将被删除。幸运的是我发现了一个页面，里面有很多图表，也有一种根据“折线周长”确定内部和外部Delaunay三角形的方法的提示，但只是一个提示，没有详细的解释。有人知道该算法吗？

编辑：我忘记提到最初的点是从封闭多边形的边界采样的，我的意图是确定每个Delaunay三角形是否在多边形内部。

你的意思是这些点在多边形的周长上，还是被（但不一定在）多边形所包围？无论哪种情况，现在你是否遇到了一个问题，即三角形可能与多边形的边界重叠（使其既是内部的又是外部的）？暂时忽略这种情况，我们可以使用点定位来找到完全内部和完全外部的三角形，假设我们已经有了多边形的梯形分解，则时间复杂度为O(t*nlogn)。对于朴素方法，检查重叠会导致O(t*n)的运行时间。不过，可能有更好的方法。 - Niki Yoshiuchi
4个回答
14

此解决方案假设您有一个数据结构，使用“虚拟无限Delaunay顶点”代表Delaunay三角剖分，就像CGAL所做的那样(在这里查看详细信息)。

思路是找到边界Delaunay边：连接两个连续采样点的边；然后通过Delaunay三角剖分“泛洪”，以对Delaunay面进行分类。人们知道无限顶点是外部的，因此只要不越过边界边，就可以将其邻居(和邻居的邻居等)分类为外部。如果到达边界边，则可以简单地将相邻的三角形标记为内部，并继续类似地进行。

输入: 一组紧密采样封闭形状的边界点，甚至可以包含空洞
输出: 形状内部的Voronoi图(形状中心轴的近似值)

  1. 计算您的点的Delaunay三角剖分
  2. 标记连接两个连续样本点的Delaunay边缘。 (查看此论文的第4-5页，了解如何通过每个Delaunay边缘上的局部测试完成此操作)
  3. 将所有无限Delaunay面分类为外部并将它们推入队列 Q.
  4. 当Q不为空时
    1. Delaunay面 f = 从 Q中弹出
    2. 对于每个未分类的相邻三角形 t
      • 如果由t和f共享的Delaunay边缘已经被标记，则将t分类为与f相反的类型
      • 否则，将t分类为与f相同的类型
      • 将t推到Q中
  5. 对于每个Delaunay边缘 e
    • 如果两个相邻的Delaunay三角形d1、d2都被分类为内部，则输出连接d1和d2的外心的线段。
对于这样的输入
sample points
可以计算出以下中轴近似值： medial axis 您可以使用免费的Windows二进制文件Mesecina来查看这个中轴线近似值在实践中的表现。源代码在这里。
1
论文的链接已经过期。 - lalitm
2
你是否考虑过使用一种不会创建外部三角形的不同三角化方法？我曾经上过一门课，花费了大量时间讨论多边形三角化的理论方面。也许浏览一下该课程网站会给你一些启示？ http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html#triangulation 编辑：实际上，我又想到了另一件事。如果你已经有了要三角化的多边形，你可以使用格林定理。格林定理使用多边形的周长来计算其面积！更重要的是，在这种情况下，您可以通过查看面积的符号来确定一个点在一条线的哪一侧或另一侧。在多边形上，格林定理变成了一个简单的减法问题。因此，取任何一个你知道在多边形内部的点，并计算它与多边形每条边的面积。这告诉你你的点需要在每条直线的哪一侧。现在只需取每个三角形内部的一个点并做同样的操作。如果任何符号不正确，则说明你有一个外部三角形。（注意：根据你的多边形的形状，这可能实际上不起作用。它应该对凸多边形很好用，但是凹性可能会引入额外的复杂性。）
0
也许我在这里做出了太多的假设，但听起来你有一个由一堆点组成的多边形，并且正在三角化这些点。然后，您想要丢弃所有落在多边形外部的三角形，对吗？
为什么不只是三角化多边形（使用单调分解或类似的东西），以便您永远不会创建任何外部三角形？ 我想这可能会增加运行时间（首先以O（nlogn）时间进行三角化，然后以O（n ^ 2）时间创建Delaunay三角剖分），但可能有更快的方法。
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接