SpatiaLite Cookbook

	Recette #12 Voisins
Février 2011

Table des matières

Le problème

A première vue, chaque Local Council partage une limite en commun avec un voisin:
[ce n'est pas une règle absolue: e.g. petites îles].
On va utiliser SQL afin d'identifier les couples de Local Councils adjacents.
Afin d'ajouter un peu de complexité, nous allons nous intéresser uniquement aux Local Councils voisins la TOSCANE (Région).

Tuscan Local Council	Tuscan County	Neighbour LC	County	Région
ANGHIARI	AREZZO	CITERNA	PERUGIA	UMBRIA
AREZZO	AREZZO	MONTE SANTA MARIA TIBERINA	PERUGIA	UMBRIA
BIBBIENA	AREZZO	BAGNO DI ROMAGNA	FORLI' - CESENA	EMILIA-ROMAGNA
CHIUSI DELLA VERNA	AREZZO	BAGNO DI ROMAGNA	FORLI' - CESENA	EMILIA-ROMAGNA
CHIUSI DELLA VERNA	AREZZO	VERGHERETO	FORLI' - CESENA	EMILIA-ROMAGNA
...	...	...	...	...

SELECT lc1.lc_name AS "Local Council",
lc2.lc_name AS "Neighbour"
FROM local_councils AS lc1,
local_councils AS lc2
WHERE ST_Touches(lc1.geometry, lc2.geometry);

Cette première requête est simple:

la fonction ST_Touches(geom1, geom2) évalue la relation spatiale existant entre chaque couple de Local Councils.
la table local_council est scannée deux fois, afin de réaliser la jointure;
En d'autres mots, cette requête permet d'évaluer chaque Local Council à un autre, de manière permutative.
On doit mettre en place deux alias (AS lc1 / AS lc2) pour identifier de façon non ambiguë les Local Councils.

Cependant, une approche aussi simpliste implique plusieurs problèmes:

cette requête va sûrement retourner un résultat correct: mais le temps de calcul sera long.
[trop long].
l'explication est relativement simple: l'évaluation ST_Touches() implique un grand nombre de calculs complexes, et représente une étape très lourde
logiquement on devrait répéter cette opération sur les millions de couples possibles.
conclusion: répéter des millions de fois une grosse opération aboutit à une requête extrêmement lente !

SELECT lc1.lc_name AS "Local Council",
  lc2.lc_name AS "Neighour"
FROM local_councils AS lc1,
  local_councils AS lc2
WHERE lc2.ROWID IN (
  SELECT pkid
    FROM idx_local_councils_geometry
    WHERE pkid MATCH RTreeIntersects(
      MbrMinX(lc1.geometry),
      MbrMinY(lc1.geometry),
      MbrMaxX(lc1.geometry),
      MbrMaxY(lc1.geometry)));

Heureusement, on peut réaliser ces requêtes spatiales d'une manière plus rapide et efficace:

on va utiliser l'Index Spatial [aka R*Tree]
cela va rajouter de la complexité à notre code SQL, mais permettra un gain de temps non négligeable.
Comment ça marche: le R*Tree est scanné dans un premier temps, afin d'évaluer le Minimum Bounding Rectangles [MBRs] des deux géométries:
- cette étape s'effectue très rapidement, et permet d'écarter de nombreux couples pour qui ont est sûr qu'ils ne partagent pas une limite commune.
- Ainsi, le nombre d'opérations impliquant ST_Touches() sera frottement réduit.
- Tout ceci réduit grandement le temps de calcul global.
Au niveau syntaxique, l'utilisation de l'index spatial nécessite simplement l'utilisation d'une sous requête:
- L' Index Spatial R*Tree est stocké dans une table séparée.
- les noms des tables sont étroitement liés: l'Index Spatial correspondant à la table myTbl et à la colonne géométrique myGeom se nomme idx_myTbl_myGeom.
- la clause MATCH RTreeIntersects() est utilisée afin de sélectionner rapidement toute géométrie intéressante, en évaluant simplement son MBR.
- MbrMinX() etc... sont utilisés afin d'identifier les points extrêmes du MBR filtré.

Voici ce qui se passe étape par étape:

un élément Géométrique est choisi dans la première instance de la table local_councils (lc1.geometry)
Puis l'index spatial R*Tree est scanné afin d'identifier tous les objets géométriques de la deuxième instance de la table local_councils ( lc2.geometry)
Seuls les objets satisfaisant la contrainte (intersection des MBR) seront sélectionnes via l'Index Spatial.
enfin, ST_Touches() sera évalué: mais uniquement sur les objets pré-filtrés.

SELECT lc1.lc_name AS "Tuscan Local Council",
  c1.county_name AS "Tuscan County",
  lc2.lc_name AS "Neighbour LC",
  c2.county_name AS County,
  r2.region_name AS Région
FROM local_councils AS lc1,
  local_councils AS lc2,
  counties AS c1,
  counties AS c2,
  regions AS r1,
  regions AS r2
WHERE c1.county_id = lc1.county_id
  AND c2.county_id = lc2.county_id
  AND r1.region_id = c1.region_id
  AND r2.region_id = c2.region_id
  AND r1.region_name LIKE 'toscana'
  AND r1.region_id <> r2.region_id
  AND ST_Touches(lc1.geometry, lc2.geometry)
  AND lc2.ROWID IN (
    SELECT pkid
      FROM idx_local_councils_geometry
      WHERE pkid MATCH RTreeIntersects(
        MbrMinX(lc1.geometry),
        MbrMinY(lc1.geometry),
        MbrMaxX(lc1.geometry),
        MbrMaxY(lc1.geometry)))
ORDER BY c1.county_name, lc1.lc_name;

Bien, maintenant que nous avons résolu le sujet de l'Index Spatial, la réécriture de la requête ne pose plus de problèmes
Etant donné qu'il s'agit d'une requète complexe, des informations supplémentaires ne vous feront pas de mal:

on a réaliser deux JOINtures: une entre local_councils et counties, et une autre entre counties et regions
Etant donné que l'on a utilisé deux instances de la table local_councils, il faut réaliser une jointure pour chaque instance
le paramètre r1.region_name LIKE 'toscana' permet de focaliser la recherche de voisins sur la TOSCANE (region).
le paramètre r1.region_id <> r2.region_id permet de s'assurer que seuls les Local Councils non TOSCANs seront pris en compte pour l'évaluation des voisins.
seuls les Local Councils Toscans ayant une limite voisine avec un Local Council non Toscans vont être sélectionnés avec cette requête

SELECT lc1.lc_name AS "Tuscan Local Council",
  c1.county_name AS "Tuscan County",
  lc2.lc_name AS "Neighbour LC",
  c2.county_name AS County,
  r2.region_name AS Région
FROM local_councils AS lc1,
  local_councils AS lc2
JOIN counties AS c1
  ON (c1.county_id = lc1.county_id)
JOIN counties AS c2
  ON (c2.county_id = lc2.county_id)
JOIN regions AS r1
  ON (r1.region_id = c1.region_id)
JOIN regions AS r2
  ON (r2.region_id = c2.region_id)
WHERE r1.region_name LIKE 'toscana'
  AND r1.region_id <> r2.region_id
  AND ST_Touches(lc1.geometry, lc2.geometry)
  AND lc2.ROWID IN (
    SELECT pkid
      FROM idx_local_councils_geometry
      WHERE pkid MATCH RTreeIntersects(
        MbrMinX(lc1.geometry),
        MbrMinY(lc1.geometry),
        MbrMaxX(lc1.geometry),
        MbrMaxY(lc1.geometry)))
ORDER BY c1.county_name, lc1.lc_name;

Même requête, mais avec une syntaxe de JOINture différente.

Réaliser des analyses spatiales n'est pas toujours une tâche facile.
Maîtriser des requêtes SQL complexes n'est pas évident (mais pas impossible).
Optimiser de telles requêtes, afin d'obtenir des réponses rapides requiert un soin et une attention particulière.
Mais le résultat en vaut la chandelle.

Table des matières

	Author: Alessandro Furieri a.furieri@lqt.it Traduced from English By RIVIERE Romain
	This work is licensed under the Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) license.

	Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.