Алгоритм исправления топологических ошибок в программных приложениях ГИС

Связанный вопрос здесь.

Я заметил, что обеспечение топологической корректности имеет важное значение для приложений ГИС, потому что входные данные от логической операции пользователя или полигона могут иметь серьезные топологические проблемы (даже если полигоны выглядят правильно), которые могут поставить под угрозу качество последующих операций.

Чистый полигон - это то, что делают Geo Wizards для обеспечения правильности топологии.

У Arcgis также есть команда убирать щепки.

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

Быстрый поиск в Google Scholar обнаружил следующие хорошо цитируемые статьи:

• Тьерри Убеда и Макс Й. Эгенхофер. Исправление топологических ошибок в ГИС . Достижения в области пространственных баз данных, Конспект лекций в области компьютерных наук , 1997, том 1262/1997, 281-297, DOI: 10.1007 / 3-540-63238-7_35 ( PDF )

• Сильви Сервинье, Тьерри Убеда, Ален Пуричелли и Роберт Лаурини. Методология улучшения пространственной согласованности географических баз данных . GeoInformatica , 2000, том 4, номер 1, 7-34, DOI: 10.1023 / A: 1009824308542 ( PDF )

Вы можете найти подробное описание процедур топологической очистки в исходном коде и руководствах GRASS GIS: http://grass.osgeo.org/programming7

Процедуры очистки кодируются здесь: http://trac.osgeo.org/grass/browser/grass/trunk/vector/v.clean

Примеры для базовых процедур:

• Выберите подвески: http://grass.osgeo.org/programming7/vector_8h.html#a40e09e816c8bcb93d247710c834d93ab
• Удалить дубликаты: http://grass.osgeo.org/programming7/vector_8h.html#a7c0deda52a08dd5a02bc05ccbe311c60
• Строки: http://grass.osgeo.org/programming7/vector_8h.html#a563fb4e4b42695cfbfbf2dc17d42028a
• и т.п.

Основные понятия изложены здесь: http://grass.osgeo.org/programming7/vectorlib.html#vlibTopoExamples

Хотя это и не алгоритм, эта страница дает некоторую информацию о том, какие типы ошибок топологии «проверяет геометрия» ищет в инструментах ArcGIS Проверить геометрию / Восстановить геометрию. http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//00170000003v000000

Null geometry: The record will be deleted from the feature class. To keep records with null geometry, uncheck the tool dialog option Delete Features with    Null Geometry, or in scripting set the delete_null parameter to KEEP_NULL.
Short segment: The geometry's short segment will be deleted.
Incorrect ring ordering: The geometry will be updated to have correct ring ordering.
Incorrect segment orientation: The geometry will be updated to have correct segment orientation.
Self intersections: the areas of overlap in a polygon will be dissolved.
Unclosed rings: The unclosed rings will be closed by connecting the ring's end points.
Empty parts: The parts that are null or empty will be deleted.
Duplicate vertex: One of the vertices will be deleted.
Mismatched attributes: The Z or M coordinate will be updated to match.
Discontinuous parts: Multiple parts will be created from the existing discontinuous part.
Empty Z values: The Z value will be set to 0.

Я не думаю, что есть способ полностью автоматизировать исправление топологических ошибок в данном наборе данных. Некоторые вещи, такие как висячие элементы, могут автоматизировать разбиение и последующее удаление полученного висячего. Но тогда как насчет полос между двумя смежными полигонами, какой полигон должен быть объединен с каким полоской, чтобы устранить его? Этот тип вопроса, кажется, требует ввода пользователя. Однако, чтобы идентифицировать ошибки, я думаю, что алгоритмы используют какую-то разновидность DE-9IM (размерно расширенный 9 что-то что-то). Я думаю, что вам лучше всего взглянуть на Java Topology Suite (JTS). В частности, класс Geometry Graph. Я думаю, что это можно использовать для построения различных компонентов определенной геометрии, а затем использовать для проверки различных проблем топологии. Я никогда не делал этого, но изучил это не так давно.

Если вы не знакомы с Java, GEOS - это разновидность JTS для C ++, или NetTopologySuite - это разновидность C #.

Надеюсь, это поможет.

Документация команд ArcGIS Integrate уже упоминалась, но ESRI также выпустила технический документ « Понимание геометрической обработки в ArcGIS», документирующий логику обработки, которая используется Integrate (и операции геообработки, включающие допуск в более общем плане). Это сфокусировано на предотвращении и исправлении топологических ошибок, возникающих при геообработке. Есть несколько ссылок, которые также могут быть полезны.