Страница 1 из 1

Алгоритмы для обрезки полигонов

Добавлено: 18 май 2018, 09:17
rhot
Провёл небольшой эксперимент.

Дано:
вектор А - 1956 полигонов,
вектор Б - 2920 полигонов,
GEOS - версия 3.6.1,
SAGA - версия 2.1.2.

Найти:
время объединения векторов А и Б

Результат:
При прочих равных условиях GEOS выполнил задачу за 56,25 секунд, а SAGA справилась за 8,41 секунды.

Полез рыться в источниках. Выяснилось, что SAGA использует алгоритм Vatti. На GEOS не смог найти ссылку на алгоритмы. Учитавая, что GEOS - это порт C++ от JTS, посмотрел у них на документацию. Пишут, что их алгоритмы уникальны, но они также использовали работу Vatti.

Собственно вопрос:
какие алгоритмы используют современные ГИС/библиотеки для обрезки полигонов?
SAGA - Vatti
GEOS (QGIS, GRASS, PostGIS) - ?
CGAL - ?
ArcGIS - ?

Re: Алгоритмы для обрезки полигонов

Добавлено: 18 май 2018, 11:02
freeExec
Э, это как: тема обрезки полигонов, эксперимент объединения векторов

Re: Алгоритмы для обрезки полигонов

Добавлено: 18 май 2018, 11:07
rhot
Дело в том, что, чтобы объединить, полигоны сначала делятся/разрезаются. Не все векторы полигоны, но все полигоны - векторы. :D