@ChymeNik

Как быстро сгруппировать набор точек (2500х2500) по ячейкам Вороного?

Есть построенная в прямоугольнике 2500х2500 диаграмма Вороного (с 500 ячейками)
Как теперь можно разделить все 2500х2500 точек между 500 ячейками (чтобы у каждой был массив с её точками)?
Есть ли более эффективный способ, чем простая проверка того, содержит ли полигон точку (и так для каждой точки)?
  • Вопрос задан
  • 224 просмотра
Пригласить эксперта
Ответы на вопрос 2
tsarevfs
@tsarevfs Куратор тега C++
C++ developer
Если нужно быстрее чем за линейное время, то есть относительно сложный путь. Диаграмма вороного двойственна с триангуляцией делоне. Если соединить центры смежных ячеек диаграммы - получим триангуляцию. Локализоваться в триангуляции делоне. можно не перебирая все вершины, а переходя к соседним треугольникам в нужном направлении (delaunay triangulation walk).
Зная в каком мы треугольнике, достаточно проверить расстояние до 3 его вершин которые совпадают с центрами ячеек вороного.
Что-то такое реализовано тут:
https://doc.cgal.org/latest/Voronoi_diagram_2/clas...
И тут:
https://doc.cgal.org/latest/Triangulation_2/classC...

Если вы пытаетесь локализовать узлы регулярной сетки, то логично в качестве начального треугольника брать результат соседней вычисленной локализации, так как точки идут подряд. В функции по второй ссылке такая возможность есть.

Может сработает более простой путь. Можно сначала разбить центры ячеек вороного по ячейкам регулярной(прямоугольной) сетки а затем искать ближайшую точку в соседних регулярных ячейках.
Ответ написан
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
По контрольным точкам диаграммы: которая из них ближайшая к очередной точке - в тот массив заносим.

Можно оптимизировать: все ячейки д.в. выпуклые, поэтому если две несоседние точки обе принадлежат одной ячейкке, то и все точки между этими двумя – тоже.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы