Блог

Существуют различные типы геометрии без многообразия, и одним из них является носовой тип. В этом случае несколько поверхностей соединены в одной точке и не имеют общего края.

Вы можете увидеть ниже пример этого конкретного типа:

Я пытаюсь придумать эффективный алгоритм для проверки того, связана ли точка с несколькими поверхностями. Для этого я создал быстрый прототип python для игры с информацией о смежности сетки, поэтому вы можете в основном выполнять типичные топологические запросы, такие как {вершины-gt;грани}, {ребра-gt;gt;грани}, {вершины-gt;gt;грани}.

 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) lt; 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}. Поэтому я знаю, что эта конкретная 2d-сетка имеет тип лука.

Первая идея, которая приходит мне в голову,-это придумать какой-нибудь алгоритм, способный извлекать поверхности, разделяемые из каждой точки сетки, таким образом, становится важным найти первую точку, разделяемую несколькими поверхностями, чтобы вы знали, что сетка не является многомерной дугообразной. С другой стороны, возможно, есть более разумные способы проверить, является ли сетка дугообразной или нет. Не могли бы вы, пожалуйста, предоставить реализацию/псевдокод/объяснение/теорию, если вы знаете такой случай?

Вы можете извлечь первичный граф (узлы-это вершины, ребра соединяют две вершины) и двойной граф (узлы-это грани, ребра соединяют две грани). Вычислите основные связанные компоненты и двойные связанные компоненты и проверьте, представляют ли они одно и то же разбиение ребер.