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.

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

: idx = tsearchn (x, t, xi) ¶

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

Поиск содержащего выпуклого оболочки Делоне.

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

Если запрошено tsearchn, также возвращает барицентрические координаты p содержащих треугольников.

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

Пример использования 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.