23. Validitet

I 90% o av fallen är svaret på frågan ”varför ger min fråga mig ett ’TopologyException’-fel” ”en eller flera av ingångarna är ogiltiga”. Vilket väcker frågan: vad innebär det att vara ogiltig, och varför ska vi bry oss?

23.1. Vad är validitet

Validitet är viktigast för polygoner, som definierar avgränsade områden och kräver en hel del struktur. Linjer är mycket enkla och kan inte vara ogiltiga, inte heller punkter.

Vissa av reglerna för polygoners giltighet känns självklara, medan andra känns godtyckliga (och faktiskt är godtyckliga).

  • Polygonringar måste stängas.

  • Ringar som definierar hål bör vara inuti ringar som definierar yttre gränser.

  • Ringar får inte korsa sig själva (de får varken röra vid eller korsa sig själva).

  • Ringarna får inte röra vid andra ringar, utom vid en punkt.

  • Element i multipolygoner får inte röra vid varandra.

De tre sista reglerna är i kategorin godtyckliga. Det finns andra sätt att definiera polygoner som är lika självkonsistenta men reglerna ovan är de som används av OGC SFSQL-standarden som PostGIS följer.

Anledningen till att reglerna är viktiga är att algoritmer för geometriberäkningar är beroende av en konsekvent struktur i indata. Det är möjligt att bygga algoritmer som inte har några strukturella antaganden, men dessa rutiner tenderar att vara mycket långsamma, eftersom det första steget i en strukturfri rutin är att analysera indata och bygga in struktur i dem.

Här är ett exempel på varför strukturen är viktig. Den här polygonen är ogiltig:

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

Du kan se ogiltigheten lite tydligare i det här diagrammet:

_images/figure_eight.png

Den yttre ringen är egentligen en åtta, med en självkorsande punkt i mitten. Observera att de grafiska rutinerna lyckas rendera polygonfyllningen, så att det visuellt ser ut som en ”yta”: två rutor med en enhet, så en total yta på två ytenheter.

Låt oss se vad databasen tror att ytan på vår polygon är:

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

Vad är det som händer här? Algoritmen som beräknar arean förutsätter att ringar inte skär varandra. En välskött ring kommer alltid att ha det område som avgränsas (det inre) på ena sidan av begränsningslinjen (det spelar ingen roll vilken sida, bara det är på en sida). Men i vår (illa skötta) åtta ligger det avgränsade området till höger om linjen för den ena loben och till vänster för den andra. Detta leder till att de ytor som beräknas för varje lob tar ut varandra (den ena blir 1, den andra -1), därav resultatet ”noll yta”.

23.2. Detektering av validitet

I det föregående exemplet hade vi en polygon som vi visste var ogiltig. Hur upptäcker vi ogiltighet i en tabell med miljontals geometrier? Med funktionen ST_IsValid(geometry). När den används mot vår åttonde figur får vi ett snabbt svar:

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

Nu vet vi att funktionen är ogiltig, men vi vet inte varför. Vi kan använda funktionen ST_IsValidReason(geometry) för att ta reda på källan till ogiltigheten:

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]

Observera att förutom orsaken (självskärning) returneras även platsen för invaliditeten (koordinat (1 1)).

Vi kan också använda funktionen ST_IsValid(geometry) för att testa våra tabeller:

-- 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. Reparation av invaliditet

Reparation av ogiltighet innebär att en polygon strippas ner till sina enklaste strukturer (ringar), att ringarna följer giltighetsreglerna och att nya polygoner byggs upp som följer reglerna för inneslutning av ringar. Ofta är resultaten intuitiva, men i fallet med extremt olämpliga indata kanske de giltiga utdata inte överensstämmer med din intuition om hur de borde se ut. De senaste versionerna av PostGIS innehåller olika algoritmer för geometrireparation: läs manualsidan noggrant och välj den du tycker bäst om.

Här är till exempel en klassisk ogiltighet - ”bananpolygonen” - en enda ring som omsluter ett område men böjer sig runt för att röra vid sig själv och lämnar ett ”hål” som egentligen inte är ett hål.

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

Om du kör ST_MakeValid på polygonen får du tillbaka en giltig OGC-polygon, bestående av en yttre och en inre ring som berör varandra i en punkt.

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))

Observera

”Bananpolygonen” (eller ”det inverterade skalet”) är ett fall där OGC topologimodell för giltig geometri och den modell som används internt av ESRI skiljer sig åt. ESRI-modellen anser att ringar som rör vid varandra är ogiltiga och föredrar bananformen för denna typ av form. OGC-modellen är den omvända. Ingen av dem är ”korrekt”, de är bara olika sätt att modellera samma situation.

23.4. Reparation av bulkvaliditet

Här är ett exempel på SQL för att flagga ogiltiga geometrier för granskning samtidigt som en reparerad version läggs till i tabellen.

-- 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;

Ett bra verktyg för att visuellt reparera ogiltig geometri är OpenJump (http://openjump.org) som innehåller en valideringsrutin under Tools->QA->Validate Selected Layers.

23.5. Funktionslista

ST_IsValid(geometri A): Returnerar en boolean som anger om geometrin är giltig.

ST_IsValidReason(geometri A): Returnerar en textsträng med orsaken till ogiltigheten och en koordinat för ogiltigheten.

ST_MakeValid(geometri A): Returnerar en geometri som är omkonstruerad för att följa giltighetsreglerna.