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: Триангуляция Делоне для случайного набора точек

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