Билинейная интерполяция по целочисленным координатам в триангуляции Деланея

Question

У меня есть плоская треугольница Делоне, состоящая из около 1 миллиона треугольников. Каждая вершина помечена несколькими скалярными метриками [1], и я хотел бы увидеть быструю и простую интерполяцию каждой из этих показателей в одной и той же регулярной сетке. Для справки, объединение моих треугольников охватывает около 10 миллионов ячеек сетки, имеющих (целочисленные) координаты. [2]

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

В моей медленной, но правильной эталонной реализации, можно вычислить следующие примерно за 10 минут:

для каждого треугольника Т:

1. Множество О всех (целое число) декартовых координатах в ограничивающей рамке T;
2. Барицентрические координаты (u, v, w) для каждого (x, y) в G;
3. Отклонение (u, v, w), которое не все положительно, т. Е. Внутри T;
4. Весовая сумма (u z_1 + v z_2 + w * z_3) для каждой оставшейся координаты в T, где z_1, z_2 и z_3 для данной метрики [1] являются скалярными значениями в вершинах T.

Мне действительно нужны шаги 1-3, чтобы быть быстрыми; шаг 4 тривиален, но это моя конечная цель. В идеале решение может принимать одну из следующих форм:

• Лицензированная (GPL в порядке) библиотека с простыми API; или
• Объяснение этого достаточно ясно, что это очевидно, как промежуточный программист может написать код в Fortran, R, Python или C.

Классическая формулировка этой задачи является «ТИН в DEM» местности -модулировать работу. Но кажется, что в наши дни обратное более часто необходимо (?)

Некоторая базовая очистка, например удаление дубликатов, когда точка попадает точно на ребро или вершину, разделяемую двумя + треугольниками, тоже в порядке.

Большое спасибо заранее за ваше время и внимание. Я очищу форматирование и отредактирую каждое предложение, как только я уйду с поезда!

Сноска:

[1] Высота, температура, и влажность. [2] Целые числа в том смысле, что они расположены на расстоянии 20x20 м друг от друга на сетке UTM. Так что просто масштабируйте на 20.

Answer 1

Хотя я не вижу ничего, что могло бы объяснить медленность в вашем описании, вот как бы я справился с этим. Основным ингредиентом является «треугольный сканер».

Начните с сортировки трех вершин на Y. Это занимает три сравнения, и существует только шесть возможных конфигураций. Петля на целочисленных ординатах от вершины Y до середины Y, затем средняя Y до нижней Y. Для каждой ординаты пересечения с левой и правой сторонами дают вам интервал.

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

Вместо использования барицентрических координат вы можете установить уравнение плоскости, т. Е. Оценить коэффициенты Z = a X + b Y + c и использовать эту формулу для интерполяции. (Вы можете даже вычислить значения поэтапно, т. Е. Z(X + 1) = Z(X) + a, но для небольшого количества точек на треугольник я не уверен, что это стоит.)

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

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

Общая рабочая нагрузка будет чувствительна к количеству треугольников, степени Y области и количеству покрытых узлов сетки, подсчитывая несколько арифметических операций для каждого из этих факторов. Для миллиона треугольников и десяти миллионов ячеек сетки время работы ниже секунды маловероятно.