列出所有边的所有面

Question

一个非常简单的问题:如何在Python (或Cython)中高效地计算以下数量。

给出3D中的多边形列表(多边形)

有如下形式的多边形列表：

vertex = np.array([[0, 0, 0], [0, 0, 1], [0, 1, 0],[1, 0, 0],[0.5, 0.5, 0.5]], order = 'F').T
polygons = np.array([3, 0, 1, 2, 4, 1, 2, 3 ,4])

即多边形是一个一维数组，它包含形式为N，i1，i2，i3，i4，…，N是多边形中的顶点数，然后是顶点数组中顶点的id数(在上面的例子中，有一个三角形和一个顶点0,1,2，4点的多边形)。

我需要计算信息:一个所有边的列表，对于每一个边，面对的信息包含这个边。

我需要快速完成:顶点的数量可能很大。

更新

多边形是封闭的，即多边形[4, 0, 1, 5, 7]表示有4个顶点，边是0-1, 1-5, 5-7, 7-0，而面实际上是多边形的一个同义词。

Answer 1

不知道，如果这是最快的选择，很可能不是，但它的工作。我认为最慢的部分是edges.index((v, polygon[i + 1]))，我们必须找到这个边缘是否已经在列表中。顶点数组实际上并不需要，因为edge是一对顶点索引。我使用face_index作为多边形索引的引用，因为您没有编写face是什么。

vertex = [[0,0,0], [0,0,1], [0,1,0],[1,0,0],[0.5,0.5,0.5]]
polygons = [3,0,1,2,4,1,2,3,4]
_polygons = polygons
edges = []
faces = []
face_index = 0

while _polygons:
    polygon = _polygons[1:_polygons[0] + 1]
    polygon.append(polygon[0])
    _polygons = _polygons[_polygons[0] + 1:]

    for i, v in enumerate(polygon[0:-1]):
        if not (v, polygon[i + 1]) in edges:
            edges.append((v, polygon[i + 1]))
            faces.append([face_index, ])
        else:
            faces[edges.index((v, polygon[i + 1]))].append(face_index)
    face_index += 1

edges = map(lambda edge, face: (edge, face), edges, faces)

print edges

<<< [((0, 1), [0]), ((1, 2), [0, 1]), ((2, 0), [0]), ((2, 3), [1]), ((3, 4), [1]), ((4, 1), [1])]

您可以通过删除行polygon.append(polygon[0])并将多边形的第一个顶点手动添加到多边形中的顶点列表来使其更快，这应该不是问题。我的意思是把polygons = [3,0,1,2,4,1,2,3,4]变成polygons = [3,0,1,2,0,4,1,2,3,4,1]。

PS尝试使用PEP8。这是一种代码类型样式。它说你应该在迭代中的每个逗号后面放一个空格，这样读起来就更容易了。