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

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

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

: tri = delaunay (x, y) ¶

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

: tri = delaunay (x) ¶

: tri = delaunay (…, options) ¶

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

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

Для 3-мерных множеств возвращаемое значение 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-мерного ввода, треугольная сетка повторно вычисляется с опциями {"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-мерных входных данных 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-мерный симплекс является треугольником, а 3-мерный - тетраэдром.

Необязательный второй аргумент, который должен быть строкой или ячейным массивом строк, содержит опции, передаваемые командному интерпретатору 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-мерного ввода, треугольная сетка повторно вычисляется с опциями {"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.

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