多边形索引列表中的相邻多边形 [英] Neighbor Polygons from List of Polygon Indices

问题描述

我有一个类似于 this 形式的网格.最后有代表每个多边形的索引列表.我需要为每个多边形生成一个相邻多边形列表，想知道是否有人知道一种有效的算法来做到这一点?

I have a mesh in a form like this. with a list of indices representing each polygon at the end. I need to generate a list of neighboring polygons for each polygon, and was wondering if anyone knows of an efficient algorithm to do this?

想到的最简单的方法是对于每个多边形，检查每个其他多边形是否有两个匹配的索引 - 但这看起来涉及一些嵌套循环.我不介意使用它，性能在这里不是一个大问题，但是是的，我只是在寻找替代方案.

The simplest way that comes to mind is for each polygon, check if every other polygon has two matching indices - but this looks like it involves a few nested loops. I don't mind using this, performance isn't a huge issue here, but yeah I'm just scouting for alternatives.

对每个多边形的最大索引/顶点数没有任何限制，但为简单起见，让我们假设其为 3(三角形多边形).

There isnt any limitation on the max indices/vertices per polygon, but for simplicity's sake, lets just assume its 3 (so triangle polygons).

感谢您的帮助！:)

推荐答案

哎呀，XML 网格 :).

Ouch, XML meshes :).

我实际上很好看，我的第一个答案很懒惰.你可以写得更好(如上文所述)，而且没有那么复杂，我不会为此花 40 美元买一篇期刊文章.这是一个应该适合您的伪代码解决方案.

I actually had a good look at this, my first answer was pretty lazy. you can write better (as posted above), and it's not that complicated, I wouldn't fork out $40 for a journal article over this. Here's a pseudo-code solution which should work for you.

注意:当我说表时，我的意思是查找表".

Note: When I say table, I mean 'lookup table'.

假设每个三角形都有编号并由顶点 v1、v2、v3 组成，这些顶点是唯一编号的，可以使用

进行比较.运算符(因此我们可以获得唯一的键组合).

Assume each triangle is numbered and composed of vertices, v1, v2, v3, which are uniquely numbered and can be compared using the < operator (so we can obtain unique key-combinations).

我们需要两个查找表:

• 名为 edge_triangles 的边->(三角形列表)表.
• 名为triangle_edges 的三角形->(边列表)表.

一个表格告诉我们哪些三角形使用给定的边，另一个表格告诉我们一个给定的三角形由哪些边组成.我们按如下方式构建这些列表:

A table which tells us which triangles use a given edge, and another which tells us which edges a a given triangle is comprised of. We build these lists as follows:

for t = next triangle
    // Determine the ordering of vertices.
    min_vertex = min(t.v1, t.v2, t.v3);
    mid_vertex = median(p.v1, t.v2, t.v3);
    max_vertex = max(t.v1, t.v2, t.v3);

    // Register which edges this triangle uses.
    edge_triangles[min_vertex][mid_vertex].append(t);
    edge_triangles[mid_vertex][max_vertex].append(t);
    edge_triangles[min_vertex][max_vertex].append(t);

    // Set the edges that make up this triangle.
    triangle_edges[t].append({min_vertex, mid_vertex});
    triangle_edges[t].append({mid_vertex, max_vertex});
    triangle_edges[t].append({min_vertex, max_vertex});
for next t

使用这些列表，我们可以获取给定三角形中的边，将它们用作边表的键，并查看哪些多边形共享该边.因此，相邻的三角形.因此，对于三角形 t，我们可以执行以下操作:

Using these lists, we can take the edges in a given triangle, use these as the key into the edge table, and see which polygons share that edge. Thus, the adjacent triangles. So for a triangle t we could do the following:

adjacent = edge_faces[face_edges[t][0]];

这是相邻等于共享三角形 t 的第 0 条边的三角形列表"的伪代码，其中第 0 条只是第一条边.

which is pseudo-code for 'adjacent is equal to the list of triangles that share the 0th edge of the triangle t', where 0th is just the first.

我们使用 min、median 和 max 来确保对于相同的边没有不同的条目:例如 {v1, v2} 和 {v2, v1}，其中 v1 和 v2 是两个顶点.我们实际上可以忽略这一点并添加一个紧凑"步骤，在该步骤中，我们连接对应于边列表中不同条目但实际上对应于同一边的列表.

We use min, median and max to make sure that that we don't have different entries for identical edges: for example {v1, v2} and {v2, v1}, where v1 and v2 are two vertices. We could actually ignore this and add a 'compact' step, where we concatenate lists which correspond to different entries in our edge list but actually correspond to the same edge.

另一个可能的问题是，如果您有两条重合但不共享公共顶点的边.在这种情况下，您可以将任一边简化为参数方程，比较它们的重合度，然后形成一个查找表，该表告诉您对于给定的边，哪些边是重合的，因此映射:

One other possible problem with this is if you have two edges which are coincident but don't share common vertices. In this case, you could reduce either edge to a parametric equation, compare them for coincidence, and form a lookup table which tells you, for a given edge, which edges are coincident, so map:

• edge->(边列表)表，名为 edge_coincident_edges.

我们使用另一个查找表，因为我们无法连接 edge->faces 表.如果边 e1 和 e2 相邻，则考虑 e2 和 e3，但 e1 和 e3 不是.如果我们在 edge->face 列表中连接 e1、e2 和 e3 条目，你最终会得到一些非常不正确的数据.这可能比你想做的要多一些，但这是我今天早上必须解决的问题:)

We use yet another look-up table because we can't concatenate the edge->faces table. Cosider if edges e1 and e2 are adjacent, e2 and e3 are, but e1 and e3 aren't. if we concatenated the e1, e2 and e3 entries in the edge->face list, you'd end up with some wildly incorrect data. This a probably bit more than you want to do, but it's the problem I had to solve this morning :).

在每条边最多只能对应2个三角形的情况下，我们可以去掉传统意义上的可以追加的'list'，而使用大小为2的固定大小的数组.这样会减少您的内存开销并提高内存效率.所以我们的边缘表更类似于:

In the case where each edge can only correspond to at most 2 triangles, we can do away with the 'list' in the traditional sense that we can append, and use a fixed-size array of size 2. This will reduce your memory overhead and improve memory efficiency. so our edge table would be more akin to:

• 名为 edge_triangles 的边->(第一个三角形，第二个三角形)表.

无论如何，基本算法可以扩展到具有任意数量边的任意数量的多边形(不一定所有多边形之间都相同)，并且相对于三角形(或一般的多边形)的数量是 O(N) 时间案件).空间复杂度为 O(E + N)，其中 E 是边，N 是多边形的数量.查找时间应该接近 O(1)，假设您有良好的散列算法.

Anyway, the basic algorithm is extensible to any number of polygons with any number of edges (not necessarily the same between all polygons), and is O(N) time with respect to the number of triangles (or polygons in the general case). Space complexity is O(E + N) Where E is edges and N is the number of polygons. The look-up time should be close to O(1), assuming you have good hashing algorithms.

这篇关于多边形索引列表中的相邻多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！