Алгоритм проектирования - лучший способ нахождения наборов треугольников, которые разделяют вершину

Question

Я пытаюсь вычислить график Вороного из триангуляции Делоне, у меня есть данные триангуляции в виде коллекции вершин (красные круги на графике) и треугольники (синие линии на графике):

Я могу рассчитать график Вороного легко вершин, (пересечение красных линий), просто получая Окружность всех треугольников.

Однако мне нужно получить информацию о ячейке для каждого красного многоугольника. Чтобы сделать это, для каждой красной вершины мне нужно найти набор треугольников, которые разделяют ту же самую вершину. Таким образом, для кружком вершин, мне нужен зеленые треугольники:

Так что мой код выглядит следующим образом (C#):

foreach (Vertex3 vertex in DelaunayVertices) 
    { 
     VoronoiCell cell = new VoronoiCell(); 
     cell.Vertex = vertex; 

     //seach all triangles for the ones that match this. 
     foreach (Face3 face in DelaunayTriangles) 
     { 
      if (face.Vertices.Where(v => v.Equals(vertex)).Any()) 
      { 
       //shares vertices, add it's circumcenter as an edge vertex of the cell 
       cell.EdgeVertices.Add(face.Circumcenter); 
      } 
     } 
    } 

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

Единственное, что я должен найти соседние вершины или грани для каждого треугольника у меня есть это смежности, поэтому для оранжевый треугольник ниже, я знаю три зеленых треугольника:

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

Answer 1

Если вы готовы хранить вторичную вершинные к-треугольник структуру данных, вы можете сначала пройти список треугольника, толкая каждый треугольник в списки смежности, связанные с тремя вершинами:

for (all tria's ti) 
    for (all nodes ni in tria ti) 
     v2t[ni] <- ti 
    end for 
end for 

Это всего лишь O(n) развертки.

Answer 2

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