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.

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