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", "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", "Qz"}
• 4D и выше: options = {"Qt", "Qbb", "Qc", "Qx"}

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

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

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

rand ("state", 2);
x = rand (10, 1);
y = rand (10, 1);
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.

Рисунок 30.1: Треугольная сетка Делоне для случайного набора точек