Принципы создания
При создании Soft-а ставились следующие цели:
1. Триангуляция должна быть близка к триангуляции Делоне.
2. Время счета должно быть линейной функцией от количества исходных точек.
3. Входными данными могут быть перечисленные ниже данные в любом сочетании:
точки на плоскости с координатами X, Y и атрибутом А;
ребра, задаваемые полилиниями (массив точек) с атрибутом А;
контур оболочки, задаваемый поли-полигоном (полигон с "дырками") с атрибутом А.
4. Должен быть предусмотрен режим триангуляции (NonEqAttr), при котором ребра создаваемых треугольников
проводятся преимущественно через точки, имеющие несовпадающие атрибуты.
5. Время триангуляции 1 млн. точек должно быть разумным - скажем не более
нескольких минут для процессоров с тактовой частотой 1 ГГц.
Реализация
Soft написан преимущественно на Delphi, имеются вставки C++. Оформлен он в виде
DLL-библиотеки, над которой сделан интерфейс доступа из трех сред:
Delphi, Builder, Visual Studio. К этим трем средам написаны примеры использования.
Особенности
Главная особенность - наличие режима NonEqAttr, предназначенного в первую очередь
для триангуляции рельефа местности по исходным изолиниям. Иллюстрация работы
этого режима и стандартного (Делоне) приведена ниже.
Рис.1. Триангуляция в режиме NonEqAttr.
Рис.2. Триангуляция Делоне.
Комментарий.
Красным цветом показаны исходные ребра, заданные изолиниями рельефа, синим - ребра,
полученные в результате триангуляции. На приведенном фрагменте изолинии имеют
разные атрибуты (значения высот), поэтому в режиме NonEqAttr триангуляция выполняется
принциально по другому и имеет существенные различия с методом Делоне.
Триангуляция в режиме NonEqAttr правильней аппроксимирует рельеф местности.
Еще одна особенность - возможность триангуляции внутри заданного поли-полигона,
т.е. полигона, у которого могут быть "дырки". Фрагмент такой триангуляции показан
на рис.3.
Рис.3. Триангуляция полигона с "дырками".
Характеристики
Фукция роста времени счета от числа исходных точек - линейная.
Абсолютные временные характеристики триангуляции вполне приемлемые, хотя и не обладают такой
"скорострельностью", которую получил
Джонатан Шевчук.
Реальная карта с изолиниями, имеющими 500 000 точек, триангулировалась в режиме NonEqAttr
в течение 160 сек. (Процессор Athlon 1.3, ОЗУ 256 М).
Время счета без использования режима NonEqAttr уменьшается примерно вдвое.
Статья на эту тему