#1 Wed 12 June 2013 12:00
- sigdu80
- Participant actif
- Date d'inscription: 2 Sep 2010
- Messages: 112
Question complexité geom
Bonjour à tous,
j'avais posé des questions il y a quelque temps sur l'optimisation de temps de calcul pour des tests d'intersection (cf http://georezo.net/forum/viewtopic.php?id=83189).
Le map dicing avait été la solution qui m'a bien aidé.
A présent, j'ai une table de références qui a une étendue bien plus grande (à l'échelle d'un département).
J'ai crée quelque parcelles et testé si elle faisait intersection avec ces tables et si oui, de récupérer le geom d'intersection.
Les tests ont donné des temps de calcul très rapides (< 0.01s).
Mais pour faire les tests à fond, il faudrait que je teste en mettant des parcelles un peu partout, non ? Ce qui paraît fastidieux et très long.
Dans le doute, je voulais mieux comprendre ce qui joue sur les temps de calcul d'intersection.
Il était évoqué les polygones dégénérés (type croissant de lune).
Est-ce dû à un grand nombre de points couplé à une grande superficie ?
Pour les détecter, comment faîtes-vous ?
- En SQL, avec une fonction qui donne les nb de points du polygone, la superficie, ...
- En QGIS, une fonction qui aide à les voir ?
Est-il conseillé dans tous les cas, d'appliquer un map dicing (100*100) ?
Merci d'avance, bon appétit.
Dernière modification par sigdu80 (Wed 12 June 2013 12:03)
Hors ligne
#2 Thu 13 June 2013 13:46
- Cornet Jérémie
- Participant assidu
- Lieu: Nouméa
- Date d'inscription: 6 Apr 2008
- Messages: 229
Re: Question complexité geom
Bonjour,
Le temps de calcul est énorme car les index géométriques (GIST) ne peuvent ici être exploités à fond.
En effet, l'index géométrique est le rectangle englobant de la géométrie. Du coup, vu que tes géométries étaient extrêmement découpées, le rectangle englobant ne permettait pas vraiment de faire un pré-filtrage.
Donc le map dicing est inutile si tes polygones sont classiques (ce qui est généralement le cas pour des couches parcellaires).
Est-ce dû à un grand nombre de points couplé à une grande superficie ?
Non, c'est vraiment du à la forme qui rend l'index géométrique beaucoup moins utile.
Pour répérer les polygones qui risquent de poser problème, un critère sur la surface et un critère sur la forme (le rapport périmètre/racine(surface) par exemple).
Hors ligne
#3 Thu 13 June 2013 18:15
- sigdu80
- Participant actif
- Date d'inscription: 2 Sep 2010
- Messages: 112
Re: Question complexité geom
Bonjour Jérémie,
D'accord, merci.
Les polygones sont parfois atypiques car ce sont des geom d'informations, pas forcément des couches parcellaires.
Voilà, cela me permet de détecter si je dois faire un map dicing sur certains polygones !
Par exemple, le geom qui m'a posé problème dans l'autre sujet a un rapport de 304 !
D'autre sont entre 70 et 20, ce qui doit être acceptable non ?
As-tu une idée d'un seuil limite du rapport "périmètre/racine carrée(surface)" au dessus duquel c'est aberrant et du coup qu'il faudrait faire un map dicing ?
Bonne fin de journée, merci encore.
Hors ligne
#4 Fri 14 June 2013 19:40
- Cornet Jérémie
- Participant assidu
- Lieu: Nouméa
- Date d'inscription: 6 Apr 2008
- Messages: 229
Re: Question complexité geom
Tu as des choses intéressantes sur les indices de forme dans cette discussion :
http://georezo.net/forum/viewtopic.php?id=61969
Sinon, je viens de penser à un truc tout bête mais puisque tu cherches en fait à caractériser l'efficacité de l'index géométrique, un bête rapport
Code:
surface du polygone / surface du rectangle englobant
te donnera un indice entre 0 et 1 immédiatement compréhensible.
Cependant, n'oublie pas de prendre en compte la surface qui a aussi son importance. Un polygone très complexe mais "tout petit" par rapport aux polygones à intersecter ne rallongera pas trop le calcul (puisque l'index permettra de préfiltrer efficacement).
Dernière modification par Cornet Jérémie (Fri 14 June 2013 19:43)
Hors ligne
#5 Mon 17 June 2013 18:10
- sigdu80
- Participant actif
- Date d'inscription: 2 Sep 2010
- Messages: 112
Re: Question complexité geom
Bonjour Jérémie,
merci encore.
Chaque formule donne des indications intéressantes et différentes.
1) bien noté pour l'indice de concavité : surface(geom) / surface(bbox(geom)).
Cette indice permet de voir si la bbox fait gagner du temps dans le pré-filtrage.
2) périmètre(geom) / racineCarré(surface(geom))
Cette formule met en avant des geoms très étendus mais ayant peu de surface.
Une 3ème chose auquel je pense serait de voir les plus grandes aires des bbox des geoms.
Un map dicing serait à adopter pour les plus grandes aires de bbox des geoms qui ont leur indice de la formule du point 2), assez élevé (encore faut-il que ces geoms-là soit répartie sur plus qu'une case de la grille pour que le map dicing apporte quelque chose évidemment).
Après, faire du cas par cas en utilisant le point 2) et surtout le point 1).
Que penses-tu de cela ?
Dernière modification par sigdu80 (Mon 17 June 2013 18:20)
Hors ligne
