Иллюстрированный самоучитель по MatLab

Триангуляция. Расчет триангуляции.

Далее мы рассмотрим функции геометрического анализа данных. Такой анализ не относится к достаточно распространенным средствам анализа данных, но для специалистов он представляет несомненный интерес.

Пусть есть некоторое число точек. Триангуляция Делоне – это множество линий, соединяющих каждую точку с ее ближайшими соседними точками. Диаграммой Вороного называют многоугольник, вершины которого – центры окружностей, описанных вокруг треугольников Делоне.


В системе MATLAB определены функции триангуляции Делоне, триангуляции Делоне для ближайшей точки и поиска наилучшей триангуляции. Рассмотрим функции, реализующие триангуляцию Делоне.

  • TRI = delaunay(x.y) – возвращает матрицу размера mх3 множества треугольников (триангуляция Делоне), такую что ни одна из точек данных, содержащиеся в векторах х и у, не попадают внутрь окружностей, проходящих через вершины треугольников. Каждая строка матрицы TRI определяет один такой треугольник и состоит из индексов векторов х и у;
  • TRI = delaunay('x,у.'sorted'-) – при расчетах предполагается, что точки векторов х и у отсортированы сначала по у, затем по х и двойные точки уже устранены. Пример:
>> rand('state',0);
>> x=rand(1.25);
>> y=rand(1.25);
>> TRI = delaunay(x,y);
>> trimesh(TRI,x,y,zeros(size(x)))
>> axis([0 1 0 1]); hold on;
>> plot(x,y,'0')
  • dsearch(x.y,TRI,xi,yi) – возвращает индекс точки из числа содержащихся в массивах х и у, ближайшей к точке с координатами (x1,y1), используя массив данных триангуляции TRI (триангуляция Делоне для ближайшей точки);
  • dsearch(x,y,TRI,x1,y1,S) – делает то же, используя заранее вычисленную разреженную матрицу триангуляции S: S=sparse(TRI(:,[1 1 2 2 3 3]), TRK:,[2 3 1 3 1 2]).1.nxy.nxy), где nxy=prod(size(x));
  • tsearch(x,y.TRI,xi,yi) – выполняет поиск наилучшей триангуляции, возвращает индексы строк матрицы триангуляции TRI для каждой точки с координатами (xi,y1). Возвращает NaN для всех точек, находящихся вне выпуклой оболочки.

Триангуляция трехмерных и n-мерных массивов (n>=2) осуществляется при помощи функций delaunayS и delaunayn соответственно. Эти функции используют не алгоритм вычисления диаграмм Вороного, как del aunay, а алгоритм qhul 1 Национального научно-технического и исследовательского центра визуализации и вычисления геометрических структур США [В MATLAB 6.1 функции delaunay, convhull, griddata, voronoi также используют qhull. – Примеч. ред.].

Построенная по приведенному ранее примеру диаграмма представлена на рис. 17.1.

Иллюстрированный самоучитель по MatLab › Обработка данных › Триангуляция. Расчет триангуляции.
Рис. 17.1. Пример применения функции delaunay

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.