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

Необязательный выходной параметр 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.