30.1.2 Определение точек в триангуляции

Часто необходимо определить, находится ли заданная точка в N-мерном пространстве внутри разбиения Делоне множества точек в этом N-мерном пространстве, и, если находится, какой N-симплекс содержит эту точку и какая точка в разбиении является ближайшей к заданной точке. Функции tsearch и dsearch выполняют эту задачу для триангуляции, а tsearchn и dsearchn — для N-мерного разбиения.

Чтобы определить, попадает ли точка, представленная вектором p, в один из симплексов N-симплекса, можно записать декартовы координаты точки в параметрической форме относительно N-симплекса. Эта параметрическая форма называется барицентрическими координатами точки. Если точки, задающие N-симплекс, представлены N + 1 векторами t(i,:), барицентрические координаты точки p задаются выражением

p = beta * t

где beta содержит N + 1 значений, которые вместе, будучи записанными в виде вектора, представляют барицентрические координаты точки p. Чтобы обеспечить единственность решения для значений beta, вводится дополнительное условие

sum (beta) == 1

поэтому приведённое выше выражение можно записать так:

p - t(end, :) = beta(1:end-1) * (t(1:end-1, :)
                - ones (N, 1) * t(end, :)

Решив уравнение относительно beta, получим

beta(1:end-1) = (p - t(end, :)) /
                (t(1:end-1, :) - ones (N, 1) * t(end, :))
beta(end) = sum (beta(1:end-1))

что даёт формулу преобразования декартовых координат точки p в барицентрические координаты beta. Важное свойство барицентрических координат состоит в том, что для всех точек N-симплекса

0 <= beta(i) <= 1

Следовательно, для проверки в tsearch и tsearchn достаточно представить каждую точку в барицентрических координатах каждого из симплексов N-симплекса и проверить значения beta. Именно так реализована функция tsearchn. Функция tsearch оптимизирована для двумерного случая, и барицентрические координаты явно не вычисляются.

: idx = tsearch (x, y, t, xi, yi)

Поиск охватывающей выпуклой оболочки Делоне.

Для t = delaunay (x, y) находит индекс в t, содержащий точки (xi, yi). Для точек вне выпуклой оболочки значение idx равно NaN.

Примечание по программированию: сложность алгоритма составляет O(M*N) для поиска M точек в N треугольниках. Обычно производительность значительно выше, если искомые точки расположены на одном непрерывном пути: сначала проверяется область, в которой была найдена предыдущая точка, что ускоряет поиск точек на непрерывном пути.

См. также: delaunay, delaunayn.

: idx = tsearchn (x, t, xi)

: [idx, p] = tsearchn (x, t, xi)

Поиск симплексов, содержащих заданные точки.

Функция tsearchn обычно используется вместе с delaunayn: t = delaunayn (x) возвращает набор симплексов t, а затем tsearchn возвращает индекс строки t, содержащей каждую точку из xi. Для точек вне выпуклой оболочки значение idx равно NaN.

При необходимости tsearchn также возвращает барицентрические координаты p охватывающих симплексов.

См. также: delaunay, delaunayn, tsearch.

Пример использования tsearch можно рассмотреть на простой триангуляции

x = [-1; -1; 1; 1];
y = [-1; 1; -1; 1];
tri = [1, 2, 3; 2, 3, 4];

состоящей из двух треугольников, заданных переменной tri. Затем можно определить, в какой треугольник попадает точка:

tsearch (x, y, tri, -0.5, -0.5)
⇒ 1
tsearch (x, y, tri, 0.5, 0.5)
⇒ 2

и убедиться, что точка не лежит ни в одном из треугольников:

tsearch (x, y, tri, 2, 2)
⇒ NaN

Функции dsearch и dsearchn находят ближайшую к заданной точке точку разбиения. Заданная точка не обязательно должна находиться в разбиении, и даже если она там находится, возвращённая точка разбиения не обязательно должна быть одной из вершин N-симплекса, содержащего заданную точку.

: idx = dsearch (x, y, tri, xi, yi)

: idx = dsearch (x, y, tri, xi, yi, s)

Возвращает индекс idx ближайшей точки в x, y для элементов [xi(:), yi(:)].

Переменная s принимается для совместимости, но игнорируется.

См. также: dsearchn, tsearch.

: idx = dsearchn (x, tri, xi)

: idx = dsearchn (x, tri, xi, outval)

: idx = dsearchn (x, xi)

: [idx, d] = dsearchn (…)

Возвращает индекс idx ближайшей точки в x для элементов xi.

Если задано значение outval, значения xi, не содержащиеся ни в одном из симплексов tri, заменяются на outval. Обычно tri возвращается функцией delaunayn (x).

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

См. также: dsearch, tsearch.

Пример использования dsearch с приведёнными выше значениями x, y и tri:

dsearch (x, y, tri, -2, -2)
⇒ 1

Если требуется пометить точки, находящиеся за пределами разбиения, можно использовать dsearchn следующим образом:

dsearchn ([x, y], tri, [-2, -2], NaN)
⇒ NaN
dsearchn ([x, y], tri, [-0.5, -0.5], NaN)
⇒ 1

В этом случае точка за пределами разбиения помечается значением NaN.