26. Dimensionsutvidgad 9-intersektionell modell

”Dimensionally Extended 9-Intersection Model” (DE9IM) är ett ramverk för modellering av hur två spatiala objekt interagerar.

För det första har varje spatialt objekt:

• En interiör

• En gräns

• En exteriör

För polygoner är insidan, gränsen och utsidan uppenbara:

Insidan är den del som avgränsas av ringarna, gränsen är själva ringarna och utsidan är allt annat i planet.

För linjära objekt är interiör, gräns och exteriör mindre välkända:

Insidan är den del av linjen som avgränsas av ändarna, gränsen är ändarna på den linjära funktionen och utsidan är allt annat i planet.

För punkter är det ännu konstigare: det inre är punkten, gränsen är den tomma mängden och det yttre är allt annat i planet.

Med hjälp av dessa definitioner av interiör, exteriör och gräns kan relationerna mellan varje par av spatiala egenskaper karakteriseras med hjälp av dimensionaliteten hos de nio möjliga korsningspunkterna mellan interiörerna/gränserna/exteriörerna hos ett par av objekt.

För polygonerna i exemplet ovan är korsningspunkten mellan interiörerna ett 2-dimensionellt område, så den delen av matrisen fylls i med en ”2”. Gränserna skärs endast i punkter, som är nolldimensionella, så den delen av matrisen fylls i med en 0.

När det inte finns någon korsningspunkt mellan komponenterna fylls rutan i matrisen med ett ”F”.

Här är ett annat exempel, där en linjestring delvis går in i en polygon:

DE9IM-matrisen för interaktionen är denna:

Observera att gränserna för de två objekten faktiskt inte korsar varandra alls (linjens slutpunkt interagerar med polygonens inre, inte med gränsen, och vice versa), så B/B-cellen fylls i med ett ”F”.

Även om det är roligt att visuellt fylla i DE9IM-matriser, skulle det vara trevligt om en dator kunde göra det, och det är vad ST_Relate-funktionen är till för.

Det föregående exemplet kan förenklas med en enkel ruta och linje, med samma spatiala förhållande som vår polygon och linjestring:

Och vi kan generera DE9IM-informationen i SQL:

SELECT ST_Relate(
         'LINESTRING(0 0, 2 0)',
         'POLYGON((1 -1, 1 1, 3 1, 3 -1, 1 -1))'
       );

Svaret (1010F0212) är detsamma som vi beräknade visuellt, men returneras som en sträng med 9 tecken, med första raden, andra raden och tredje raden i tabellen sammanfogade.

101
0F0
212

DE9IM-matrisernas styrka ligger dock inte i att generera dem, utan i att använda dem som en matchningsnyckel för att hitta geometrier med mycket specifika relationer till varandra.

CREATE TABLE lakes ( id serial primary key, geom geometry );
CREATE TABLE docks ( id serial primary key, good boolean, geom geometry );

INSERT INTO lakes ( geom )
  VALUES ( 'POLYGON ((100 200, 140 230, 180 310, 280 310, 390 270, 400 210, 320 140, 215 141, 150 170, 100 200))');

INSERT INTO docks ( geom, good )
  VALUES
        ('LINESTRING (170 290, 205 272)',true),
        ('LINESTRING (120 215, 176 197)',true),
        ('LINESTRING (290 260, 340 250)',false),
        ('LINESTRING (350 300, 400 320)',false),
        ('LINESTRING (370 230, 420 240)',false),
        ('LINESTRING (370 180, 390 160)',false);

Anta att vi har en datamodell som innehåller Sjöar och Dockor, och anta vidare att dockor måste vara inuti sjöar och måste röra gränsen för deras innehållande sjö i ena änden. Kan vi hitta alla bryggor i vår databas som följer denna regel?

Våra legala bryggor har följande egenskaper:

• Deras interiörer har en linjär (1D) korsningspunkt med sjöns interiör

• Deras gränser har en punkt (0D) korsningspunkt med sjöns inre

• Deras gränser har också en punkt (0D) som skär sjöns gräns

• Deras interiörer har ingen korsningspunkt (F) med sjöns exteriör

Så deras DE9IM-matris ser ut så här:

Så för att hitta alla lagliga bryggor skulle vi vilja hitta alla bryggor som korsar sjöar (en superuppsättning av potentiella kandidater som vi använder för vår länknyckel) och sedan hitta alla bryggor i den uppsättningen som har det lagliga relateringsmönstret.

SELECT docks.*
FROM docks JOIN lakes ON ST_Intersects(docks.geom, lakes.geom)
WHERE ST_Relate(docks.geom, lakes.geom, '1FF00F212');

-- Answer: our two good docks

Observera användningen av treparameterversionen av ST_Relate, som returnerar true om mönstret matchar eller false om det inte gör det. För ett helt definierat mönster som det här behövs inte versionen med tre parametrar - vi kunde bara ha använt en stränglikhetsoperator.

För lösare mönstersökningar tillåter dock de tre parametrarna ersättningstecken i mönstersträngen:

• ”*” betyder ”alla värden i den här cellen är acceptabla”

• ”T” betyder ”alla icke-falska värden (0, 1 eller 2) är acceptabla”

En möjlig brygga som vi inte inkluderade i vårt grafiska exempel är en brygga med en tvådimensionell korsningspunkt med sjögränsen:

INSERT INTO docks ( geom, good )
  VALUES ('LINESTRING (140 230, 150 250, 210 230)',true);

Om vi ska inkludera detta fall i vår uppsättning av ”lagliga” bryggor måste vi ändra relationsmönstret i vår fråga. I synnerhet kan korsningspunkten mellan bryggans inre sjögräns nu vara antingen 1 (vårt nya fall) eller F (vårt ursprungliga fall). Så vi använder ”*” i mönstret.

Och SQL ser ut så här:

SELECT docks.*
FROM docks JOIN lakes ON ST_Intersects(docks.geom, lakes.geom)
WHERE ST_Relate(docks.geom, lakes.geom, '1*F00F212');

-- Answer: our (now) three good docks

Bekräfta att den striktare SQL från föregående exempel inte returnerar den nya dockan.

26.1. Testning av datakvalitet

TIGER-data kvalitetskontrolleras noggrant när de tas fram, så vi förväntar oss att våra data uppfyller strikta standarder. Till exempel: inget folkbokföringsblock får överlappa något annat folkbokföringsblock. Kan vi testa för det?

Säkert!

SELECT a.gid, b.gid
FROM nyc_census_blocks a, nyc_census_blocks b
WHERE ST_Intersects(a.geom, b.geom)
  AND ST_Relate(a.geom, b.geom, '2********')
  AND a.gid != b.gid
LIMIT 10;

-- Answer: 10, there's some funny business

På samma sätt förväntar vi oss att all vägdata är ändkodad. Det vill säga att vi förväntar oss att korsningar endast sker i ändarna av linjerna, inte i mittpunkterna.

Vi kan testa det genom att leta efter gator som korsar varandra (så att vi har en skarv) men där skärningen mellan gränserna inte är nolldimensionell (det vill säga att ändpunkterna inte rör vid varandra):

SELECT a.gid, b.gid
FROM nyc_streets a, nyc_streets b
WHERE ST_Intersects(a.geom, b.geom)
  AND NOT ST_Relate(a.geom, b.geom, '****0****')
  AND a.gid != b.gid
LIMIT 10;

-- Answer: This happens, so the data is not end-noded.

26.1.1. Funktionslista

ST_Relate(geometri A, geometri B): Returnerar en textsträng som representerar DE9IM-relationen mellan geometrierna.