使用网格中的顶点（2D 和 3D）查找边缘的算法
我有一个网格，具有某些类型的元素（例如三角形、四边形）。对于每个元素，我知道它的所有顶点，即三角形 2D 元素将有 3 个顶点 v1、v2 和 v3，其 x、y、z 坐标已知。
问题 1
我正在寻找一种可以返回所有边的算法...在本例中：
edge(v1, v2)、edge(v1, v3)、edge(v2, v3)。根据每个元素有多少个顶点，算法应该有效地确定边缘。
问题2
我使用的是C++，那么，存储上述算法返回的边信息的最有效方法是什么？例如，我感兴趣的是一个元组（v1，v2），我想将其用于一些计算，然后忘记它。
谢谢
I have a a mesh, with certain types of elements (e.g. triangular, tetra). For each element I know all its vertices i.e. a triangular 2D element will have 3 vertices v1, v2 and v3 whose x,y,z coords are known.
Question 1
I am looking for an algorithm that will return all the edges... in this case:
edge(v1, v2), edge(v1, v3) , edge(v2, v3). Based on how many vertices each element has , the algorithm should efficiently determine the edges.
Question 2
I am using C++, so, what will be the most efficient way to store the information about the edges returned by the above algorithm? Example, all I am interested in is a tuple (v1, v2) that I want to use for some computation and then forget about it.
Thank you
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以使用半边数据结构。
基本上，您的网格还有一个边列表，并且每个方向上的每对顶点都有一个边结构。这意味着如果有顶点 A 和 B，那么某处存储有两个边结构，一个用于 A->B，一个用于 B->A。每条边都有 3 个指针，一个称为前一个，一个称为下一个，一个称为孪生。跟随下一个和上一个指针将引导您绕过网格中三角形或多边形的边缘。调用 twin 会将您带到相邻多边形或三角形中的相邻边。 （看图片中的箭头）这是我所知道的最有用和最详细的边缘数据结构。我用它通过创建新边缘和更新指针来平滑网格。顺便说一句，每条边还应该指向一个顶点，以便它知道它在空间中的位置。
You can use the half-edge data structure.
Basically your mesh also has a list of edges, and there is one edge structure per pair of verts in each direction. That means if you have verts A and B then there are two edge structures stored somewhere, one for A->B and one for B->A. Each edge has 3 pointers, one called previous, one called next and one called twin. Following the next and previous pointers walks you around the edges of the triangle or polygon in the mesh. Calling twin takes you to the adjacent edge in the adjacent polygon or triangle. (Look at the arrows int he picture) This is the most useful and verbose edge data structure I know of. I've used it to smooth meshes by creating new edges and updating the pointers. Btw, each edge should also point to a vertex so it knows where it is in space.
您的问题实际上分为三个部分，而不是两个部分：
您必须提出其他问题才能找到合适的答案。
应该使用什么数据结构来表示网格？
您需要处理哪些元素类型？
如果您只需要处理多边形（闭环）和单纯形（每个节点都连接到元素中的每个其他节点，例如四面体），那么有序节点列表就足够了，因为可以从节点列表中隐含边。另一方面，如果您需要处理六面体、棱柱或一般多面体等元素类型，那么您需要有关元素拓扑的更多信息。简单的边缘映射数组通常就足够了。它只是元素节点列表中索引的数组[][2]，它告诉您如何连接给定元素类型的点。
Chris 描述的半边结构仅适用于 2D。在 3D 中，每条边可以附加任意数量的元素，而不仅仅是两个。半边表示有一个 3D 扩展，我认为它被称为风车结构。
如果您必须支持任意元素类型，我更喜欢更完整的数据结构来表示元素拓扑。常见的选择是使用边和共边。每对连接的节点都有一个边结构，并且元素中该边的每次使用都有一个共边。它类似于风车方法，但更明确一些。
我应该使用什么算法从元素中提取边缘？
速度或内存有多重要？结果是否应该为每个元素包含每条边一次，还是无论有多少元素使用它都只包含一次？结果中边的顺序重要吗？每条边的节点顺序重要吗？
很难想出一种适用于任意元素类型且仅访问每个边一次的算法。为了确保每个边只出现一次，您可以过滤结果，或者您可以有点黑客并在每个边上保留“已访问”位以确保您不会将其粘贴在结果中两次。
我应该如何表示结果？
我使用结果的方式有何重要意义？
如果您要在计算密集型计算中使用结果，那么大的坐标数组可能是最好的选择。您不想在计算过程中一遍又一遍地重新获取节点坐标。但是，如果您要过滤结果以删除重复的边，则比较坐标（节点对有 6 个双精度）并不是可行的方法。如果要过滤，请首先生成指向边缘结构的指针列表，然后过滤掉重复项，然后生成坐标列表。您也可以对节点对使用这种方法，但随后您必须针对每条边的两种可能的节点顺序进行过滤，从而使过滤所需的时间加倍。
如果内存比性能更重要，则边缘指针列表也是可行的方法。但是，您无需将边列表转换为坐标列表，而是在计算过程中查找坐标。这样获取节点坐标会比较慢，但可以避免创建大量坐标列表 - 每个边存储一个指针，而不是每个边存储 6 个双精度指针。
许多网格应用程序将所有坐标存储在一个大的全局数组中，每个节点都有一个数组索引。如果是这种情况，不要将边缘列表转换为坐标数组，而是将其转换为全局坐标数组中的索引列表。性能与局部坐标数组的差异应该不会太大，但没有内存和填充开销。
There are really three parts to your question, not two:
You have to ask additional questions to find appropriate answers.
What data structures should be used to represent the mesh?
What element types do you need to handle?
If you only need to handle polygons (closed loops) and simplicials (every node is connected to every other node in the element, such as a tetrahedron), then an ordered node list is sufficient because edges can be implied from the list of nodes. If, on the other hand, you need to handle element types such as hexahedra, prisms, or general polyhedra then you need more information about the element topology. A simple array of edge mappings is often sufficient. It's just an array[][2] of indices into the element's list of nodes which tells you how to connect the dots for a given element type.
The half-edge structure described by Chris is a good choice for 2D only. In 3D there can be an arbitrary number of elements attached to each edge, not just two. There is a 3D extension to the half-edge representation that I think is called a pinwheel structure.
If you've got to support arbitrary element types, I prefer a more complete data structure to represent element topology. A common option is to use edges and co-edges. There is an edge structure for each pair of connected nodes, and a co-edge for each use of that edge in an element. It's similar to the pinwheel approach, but a bit more explicit.
What algorithm should I use to extract edges from the elements?
How important is speed or memory? Should the result include each edge once per element, or only once no matter how many elements are using it? Does the order of edges in the result matter? Does the order of the nodes of each edge matter?
It's pretty hard to come up with an algorithm for arbitrary element types that will only visit each edge once. To ensure each edge only appears once, you can either filter the result, or you can be a bit hackish and keep a "visited" bit on each edge to ensure you don't stick it in the result twice.
How should I represent the results?
What matters about the way I will use the result?
If you're going to be using the result in a compute-intensive calculation, a big array of coordinates may be the best option. You don't want to re-fetch the node coordinates over and over during your computation. However, if you're filtering the results to remove duplicate edges, comparing coordinates (6 doubles for a node pair) is not the way to go. If you are filtering, generate a list of pointers to edge structures first, then filter out duplicates, and then generate your list of coordinates. You could use this approach with node pairs too, but then you have to filter against both possible node orders per edge, doubling the amount of time it takes to filter.
A list of edge pointers is also the way to go if memory matters more than performance. Instead of converting your edge list to a coordinate list, however, you look up coordinates during your calculation. Getting node coordinates is slower that way, but you avoid making a massive list of coordinates - you store a single pointer per edge instead of 6 doubles per edge.
Many mesh applications store all coordinates in a big global array, with each node having an index into the array. If this is the case, instead of converting your edge list to a coordinate array, convert it to a list of indices into the global coordinate array. Performance should not be much off from a local coordinate array, but without the memory and population overhead.
我没有适合你的算法，但我可以告诉你去哪里寻找。
“点集三角测量” 就是您要寻找的内容。
这里有一些开源库可以为您完成此操作（了解算法代码）：
I don't have algorithms for you, but I can tell you where to look.
"Point Set Triangulation" is what you are looking for.
Here are some open source libraries which will do this for you (grok the code for algorithms):