我有一组不重叠的多边形。这些多边形可以共享节点、边，但严格来说不能重叠。
现在，我将使用约束德劳内三角剖分 (CDT) 技术对它们进行网格划分。我可以毫无问题地获得网格。
我的问题是，在网格之后，我想知道哪个网格元素属于哪个原始多边形。我目前的方法是计算每个网格元素的质心，并检查该质心属于哪个原始多边形。但我不喜欢这种方法，因为它的计算量很大。
有没有有效的方法来做到这一点（就 Big O 运行时而言）？我的项目涉及数以万计的多边形，我不希望速度减慢。
编辑：确保网格元素中的所有顶点共享一个公共面不起作用，因为在某些情况下所有顶点可以有多个公共面，如下所示（虚线形成一个网格元素，其顶点有 2 个公共面）：
我可以想到两个选项，都以某种方式提到：
维护点/顶点中的信息。请参阅其他相关问题。
以您的方式重新计算信息，将每个网格元素的质心定位在原始多边形中，但这可以通过使用 a 来优化spatial_sort，并在输入多边形中按顺序定位它们（使用先前的结果作为开始下一个点位置的提示）。
按以下方式创建一个新图 G(V,E)。对于每个网格，在 V 中创建一个节点。对于每个虚线边，在 E 中创建一个连接两个相应网格的边。不要将实体边缘映射到 E 中的边缘。
运行 ConnectedComponents(G)。
每个网格都将标有标签（与多边形一一对应。）
正如 Mikeb 所说，用多边形 id 标记所有原始顶点。
由于您想要多边形内部的那个，因此只需确保您只围绕多边形顺时针旋转，这样可以确保如果两个多边形的点重叠，您会得到一个朝向正确方向的多边形。
我希望这种方法保持接近 O(n)，其中 n 表示点的数量，因为每个三角形只能有一个或两个与所有三个点重叠的多边形。
用多边形ID（或多个，我猜，因为多边形可以共享顶点）标记每个原始顶点怎么样？然后，如果我正确理解 DT，您可以查看网格中给定三角形中的三个顶点，看看它们是否共享一个公共标签，如果是，则该网格来自标记的多边形。
也许您可以为每个多边形单独调用 CDT，并在每次调用后用它们的多边形标记三角形。