检查哪个网格元素位于原始多边形内
我有一组不重叠的多边形。这些多边形可以共享节点、边，但严格不能重叠。
现在，我将使用约束 Delaunay 三角剖分 (CDT) 技术对它们进行网格划分。我可以毫无问题地获得网格。
我的问题是，在网格之后，我想知道哪个网格元素属于哪个原始多边形。我当前的方法是计算每个网格元素的质心，并检查该质心属于哪个原始多边形。但我不喜欢这种方法，因为它的计算量很大。
有没有有效的方法可以做到这一点（就 Big O 运行时而言）？我的项目涉及数以万计的多边形，我不希望速度减慢。
编辑：确保网格元素中的所有顶点共享一个公共面是行不通的，因为在某些情况下，所有顶点可以有多个公共面，如下所示（虚线形成一个网格元素，其顶点有 2 个公共面）：
I have a set of non-overlapping polygons. These polygons can share nodes, edges, but strictly no overlapping.
Now, I am going to mesh them using Constrainted Delaunay Triangulation (CDT) technique. I can get the mesh without problem.
My problem is, after the mesh, I want to know which mesh element belongs to which original polygon. MY current approach is to compute the centroid for each mesh element, and check which of the original polygon this centroid falls into. But I don't like this approach as it is very computationally intensive.
Is there any efficient ways to do this ( in terms of Big O the runtime)? My projects involve tens of thousands of polygons and I don't want the speed to slow down.
Edit: Make sure that all the vertices in a mesh element share a common face is not going to work, because there are cases where the all the vertices can have more than one common face, as below ( the dotted line forms a mesh element whose vertices have 2 common faces):
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我可以想到两个选项，两者都以某种方式提到：
维护点/顶点中的信息。 其他相关问题。
按照您的方式重新计算信息，在原始多边形中定位每个网格元素质心，但这可以通过使用
spatial_sort，并在您的输入多边形（使用之前的结果作为开始下一个点位置的提示）。I can think of two options, both somehow mentioned :
Maintain the information in your points/vertices. See this other related question.
Recompute the information the way you did, locating each mesh element centroid in the original polygon, but this can be optimized by using a
spatial_sort, and locating them sequentially in your input polygon (using the previous result as hint for starting the next point location).用多边形 id 标记每个原始顶点怎么样（我猜是几个，因为多边形可以共享顶点）。然后，如果我正确理解 DT，您可以查看网格中给定三角形中的三个顶点，看看它们是否共享公共标签，如果是，则该网格来自标记的多边形。
What about labeling each of your original vertices with a polygon id (or several, I guess, since polys can share vertices). Then, if I understand DT correctly, you can look at the three verts in a given triangle in the mesh and see if they share a common label, if so, that mesh came from the labeled polygon.
正如 Mikeb 所说，用多边形 id 标记所有原始顶点。
由于您想要多边形内部的点，因此只需确保仅绕多边形顺时针旋转，这可以确保如果两个多边形的点重叠，您会得到面向正确方向的点。
我希望这种方法保持接近 O(n)，其中 n 表示点数，因为每个三角形只能有一个或两个与所有三个点重叠的多边形。
As Mikeb says label all your original vertices with a polygon id.
Since you want the one that's inside the polygon, just make sure you only go clockwise around the polygons, this makes sure that if the points overlap for two polygons you get the one facing the correct direction.
I would expect this approach to remain close to O(n) where n represents number of points as each triangle can at only have one or two polygons that overlap all three points.
按以下方式创建一个新图 G(V,E)。对于每个网格，在 V 中创建一个节点。对于每个虚线边，在 E 中创建一条连接两个相应网格的边。不要将实体边映射到 E 中的边。
运行 ConnectedComponents(G)。
每个网格都会标有一个标签（与多边形一一对应。）
Create a new graph G(V,E) in the following way. For every mesh create a node in V. For every dashed edge create an edge in E that connects the two corresponding meshes. Don't map solid edges into edges in E.
Run ConnectedComponents(G).
Every mesh will be labeled with a label (with 1-to-1 correspondence to polygons.)
也许您可以为每个多边形单独调用 CDT，并在每次调用后用它们的多边形标记三角形。
Maybe you can call CDT separately for each polygon, and label the triangles with their polygon after each call.