30.1 Треугольная сетка Делоне ¶

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

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

: tri = delaunay (x, y) ¶

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

: tri = delaunay (x) ¶

: tri = delaunay (…, options) ¶

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

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

Для наборов в 3D пространстве возвращаемое значение 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 терпит неудачу при обработке 2D ввода, то вычисление сетки выполняется повторно с параметрами {"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.

Для 3D ввода 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. Например, 2D симплекс — это треугольник, а 3D симплекс — тетраэдр.

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

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

Если Qhull терпит неудачу для 2D ввода, то вычисление сетки выполняется повторно с параметрами {"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.

• Построение треугольной сетки
• Определение точек в треугольной сетке