我很确定这是一个常见的问题，但无论我如何改写它，我都无法在互联网上找到任何答案。
我正在制作一个用户界面，供用户通过选择多个顶点来选择网格内的区域。
更准确地说，给定一个三角形网格和一组顶点(它是网格顶点的子集)，我想得到被顶点子集包围的所有面。
我查找了一些算法，例如多边形中的点，Dijkstra的算法等，但它们似乎没有帮助。
非常感谢。
首先，您需要在表示轮廓的网格上嵌入一条闭合折线。有了这个轮廓后，你可以填充它的内部以获得相应的面。
等高线
有多种方法可以获取等高线。一种方法是使用路径查找算法(如 A*)来查找选择集中两个连续顶点之间的最短路径(即(v0 -> v1), (v1 -> v2) ... (vn -> v0))。这将为您提供一条表示为网格的有向边的折线。
根据用户选择的行为程度，您可能需要稍微清理一下轮廓。例如，如果轮廓包含沿两个方向遍历的边(例如v1 -> v2 -> v3 -> v2 -> v4 -> ...)，你可以杀死这个边缘对。如果您有自相交点，则需要进行类似的清理。
填充内部
一旦有了定向等高线，就可以通过宽度优先遍历来填充其内部。这个想法是从轮廓边缘开始，然后迭代添加入射面。基本算法可以概述如下：
Input:
E: directed edges of the contour
O <- empty list of faces to examine
V <- empty list of visited faces
// Initialization
for every e in E:
calculate the face left of e (-> f)
add f to O
add f to V
// Do BFS
while O is not empty:
take the first element out of O (-> f)
for all faces g adjacent to f and not in V:
add g to O
add g to V
完成此过程后，所选面将以V表示。但是，有一个关键部分：
calculate the face left of e
首先，左边和右边的概念应该从网格本身中清楚。面的顶点通常按逆时针或顺时针顺序(面缠绕顺序)排序。因此，每个非边界边{v1, v2}都存在于两个面中：一次是(v1 -> v2)，一次是(v2 -> v1)。根据缠绕顺序，可以选择包含正确方向边的面。然后，如果您知道轮廓的缠绕顺序，这就是您需要做的。也就是说，如果您的轮廓始终是顺时针的，并且您的网格面始终是顺时针顺序，那么您就完成了。
如果轮廓可以在任一方向上，事情就会变得有点复杂。然后，不清楚用户想要标记哪个部分(考虑一个轮廓为赤道的球体)。有两个简单的选项：
- 使用较小的区域
- 让用户在目标区域内选择一个点并使用该点。
对于这两个选项，您需要从轮廓在两个方向上执行 BFS(准确地说，它们是两个单独的 BFS)。出于性能原因，最好同时执行这两项操作。然后，只要其中一个区域用完O中的开放面(选项 1，此区域将是较小的区域)，或者遇到附加点(选项 2，仅针对此区域继续 BFS)，就可以中止。
为了有效地完成此BFS，您需要一种方法将边缘映射到网格上的相应面和/或邻域数据结构。如果要使用后者，则可能需要考虑半边数据结构