有不同类型的非流形几何，其中一种是弓型。在这种情况下，多个曲面在一个点连接并且不共享边。
您可以在下面看到此特定类型的示例：
我正在尝试提出一种有效的算法来检查一个点是否连接到多个表面。为了做到这一点，我创建了一个快速的 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}。所以我知道特定的二维网格是弓形的。
我想到的第一个想法是提出一些算法，该算法能够提取从网格的每个点共享的表面，这样就可以找到多个表面共享的第一个点，这样你就知道网格是非歧管弓型。另一方面，也许有更聪明的方法来检查网格是否是弓形的。如果您知道这种情况，您能否提供一个实现/伪代码/解释/理论？