我在规则三角形网格上随机选择了3个顶点
(V1, V2, V3)。对于这三个顶点，我已经计算出它们之间的测地线距离和路径（通过使用Dijkstra），并形成了一个三角形表面，如上图所示。 现在，我有了每个路径中的顶点，并且可以计算到给定顶点的测地线距离。位于三角形区域。我该怎么办？
#1 楼
有一种替代方法依赖于洪水填充。首先，将边缘数据排列成一个循环，在该循环中，边沿将形成逆时针循环。然后从循环上的任意点开始，并选择连接该点的边。使用出站边界边并将其与另一个出站边相交，如果它指向面法线方向，则该边将被包括在内，如果不丢弃的话。从该边缘继续直到您到达边界边缘，然后终止填充。继续在尚未访问的边界边缘顶点。评论
$ \ begingroup $
我对洪水填充算法不熟悉。您的解释对我来说似乎有点复杂。您能否提供一个体面的参考资料看一下？谢谢。
$ \ endgroup $
– mkocabas
17年7月19日在5:47
$ \ begingroup $
我通过阅读获得了解决方案。谢谢。
$ \ endgroup $
– mkocabas
17年7月19日在8:12
#2 楼
我已经评论过洪水填充的用法，以及它如何变得更好，因为它更灵活，但另一个可行的解决方案是scanline。 （之所以说是可能的，是因为它对您的几何形状有很多假设，但对于所示的特定集合和许多类似的集合而言，它都可以使用。）对于您的3点示例：从段v1，v2和v3所在的行。 （顶点位于v2的左上角）我们将其称为顶点v4。For every vertex pair a,b down v1,v4 and v1,v3
For every vertex from a to b
Mark as in the set
For every vertex pair a,b down v3,v2 and v4,v3
For every vertex from a to b
Mark as in the set
它被称为扫描线，因为（在上图中）您同时沿红色和绿色线下降，然后沿红色和蓝色下降行同时扫描行中的行。
如果有索引模式（通常是这种情况），此解决方案将非常快。否则，需要进行计算以确定该线上的相邻顶点。
有趣的是扫描线，重心测试（在三角形边界框中）和泛洪填充都是在3d渲染中绘制三角形的方式。 。
#3 楼
我认为您可以为表面上的每个点计算一些表面绑定的重心坐标，然后使用它们来检查三角形的内部或外部。我手头没有确切的算法但是我发现下面的这篇论文似乎确实可以处理这种坐标。
表面上的重心坐标
评论
$ \ begingroup $
感谢您提供答案和参考文件。我将尝试实施建议的方法。
$ \ endgroup $
– mkocabas
17年7月18日在12:55
评论
假设重心方法能够实现我认为的功能，那么使用大型方法会很慢。想象一个900万个顶点的集合，而所需集合中只有9个顶点。当v1，v2和v3为您提供所需的所有信息时，为什么要迭代整个集合。洪水填充答案将是最快的灵活解决方案。尽管不灵活，但如果可以假设像现在那样在几何图形中有线，则扫描线将是最快的方法。对于性能问题，您绝对正确。我想在大型网格中使用此方法，因此我正在寻找一种有效的方法。实际上，我对泛洪填充算法和扫描填充算法都不熟悉，我将介绍它们。谢谢。
带有图的洪水填充将从一个节点开始，如果满足边界条件但未访问，则访问每个相邻节点，将其标记为已访问，然后重复（递归）。变更：将路径上的每个节点标记为已访问，并从集合内的一个节点开始。然后只需使用访问检查作为边界条件。
感谢您的详细解释。我发现洪水填充算法更合理，但我想同时实施洪水填充和扫描线，然后比较性能。