如何检测边是否在约束三角测量中的闭合曲线内？

How to detect if an edge is inside a closed curve in a constrained triangulation?

提问人：Makogan 提问时间：10/10/2023 更新时间：10/10/2023 访问量：38

问：

假设有一个受约束的 Delaunay 三角剖分，如下所示：

https://www.researchgate.net/figure/Results-of-three-steps-constrained-Delaunay-triangulation-in-a-simple-vague-region-a_fig8_225854833 enter image description here

我确切地知道如何处理 a 并得到 c。

但是，如果你有一个像 C 这样的形状，你怎么能检测边缘/面是否在其中一个紧密的轮廓内，以便你可以删除它呢？

算法 数学 几何 三角测量

评论

0赞 Gene 10/10/2023
如果边的中点在所有原始轮廓之外，则拒绝该边？扫描线算法应该非常有效地做到这一点。
0赞 Makogan 10/10/2023
即输入多段线上的 O（n），感觉这个问题在 O（1） 中是可以解决的。
0赞 n. m. could be an AI 10/10/2023
划定区域的等值线通常定向，使得该区域的内部位于等值线的左侧。然后，用一团点积确定哪个三角测量边缘在内部，哪个在外部是微不足道的。

答：

1赞 Sneftel 10/10/2023 #1

假设约束曲线是流形且定向的：对于每个约束边，从该边的下一条边 CCW 开始，按 CCW 顺序遍历共享该边的起始顶点的所有边。删除所有边，直到命中另一条受约束的边。

上一个：Python 2D 路径规划算法 - 动态窗口方法，机器人在达到目标之前失速

下一个：根据 JS 中提供的公式和输入值列表，查找或组合公式以获取变量