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.

См. также: 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).

См. также: 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.