ST_IsValid и повторяющиеся узлы

Ответить
Аватара пользователя
Denis Rykov
Гуру
Сообщения: 3376
Зарегистрирован: 11 апр 2008, 21:09
Репутация: 529
Ваше звание: Author
Контактная информация:

ST_IsValid и повторяющиеся узлы

Сообщение Denis Rykov » 01 апр 2010, 14:55

Совсем недавно возник вопрос: "Являются ли корректными с точки зрения стандартов OGC полигоны с повторяющимися узлами?" Инструменты проверки таких полигонов в QGIS, ArcView и ArcGIS выдают сообщения об ошибке, свидетельствующей о самопересечении. Посмотрим, что на это скажет PostGIS, который как сказано на главной странице:
follows the OpenGIS "Simple Features Specification for SQL" and has been certified as compliant with the "Types and Functions" profile.
И что же мы имеем в результате выполнения команды select ST_IsValidReason(the_geom):

Код: Выделить всё

Valid Geometry
То есть судя по всему, стандарты OGC допускают такие полигоны. Однако, после прочтения текста стандарта и его небольшой выжимки, проясняющей вопросы простоты и валидности объектов, прямого указания на то, что подобного рода полигоны допустимы или нет, я не нашёл. Так может стандарт не покрывает подобные ситуации и разработчики PostGIS-а согласно каким-то своим соображениям посчитали такие полигоны корректными, а разработчики другого ПО (QGIS в частности) - нет? Возможно. Но чтобы не гадать, отправимся в рассылку PostGIS и спросим там: "Почему PostGIS считает такие полигоны валидными и как это соотносится со стандартом OGC и почему на их взгляд другое ПО считает такие полигоны не валидными?". В результате получился очень интересный диалог (привожу переведенный и несколько сокращенный вариант ответов на сколько я их понял, если кто хочет, может прочитать оригинал):
strk писал(а):По моим соображениям при передачи данных из PostGIS в QGIS, ArcView или ArcGIS (ПО, которое ругается на такие полигоны) могла быть потеряна точность координат и вследствие этого возникает ошибка самопересечения.
Для меня осталось не понятным, что хотел сказать автор. Следующий пост также ясности не внёс:
Andrea Peri писал(а):Привет. Попробую объяснить. Самопересечение недопустимо согласно OGC, поскольку в стандарте описана модель простой геометрии (simple-feature). Функция же проверки валидности ST_IsValid в PostGIS фактически применима не только к простым геометриям.
Опять двадцать пять :) А что же тогда является критерием валидности геометрии в PostGIS?
Andrea Peri писал(а): Можно использовать функцию ST_IsSimple, чтобы узнать, является ли геометрия простой, а затем с помощью ST_IsValid определить является ли она валидной.
Что сказал, что нет - яснее не стало. Еще когда переводил стандарт OGC я для себя отметил, что полигон - по определению - всегда простая геометрия, поэтому уже заранее был известен результат функции ST_IsSimple, что и подтвердилось на практике. Из каких соображений PostGIS считает полигоны с дублирующимися узлами валидными? Послушаем следующего участника:
Martin Davis писал(а): Данный тип полигонов является корректным с точки зрения стандартов OGC и поэтому определяется как валидный в PostGIS (а также в GEOS/JTS). Следует посмотреть на семантику процесса валидации в других системах и определиться, почему они считают такие полигоны не корректными. Модель OGC SFS допускает дублирующиеся точки.
Вот он долгожданный ответ, однако хотелось бы спросить у отвечающего, а где он собственно узрел в тексте стандарта то, о чем пишет? Подключается еще один товарищ:
Kevin Neufeld писал(а): Внесу некоторую ясность. Согласно спекам OGC понятие простота применима *только* к точечным и линейным объектам (а также к мультиточкам и мультилиниям). Понятие валидности же применимо *только* к площадным объектам - полигонам и мультиполигонам.

В стандарте OGC вопрос повторяющихся точек в линейных объектах прояснен не до конца. В нем сказано: "не должны иметь аномальных геометрических точек, таких как самопересечения или самокасания" и "линейный объект является простым, если не проходит через одну точку дважды".

В PostGIS также реализовано кое-что из SQL/MM спецификации. В ней я читаю: "не является простым если некоторые внутренние точки расположены на одинаковых местах с другими точками или точками границы". Для меня это более понятно, и (обращается ко мне) я считаю, что ты прав и что ST_IsSimple на самом деле не должен допускать дублирующих точек. Отправлю тикет.

Итак, простота - только для точек и линий.
Полигон является валидным в том случае, если составляющие его линии просты (например, не допустимы восьмёрки) и выполняется еще некоторый ряд условий (внутреннее кольцо должно содержаться внутри наружнего и т.д.). Поэтому и полигон с дублирующимися узлами считается валидным, так как PostGIS не распознает линейные объекты с дубликатами (границы полигонов) как не простые.
Таким образом, из слов высказавшегося товарища можно сделать вывод, что согласно OGC - ситуация не ясна - валидный полигон или нет, так как не понятно - является ли линия простой, если в ней присутствуют дубликаты. Вот что ему ответил уже фигурировавший ранее в диалоге и утверждавший, что полигон однозначно валиден по OGC Martin Davis:
Martin Davis писал(а): То есть ты утверждаешь, что геометрия, содержащая последовательные дублирующиеся точки - некорректна?
Это довольно сильное изменение к семантики валидности.

Если ты изменишь семантику isSimple, чтобы она выдавала false для линейных объектов, содержащих дублирующиеся точки, то тем самым потеряешь возможность отличать настоящее топологическое самопересечение от топологически иррелевантного случая присутствия дубликатов. Поэтому следует, вероятно, реализовать дополнительную функцию, которая детектирует *только* дубликаты. И почему бы в этом случае не оставить isSimple в исходном варианте.
Мда, непонятная ситуация, будем надеяться, что следующие сообщения несколько прояснят ситуацию - почему же все-таки дублирующиеся точки - топологически иррелевантны.
Andrea Peri писал(а): Для мультиточек (по OGC):
>..
>Мультиточка проста если никакие две точки не совпадают (не имеют одинаковые X и Y координаты)
>

Для кривых:

>..
>Кривая считается простой, если она не проходит через некоторую точку дважды, за исключением своих начальных и конечных точек (Reference [1], section 3.12.7.3):
>∀ c ∈ Curve, [a, b] = c.Domain, c =: f :[a, b] → ℜ n
>c.IsSimple ⇔ ∀ x1, x2 ∈ [a, b]: [ f(x1)=f(x2) ^ x1<x2] ⇒ [x1=a^x2=b]
>..

Так кривая с соседними дублирующимися точками не удовлетворяет этому условию:
(10 10, 20 20, 20 20, 30 30). Не удовлетворяет ему и кривая, содержащая не последовательные дубли.

Таким образом, я считаю, что в рамках модели простых геометрий - любая геометрия, содержащая дублирующиеся внутренние точки (не обязательно последовательные) - невалидна. Кстати, а почему дублирующися точки топологически иррелевантны?
Martin Davis писал(а): Потому что они топологически не различимы. Я считаю, что некоторая путаница связана из за различия между текстовым и представлением в памяти LineString. В текстовом представлении дубликаты возможны, но с точки зрения топологии они не значимы.
После таких дискуссий стало понятно, что конкретного ответа на вопрос, является ли полигон с повторяющимися узлами корректным согласно OGC скорее всего нет. А вы как считаете?
Spatial is now, more than ever, just another column- The Geometry Column.

Аватара пользователя
SS_Rebelious
Гуру
Сообщения: 1304
Зарегистрирован: 24 фев 2009, 16:51
Репутация: 99
Ваше звание: GIS pro-fan
Откуда: Lahti / Газ-ПУТИНбург
Контактная информация:

Re: ST_IsValid и повторяющиеся узлы

Сообщение SS_Rebelious » 01 апр 2010, 16:21

Оговорюсь, что мне не близок OGS и его понятия валидности объектов (в том смысле, что мне ни горячо, ни холодно от содержащегося в нём определения валидности), но для меня важен здравый смысл и возможность адекватно работать с имеющимся материалом.

Я считаю, что полигон или линия в которой имеются дублирующиеся узлы должны признаваться валидными по умолчанию, либо решение должно быть переложено на плечи оператора, который задаёт условия возможности/невозможности наличия узлов с одинаковыми координатами.

Проясню свою позицию: полигоны являются графическим представлением реальных объектов/явлений существующих в 4-мерном пространстве. У двух узлов могут быть одинаковые координаты X и Y, но различные Z (мы ведь можем работать с объектом на плоскости и не обращать внимание на его высоту, но в следующий момент нам понадобится увидеть его в объёме или информация о Z может появится много позже плановых координат). Не будем забывать и о точности измерения координат - они могут быть достаточно грубы для того, чтобы узлы дублировались. Если по умолчанию признавать полигоны с дублирующимися узлами невалидными, то можно просто-напросто потерять часть информации, при попытке сделать его валидным!

С другой стороны - каждый новый узел требует всё больше ресурсов для обработки объекта, поэтому дублирующиеся узлы негативно сказываются на производительности. В таком случае чистка дублирующихся узлов будет хорошей идеей, если при этом известно, что дубли не несут дополнительную информацию об объекте. Здесь уже ответственность должна лежать на операторе. ПО должно делегировать это решение человеку.
Look for something long enough, and you will find it. Look for something without understanding, and it will find you...
"All paid jobs absorb and degrade the mind." Aristotle
If you take 1 step towards freedom it'll take 2 steps towards you!

Аватара пользователя
Максим Дубинин
MindingMyOwnBusiness
Сообщения: 9128
Зарегистрирован: 06 окт 2003, 20:20
Репутация: 747
Ваше звание: NextGIS
Откуда: Москва
Контактная информация:

Re: ST_IsValid и повторяющиеся узлы

Сообщение Максим Дубинин » 01 апр 2010, 17:26

DR, спасибо что поднял тему, выяснил подробности, а главное, донес их до нас, я уверен, что если еще масса нюансов по которым нужно внести ясность и твой способ - самый эффективный. Я бы задал еще этот вопрос на форуме OGC.

По поводу комментариев:
strk говорит вот что, если у тебя есть две разные точки:
1. 45.12345678, 54.12345678
2. 45.12345679, 54.12345679
То импортировав с обрезанием последнего знака ты получаешь 2 абсолютно идентичные точки.

С практической точки зрения, не представляю, где могут понадобится полностью дублирующиеся узлы.
SS_rebelious, твой пример с разной координатой Z это не идентичные узлы, конечно такие удаляться не должны.
пристегивайтесь, турбулентность прямо по курсу

Voltron
Гуру
Сообщения: 2627
Зарегистрирован: 29 мар 2007, 14:12
Репутация: 34
Откуда: Ukraine

Re: ST_IsValid и повторяющиеся узлы

Сообщение Voltron » 01 апр 2010, 19:22

Интересный вопрос. Неплохо было бы узнать мнение OGC по этому поводу.

Про точки в трехмерном пространстве согласен с sim'ом: если две координаты совпадают, а третья - нет, то это разные точки. Насколько помню, в ArcGIS есть поддержка шейпов с Z-координатой и при проверке геометрии она учитывается наравне со всеми остальными.

Аватара пользователя
SS_Rebelious
Гуру
Сообщения: 1304
Зарегистрирован: 24 фев 2009, 16:51
Репутация: 99
Ваше звание: GIS pro-fan
Откуда: Lahti / Газ-ПУТИНбург
Контактная информация:

Re: ST_IsValid и повторяющиеся узлы

Сообщение SS_Rebelious » 01 апр 2010, 20:01

Вообще-то я говорил про случай, когда сведения об этой самой Z координате по каким-либо причинам изначально отсутствуют в слое, а не когда её значение задано явно.
Look for something long enough, and you will find it. Look for something without understanding, and it will find you...
"All paid jobs absorb and degrade the mind." Aristotle
If you take 1 step towards freedom it'll take 2 steps towards you!

Аватара пользователя
Denis Rykov
Гуру
Сообщения: 3376
Зарегистрирован: 11 апр 2008, 21:09
Репутация: 529
Ваше звание: Author
Контактная информация:

Re: ST_IsValid и повторяющиеся узлы

Сообщение Denis Rykov » 30 авг 2010, 06:23

Начиная с версии 2.0.0 в PostGIS появилась функция ST_RemoveRepeatedPoint, позволяющая удалять повторяющиеся узлы.
Spatial is now, more than ever, just another column- The Geometry Column.

Ответить

Вернуться в «PostGIS/PostgreSQL»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 23 гостя