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

问题描述

我有一个此形式的网格. 索引列表表示末尾的每个多边形.我需要为每个多边形生成一个相邻多边形的列表，想知道是否有人知道一种有效的算法来做到这一点?

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

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

感谢您的帮助！ :)

解决方案

好吧，XML网格:).

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

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

假设每个三角形都有编号，并且由顶点v1，v2，v3组成，这些顶点是唯一编号的，可以使用<运算符(这样我们就可以获得唯一的键组合).

我们需要两个查询表:

• 称为edge_triangles的edge->(三角形列表)表.
• 一个称为triangle_edges的triangle->(边列表)表.

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

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，我们可以执行以下操作:

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

是"adjcent等于共享三角形t的第0个边的三角形的列表"的伪代码，其中0th只是第一个.

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

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

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

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

在每个边缘最多只能对应2个三角形的情况下，我们可以取消传统的可以附加的列表"，而使用大小为2的固定大小的数组.这将减少您的内存开销并提高了内存效率.因此我们的边桌将更类似于:

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

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

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.

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

Thanks for any help! :)

解决方案

Ouch, XML meshes :).

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'.

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).

We need two look-up tables:

• An edge->(triangle list) table called edge_triangles.
• A triangle->(edges list) table called 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

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]];

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.

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->(edges list) table called edge_coincident_edges.

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 :).

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:

• An edge->(first triangle, second triangle) table called edge_triangles.

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屋！