python - 检测弓形非流形几何的算法

问题描述

有不同类型的非流形几何，其中一种是弓型。在这种情况下，多个曲面在一个点连接并且不共享边。

您可以在下面看到此特定类型的示例：

我正在尝试提出一种有效的算法来检查一个点是否连接到多个表面。为了做到这一点，我创建了一个快速的 Python 原型来处理网格邻接信息的构建位置，因此您基本上可以进行典型的拓扑查询，例如 {vertices->faces}、{edges->faces}、{顶点->面}。

class Triangle:
    def __init__(self, a, b, c, label):
        self.a = a
        self.b = b
        self.c = c
        self.label = label
        self.adjacent_triangles = []

    def __repr__(self):
        return f"{self.label}"


class Vertex:
    def __init__(self, x, y, label):
        self.x = x
        self.y = y
        self.label = label
        self.adjacent_triangles = set()

    def __repr__(self):
        return f"{self.label} - {self.adjacent_triangles}"


class Edge:
    def __init__(self, a, b):
        self.a = a
        self.b = b
        self.adjacent_triangles = []

    def __repr__(self):
        return f"{self.__dict__}"


class TriMesh:
    def __init__(self, vertices, triangles):
        edges = {}

        def process_edge(a, b, triangle):
            vertex_index_a = min(a, b)
            vertex_index_b = max(a, b)
            key = f"{vertex_index_a}_{vertex_index_b}"

            if key in edges:
                edge = edges[key]
            else:
                edge = Edge(vertices[vertex_index_a], vertices[vertex_index_b])
                edges[key] = edge

            edge.adjacent_triangles.append(triangle)

        for triangle in triangles:
            process_edge(triangle.a, triangle.b, triangle)
            process_edge(triangle.b, triangle.c, triangle)
            process_edge(triangle.c, triangle.a, triangle)

        for key in edges:
            edge = edges[key]
            f0 = edge.adjacent_triangles[0]
            edge.a.adjacent_triangles.add(f0)
            edge.b.adjacent_triangles.add(f0)

            if len(edge.adjacent_triangles) < 2:
                continue

            f1 = edge.adjacent_triangles[1]
            edge.a.adjacent_triangles.add(f1)
            edge.b.adjacent_triangles.add(f1)
            f0.adjacent_triangles.append(f1)
            f1.adjacent_triangles.append(f0)

        self.vertices = vertices
        self.triangles = triangles
        self.edges = edges


if __name__ == "__main__":
    #     4---5   6   7
    #     |\t1|  /|\
    #     | \ | / | \
    #     |t0\|/t2|t3\
    #     0---1---2---3
    v = [
        Vertex(0, 0, "0"),
        Vertex(1, 0, "1"),
        Vertex(2, 0, "2"),
        Vertex(3, 0, "3"),
        Vertex(0, 1, "4"),
        Vertex(1, 1, "5"),
        Vertex(2, 1, "6"),
        Vertex(3, 1, "7"),
    ]
    t = [
        Triangle(0, 1, 4, "t0"),
        Triangle(1, 5, 4, "t1"),
        Triangle(1, 2, 6, "t2"),
        Triangle(2, 3, 6, "t3"),
    ]

    m = TriMesh(vertices=v, triangles=t)

    for v in m.vertices:
        print(v)

检测多个表面是否连接到一个点的有效算法是什么？例如，在上面您可以看到顶点1由 2 个曲面共享，S1={t0,t1} & S2={t2}。所以我知道特定的二维网格是弓形的。

我想到的第一个想法是提出一些算法，该算法能够提取从网格的每个点共享的表面，这样就可以找到多个表面共享的第一个点，这样你就知道网格是非歧管弓型。另一方面，也许有更聪明的方法来检查网格是否是弓形的。如果您知道这种情况，您能否提供一个实现/伪代码/解释/理论？

标签： pythonalgorithm3dmeshmanifold

python - 检测弓形非流形几何的算法

问题描述

解决方案

推荐阅读