Найдите треугольник, содержащий произвольную точку в треугольной поверхности Делоне

Я хочу сделать линейную интерполяцию нерегулярно сэмплированной функции z(x,y) на основе триангуляции Delaunay. Скажем, у меня есть холм, для которого я получил триангуляцию Делоне:

Я знаю высоту z на каждой из треугольных вершин (выборок). Я хочу высоту z в произвольной точке (x,y).

Как определить, какой треугольник содержит точку (x,y)? Как только я это знаю, я предполагаю, что довольно сложно интерполировать между тремя вершинами треугольника.
Знаете ли вы о готовой реализации этого? Возможно, с включенным битом интерполяции? Я уверен, что там должна быть реализация с открытым исходным кодом. Меня особенно интересует Java (источник или JAR), но любой вкус VB или другого языка может быть полезен.

Ответ 1

Вы можете найти целевой треугольник пройдя триангуляцию по направлению к найденной точке. Это предполагает, что вы можете получить доступ к соседним треугольникам в постоянное время, что имеет место, если триангуляция сохраняется в двусвязном краевом списке или аналогичных структурах. Реализация прост, потому что вам не нужны никакие дополнительные структуры данных.

Добавленные сведения:. Пусть P - искомая точка. Возьмем любой треугольник T0 и точку P0 в T0. Если P находится в T0, вы закончите. Остается найти ребро E0 из T0, которое пересекает линия P0-P. Перейдите к соседнему треугольнику T1 из T над ребром E0 и возьмите точку P1 в T1. Теперь повторяем, пока треугольник Tn не содержит P.

Ответ 2

Знания моих алгоритмов немного ржавые. Вместо моего предыдущего ответа вы, вероятно, лучше используете "Диаграмма Вороного" .

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

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

Я предполагаю, что вы также можете использовать R-tree, в котором вы ссылаетесь на свои треугольники.

Быстрый поиск в google с помощью java r-tree должен помочь вам найти существующие библиотеки.

Ответ 3

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

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

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

Если это не достаточно быстро, вам нужно настроить R-Tree. Это позволяет быстро находить треугольники из их местоположений, но для этого требуется много предварительной обработки и значительного объема памяти для дерева.

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

Ответ 4

Вы можете использовать иерархию Delaunay http://hal.inria.fr/inria-00166711 Идея состоит в том, чтобы взять подмножество точек, триангулировать ее и иметь связи между вершинами между двумя слоями. Затем "прогулка" выполняется в небольшой триангуляции, затем одна переходит от одного слоя к следующему, затем продолжается прогулка. Это реализовано в триангуляциях CGAL: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Section_37.10

Ответ 5

Я нашел здесь рабочую реализацию: http://www.cs.bgu.ac.il/~benmoshe/DT/

Метод find находит треугольник, содержащий данную точку, а z делает плоскую интерполяцию.

К сожалению, это скомпилированный JAR, поэтому я не знаю, что такое алгоритм, но я чувствую, что он "проходит через триангуляцию" , как это было предложено @Jiri и @DJClayworth.

Также неудачной является довольно нетрадиционная номенклатура, используемая в этом JAR. В конце концов я могу написать класс обертки с лучшей номенклатурой.