2

一个非常简单的问题：如何在 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号（在上面的例子中，一个三角形有 3 个顶点 [0,1,2] 和一个多边形有 4 个顶点 [1,2,3,4]

我需要计算信息：所有边的列表以及每条边的信息，哪些面包含该边。

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

更新
多边形是封闭的，即多边形[4, 0, 1, 5, 7]意味着有4个顶点和边是0-1, 1-5, 5-7, 7-0 实际上面是多边形的同义词。

4

1 回答 1

0

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

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。这是一种代码类型。它说您应该在可迭代的每个逗号之后放置一个空格，以便更容易阅读。

于 2013-02-08T11:27:53.807 回答