30.1 Триангуляция Делоне

Триангуляция Делоне строится на основе множества окружностей. Эти окружности выбираются таким образом, чтобы на окружности каждой окружности находилось по крайней мере три точки из заданного набора. Ни одна из точек набора не попадает внутрь какой-либо окружности.

В общем случае на окружности любой окружности находятся только три точки. Однако в некоторых случаях, и особенно для случая регулярной сетки, на одной окружности может находиться 4 или более точек. В этом случае триангуляция Делоне не является уникальной.

: tri = delaunay (x, y) ¶

: tetr = delaunay (x, y, z) ¶

: tri = delaunay (x) ¶

: tri = delaunay (…, options) ¶

Вычислить триангуляцию Делоне для 2-D или 3-D набора точек.

Для 2-D наборов возвращаемое значение tri представляет собой набор треугольников, удовлетворяющих критерию окружности Делоне, т. е. ни одна точка из [x, y] не находится внутри окружности определяющего треугольника. Набор треугольников tri является матрицей размером [n, 3]. Каждая строка определяет треугольник, а три столбца — три вершины треугольника. Значение tri(i,j) — индекс в x и y для местоположения j-й вершины i-го треугольника.

Для 3-D наборов возвращаемое значение tetr представляет собой набор тетраэдров, удовлетворяющих критерию окружности Делоне, т. е. ни одна точка из [x, y, z] не находится внутри окружности определяющего тетраэдра. Набор тетраэдров является матрицей размером [n, 4]. Каждая строка определяет тетраэдр, а четыре столбца — четыре вершины тетраэдра. Значение tetr(i,j) — индекс в x, y, z для местоположения j-й вершины i-го тетраэдра.

Входной параметр x также может быть матрицей с двумя или тремя столбцами, где первый столбец содержит данные x, второй — y, а необязательный третий — z.

Необязательный конечный аргумент, который должен быть строкой или ячейкой строк, содержит параметры, передаваемые команде qhull. Подробности см. в документации библиотеки Qhull http://www.qhull.org/html/qh-quick.htm#options. Параметры по умолчанию — {"Qt", "Qbb", "Qc"}. Если Qhull терпит неудачу для входных данных 2-D, триангуляция пытается выполниться снова с параметрами {"Qt", "Qbb", "Qc", "Qz"}, что может привести к снижению точности.

Если options отсутствует или [], используются параметры по умолчанию. В противном случае options заменяет список параметров по умолчанию. Для добавления пользовательских параметров к значениям по умолчанию необходимо повторить параметры по умолчанию в options. Для передачи без аргументов используйте пустую строку.

x = rand (1, 10);
y = rand (1, 10);
tri = delaunay (x, y);
triplot (tri, x, y);
hold on;
plot (x, y, "r*");
axis ([0,1,0,1]);

См. также: delaunayn, convhull, voronoi, triplot, trimesh, tetramesh, trisurf.

Для входных данных 3-D delaunay возвращает набор тетраэдров, удовлетворяющих критериям окружности Делоне. Аналогично, delaunayn возвращает N-мерный симплекс, удовлетворяющий критериям окружности Делоне. N-мерное расширение триангуляции называется разбиением.

: T = delaunayn (pts) ¶

: T = delaunayn (pts, options) ¶

Вычислить триангуляцию Делоне для N-мерного набора точек.

Триангуляция Делоне — это разбиение выпуклой оболочки набора точек, такая, что никакая N-сфера, определённая N-треугольниками, не содержит других точек из набора.

Входная матрица pts размером [n, dim] содержит n точек в пространстве размерности dim. Возвращаемая матрица T имеет размер [m, dim+1]. Каждая строка T содержит набор индексов для обратной ссылки на исходный набор точек pts, описывающий симплекс размерности dim. Например, 2-D симплекс — это треугольник, а 3-D симплекс — тетраэдр.

Необязательный второй аргумент, который должен быть строкой или ячейкой строк, содержит параметры, передаваемые команде qhull. Подробности см. в документации библиотеки Qhull http://www.qhull.org/html/qh-quick.htm#options. Параметры по умолчанию зависят от размерности ввода:

• 2-D и 3-D: options = {"Qt", "Qbb", "Qc"}
• 4-D и выше: options = {"Qt", "Qbb", "Qc", "Qx"}

Если Qhull терпит неудачу для входных данных 2-D, триангуляция пытается выполниться снова с параметрами {"Qt", "Qbb", "Qc", "Qz"}, что может привести к снижению точности.

Если options отсутствует или [], используются параметры по умолчанию. В противном случае options заменяет список параметров по умолчанию. Для добавления пользовательских параметров к значениям по умолчанию необходимо повторить параметры по умолчанию в options. Для передачи без аргументов используйте пустую строку.

См. также: delaunay, convhulln, voronoin, trimesh, tetramesh.

Пример триангуляции Делоне для набора точек:

rand ("state", 1);
x = rand (1, 10);
y = rand (1, 10);
T = delaunay (x, y);
X = [ x(T(:,1)); x(T(:,2)); x(T(:,3)); x(T(:,1)) ];
Y = [ y(T(:,1)); y(T(:,2)); y(T(:,3)); y(T(:,1)) ];
axis ([0, 1, 0, 1]);
plot (X, Y, "b", x, y, "r*");

Результат, который можно увидеть на Рис. 30.1.

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