У меня есть плоская триангуляция Делоне, состоящая примерно из 1 миллиона треугольников. Каждая вершина помечена несколькими скалярными метриками [1], и я хотел бы увидеть быструю и простую интерполяцию каждой из этих метрик на одной и той же регулярной сетке. Для справки, объединение моих треугольников покрывает около 10 миллионов ячеек сетки, имеющих (целочисленные) координаты. [2]
Когда я говорю просто, я имею в виду просто. Билинейка это хорошо! Насколько я понимаю, это (а) в основном то, чем графические процессоры зарабатывают на жизнь, и (б) вероятно, является предметом бесчисленных домашних заданий. Я сам являюсь государственным исследователем в области общественного здравоохранения, поэтому для меня это не домашнее задание. :-)
В моей медленной, но правильной эталонной реализации я могу вычислить следующее примерно за 10 минут:
Для каждого треугольника T:
- Набор G всех (целочисленных) декартовых координат в пределах ограничивающей рамки T;
- Барицентрические координаты (u, v, w) для каждого (x, y) в G;
- Отказ от (u, v, w), которые не все положительны, то есть внутри T;
- Взвешенная сумма (uz_1 + vz_2 + w*z_3) для каждой оставшейся координаты в T, где z_1, z_2 и z_3 — для данной метрики [1] скалярные значения в вершины Т.
Мне действительно нужно, чтобы шаги 1-3 были быстрыми; шаг 4 тривиален, но это моя конечная цель. В идеале решение должно принимать одну из следующих форм:
- Соответствующая лицензия (GPL в порядке) библиотека с очень простым API; или же
- Объяснение настолько ясное, что становится очевидным, как программист среднего уровня может написать код на Fortran, R, Python или C.
Классической постановкой этой задачи является работа по моделированию местности «TIN to DEM». Но кажется, что в наши дни чаще требуется обратное (?)
Некоторая базовая очистка, например удаление дубликатов, когда точка попадает точно на ребро или вершину, общую для 2+ треугольников, тоже подойдет.
Заранее большое спасибо за ваше время и внимание. Я уберу форматирование и отредактирую в соответствии с предложениями, как только сойду с поезда!
Сноски:
[1] Высота над уровнем моря, температура и влажность. [2] Целые числа в том смысле, что они расположены на расстоянии 20x20 м друг от друга в сетке UTM. Так что просто масштабируйте на 20.
