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 оптимизирована для 2-мерных случаев, и барицентрические координаты не формируются явно.

: 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.