23. Валідність

У 90% випадків відповідь на питання «чому мій запит видає помилку «TopologyException»» звучить так: «one or more of the inputs are invalid. Це викликає питання: що означає «invalid» і чому нам слід про це турбуватися?

23.1. Що таке валідність

Валідність є найважливішою для полігонів, які визначають обмежені області і вимагають значної структури. Лінії є дуже простими і не можуть бути недійсними, так само як і точки.

Деякі правила валідності полігонів здаються очевидними, а інші — довільними (і насправді є довільними).

  • Полігонми повинні бути замкненими.

  • Кільця, що визначають отвори, повинні знаходитися всередині кілець, що визначають зовнішні межі.

  • Кільця не можуть перетинатися між собою (вони не можуть ні стикатися, ні перетинатися).

  • Кільця не можуть торкатися інших кілець, за винятком однієї точки.

  • Елементи багатокутників не можуть торкатися один одного.

Останні три правила належать до категорії довільних. Існують інші способи визначення багатокутників, які є рівноцінними, але вищезазначені правила використовуються стандартом OGC SFSQL, якому відповідає PostGIS.

Причина, чому правила є важливими, полягає в тому, що алгоритми для обчислень з геометрією залежать від узгодженої структури вхідних даних. Можна створити алгоритми, які не роблять жодних структурних припущень, але такі процедури зазвичай працюють дуже повільно, оскільки першим кроком у будь-якій процедурі без попередньої структури є аналіз вхідних даних і побудова структури в них.

Ось приклад того, чому структура має значення. Цей багатокутник є некоректним:

POLYGON((0 0, 0 1, 2 1, 2 2, 1 2, 1 0, 0 0));

На цій діаграмі можна трохи чіткіше побачити помилку:

_images/figure_eight.png

Зовнішнє кільце насправді має форму «вісімки» з самоперетином посередині. Зверніть увагу, що графічні процедури успішно відображають заповнення полігону, тож візуально він виглядає як «площа»: два квадрати розміром один на один, тобто загальна площа — дві одиниці.

Давайте подивимося, яку площу нашого багатокутника визначає база даних:

SELECT ST_Area(ST_GeometryFromText(
         'POLYGON((0 0, 0 1, 1 1, 2 1, 2 2, 1 2, 1 1, 1 0, 0 0))'
       ));

 st_area
---------
       0

Що тут відбувається? Алгоритм, який обчислює площу, передбачає, що кільця не мають самоперетинів. «Правильне» кільце завжди має площу, обмежену (внутрішню частину), розташовану з одного боку від обмежувальної лінії (неважливо, з якого саме боку, головне — що лише з одного). Однак у нашій (неправильно побудованій) «вісімці» обмежена площа для однієї петлі знаходиться праворуч від лінії, а для іншої — ліворуч. Це призводить до того, що обчислені площі для кожної петлі взаємно компенсуються (одна виходить як +1, інша як −1), і в результаті маємо «нульову площу».

23.2. Визначення валідності

У попередньому прикладі ми мали один багатокутник, про який знали, що він є недійсним. Як виявити недійсність у таблиці з мільйонами геометрій? За допомогою функції ST_IsValid(geometry). Застосувавши її до нашої вісімки, ми отримуємо швидку відповідь:

SELECT ST_IsValid(ST_GeometryFromText(
         'POLYGON((0 0, 0 1, 1 1, 2 1, 2 2, 1 2, 1 1, 1 0, 0 0))'
       ));

f

Тепер ми знаємо, що об’єкт є недійсним, але не знаємо, чому. Ми можемо використати функцію ST_IsValidReason(geometry), щоб з’ясувати причину недійсності:

SELECT ST_IsValidReason(ST_GeometryFromText(
         'POLYGON((0 0, 0 1, 1 1, 2 1, 2 2, 1 2, 1 1, 1 0, 0 0))'
       ));

Self-intersection[1 1]

Зверніть увагу, що крім причини (самоперетин) також повертається місце розташування недопустимого елемента (координати (1 1)).

Ми також можемо скористатися функцією :command:ST_IsValid(geometry), щоб перевірити наші таблиці:

-- Find all the invalid polygons and what their problem is
SELECT name, boroname, ST_IsValidReason(geom)
FROM nyc_neighborhoods
WHERE NOT ST_IsValid(geom);

          name           |   boroname    |          st_isvalidreason
-------------------------+---------------+-----------------------------------------
 Howard Beach            | Queens        | Self-intersection[597264.08 4499924.54]
 Corona                  | Queens        | Self-intersection[595483.05 4513817.95]
 Steinway                | Queens        | Self-intersection[593545.57 4514735.20]
 Red Hook                | Brooklyn      | Self-intersection[584306.82 4502360.51]

23.3. Виправлення некоректної геометрії

Виправлення некоректної геометрії передбачає розбиття полігону на його найпростіші структури (кільця), перевірку, що кільця відповідають правилам валідації, а потім побудову нових полігонів, що дотримуються правил вкладення/замикання кілець. Часто результати бувають інтуїтивно зрозумілими, але у випадку надто «погано» сформованих вхідних даних валідні вихідні геометрії можуть не відповідати вашому уявленню про те, як вони мали б виглядати. У новіших версіях PostGIS є кілька алгоритмів для відновлення геометрій — уважно прочитайте сторінку довідки ST_MakeValid і виберіть той, який вам підходить.

Наприклад, ось класичний випадок некоректної геометрії — «банановий полігон» — одне кільце, яке охоплює площу, але вигинається так, що торкається само себе, утворюючи «дірку», яка насправді не є діркою.

POLYGON((0 0, 2 0, 1 1, 2 2, 3 1, 2 0, 4 0, 4 4, 0 4, 0 0))
_images/banana.png

Виконання команди ST_MakeValid на полігоні повертає валідний полігон OGC, що складається з зовнішнього та внутрішнього кілець, які стикаються в одній точці.

SELECT ST_AsText(
         ST_MakeValid(
           ST_GeometryFromText('POLYGON((0 0, 2 0, 1 1, 2 2, 3 1, 2 0, 4 0, 4 4, 0 4, 0 0))')
         )
       );

POLYGON((0 0,0 4,4 4,4 0,2 0,0 0),(2 0,3 1,2 2,1 1,2 0))

Примітка

«Банановий полігон» (або «інверсна оболонка») — це випадок, коли топологічна модель валідної геометрії за :term:OGC та модель, яку внутрішньо використовує ESRI, відрізняються. Модель ESRI вважає кільця, що торкаються, некоректними й надає перевагу банановій формі для такого типу фігур. Модель OGC — навпаки. Жодна з них не є «правильною» чи «неправильною» — це просто різні способи моделювання однієї й тієї ж ситуації.

23.4. Масове виправлення геометрії

Ось приклад SQL-запиту, який позначає некоректні геометрії для перевірки та одночасно додає виправлену версію до таблиці.

-- Column for old invalid form
ALTER TABLE nyc_neighborhoods
  ADD COLUMN geom_invalid geometry
  DEFAULT NULL;

-- Fix invalid and save the original
UPDATE nyc_neighborhoods
  SET geom = ST_MakeValid(geom),
      geom_invalid = geom
  WHERE NOT ST_IsValid(geom);

-- Review the invalid cases
SELECT geom, ST_IsValidReason(geom_invalid)
  FROM nyc_neighborhoods
  WHERE geom_invalid IS NOT NULL;

Хорошим інструментом для візуального виправлення некоректної геометрії є OpenJump (http://openjump.org), який містить функцію перевірки коректності за шляхом Tools->QA->Validate Selected Layers.

23.5. Список функцій

ST_IsValid(geometry A) <http://postgis.net/docs/ST_IsValid.html>_: Повертає булеве значення, яке вказує, чи є геометрія коректною.

ST_IsValidReason(geometry A) <http://postgis.net/docs/ST_IsValidReason.html>_: Повертає текстовий рядок із причиною некоректності та координатою, де вона виникає.

ST_MakeValid(геометрія A): Повертає геометрію, реконструйовану відповідно до правил валідності.