Некоторые подробности триангуляции

Принципы создания

При создании Soft-а ставились следующие цели:

1. Триангуляция должна быть близка к триангуляции Делоне.
2. Время счета должно быть линейной функцией от количества исходных точек.
3. Входными данными могут быть перечисленные ниже данные в любом сочетании:
  • точки на плоскости с координатами X, Y и атрибутом А;
  • ребра, задаваемые полилиниями (массив точек) с атрибутом А;
  • контур оболочки, задаваемый поли-полигоном (полигон с "дырками") с атрибутом А.

  • 4. Должен быть предусмотрен режим триангуляции (NonEqAttr), при котором ребра создаваемых треугольников проводятся преимущественно через точки, имеющие несовпадающие атрибуты.
    5. Время триангуляции 1 млн. точек должно быть разумным - скажем не более нескольких минут для процессоров с тактовой частотой 1 ГГц.

    Реализация

    Soft написан преимущественно на Delphi, имеются вставки C++. Оформлен он в виде DLL-библиотеки, над которой сделан интерфейс доступа из трех сред: Delphi, Builder, Visual Studio. К этим трем средам написаны примеры использования.

    Особенности

    Главная особенность - наличие режима NonEqAttr, предназначенного в первую очередь для триангуляции рельефа местности по исходным изолиниям. Иллюстрация работы этого режима и стандартного (Делоне) приведена ниже.


    режим NonEqAttr
    Рис.1. Триангуляция в режиме NonEqAttr.

    режим Делоне
    Рис.2. Триангуляция Делоне.

    Комментарий. Красным цветом показаны исходные ребра, заданные изолиниями рельефа, синим - ребра, полученные в результате триангуляции. На приведенном фрагменте изолинии имеют разные атрибуты (значения высот), поэтому в режиме NonEqAttr триангуляция выполняется принциально по другому и имеет существенные различия с методом Делоне.
    Триангуляция в режиме NonEqAttr правильней аппроксимирует рельеф местности.

    Статья на эту тему


    Еще одна особенность - возможность триангуляции внутри заданного поли-полигона, т.е. полигона, у которого могут быть "дырки". Фрагмент такой триангуляции показан на рис.3.

    триангуляция полигона
    Рис.3. Триангуляция полигона с "дырками".

    Характеристики

    Фукция роста времени счета от числа исходных точек - линейная.
    Абсолютные временные характеристики триангуляции вполне приемлемые, хотя и не обладают такой "скорострельностью", которую получил Джонатан Шевчук.
    Реальная карта с изолиниями, имеющими 500 000 точек, триангулировалась в режиме NonEqAttr в течение 160 сек. (Процессор Athlon 1.3, ОЗУ 256 М).
    Время счета без использования режима NonEqAttr уменьшается примерно вдвое.


    Здесь можно скачать Soft

    На главную

    Хостинг от uCoz