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

Question

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

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

• Как узнать, какой треугольник содержит точку (x,y)? Когда я знаю это, я думаю, что довольно просто интерполировать между тремя вершинами треугольника.

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

Answer 1

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

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

Answer 2

Вы можете использовать иерархию Делоне 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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

---

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

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

Answer 5

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

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

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

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