Блог

Учитывая триангуляцию Делоне набора точек, как я должен индексировать свою триангуляцию, чтобы выполнить быструю локализацию точки?

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

Это медленно. Есть идеи, как сделать этот поиск более эффективным?

Миссия выполнена, вот как я закончил это делать:

1) Проверьте, находится ли точка внутри треугольника, ограничивающего прямоугольник.

2) Назначьте точку как начало горизонтальной линии, заканчивающейся максимальной шириной.

3) Проверьте пересечения треугольников, найденных в (1), с линией из (2).

4) Если треугольник пересекается, проверьте, сколько раз горизонтальная линия пересекается с треугольником.

5) Если пересекается 1 раз, означает точку в треугольнике. Иначе, не в треугольнике.

Ссылка:

Быстрая генерация точек внутри триангулированных объектов, полученных по контурам поперечного сечения

Вот три подхода, которые вы могли бы использовать: от быстрых и практичных до теоретически надежных:

• Постройте регулярную сетку, в которой каждая ячейка содержит список треугольников, которые ее пересекают. Учитывая точку запроса, за постоянное время определите ячейку, которая ее содержит, затем сравните свою точку запроса только с теми треугольниками, которые есть в списке этой ячейки.

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

• Проведите горизонтальную линию вниз по всем треугольникам. Точки в ваших наборах точек соответствуют событиям. При каждом событии некоторые треугольники начинают пересекать линию розыгрыша, а другие треугольники перестают пересекать линию розыгрыша. Вы можете использовать неизменяемую (или постоянную) отсортированную структуру данных карты для эффективного представления этого. map<double, sweepstate> , где ключом является y-перехват линии розыгрыша в событии и sweepstate представляет собой отсортированный список пар отрезков (соответствующих левой и правой сторонам треугольников). Учитывая точку запроса, вы сначала используете ее значение y для поиска a sweepstate , а затем выполняете один тест удержания трапеции. (Две горизонтальные линии и два отрезка между ними образуют трапецию.)

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

Также может быть, что распределение ваших точек запроса допускает альтернативные / более простые подходы.

Решением является иерархическое дерево, т.Е. дендограмма или иерархический кластер. Например, используйте эвклидово расстояние: http://en.m.wikipedia.org/wiki/Hierarchical_clustering. Или вы можете использовать дерево метрик.