Domaines connexes ... oopas ?
GérarD
Bonjour.
Je désirerais avoir des illuminations sur un problème de continuité de
territoire (au sens large).
Le but est de savoir si des domaines d'information sont contigus ou pas
(dans la représentation spatiale d'une statistique, entre autres)
Je vais poser plus précisément le problème par un exemple concret (...
MyRqbe lol) :
Pour l'exemple, je me placerai dans un repère orthonormé, facile à
visualiser.
Soit un "univers" de 4 x 4 unités, décomposé en 6 "domaines" polygonaux
irréguliers,
chaque domaine étant défini par le parcours rectiligne de ses points
extérieurs signifiants.
Les définitions de ces domaines sont :
Domaine A : (0,0 ; 0,1 ; 1,1 ; 2,0 ; 0,0)
Domaine B : (0,1 ; 0,4 ; 2,4 ; 2,2 ; 1,1 ; 0,1)
Domaine C : (2,4 ; 4,4 ; 4,1 ; 3,1 ; 3,0 ; 2,0 ; 2,1 ; 3,2 ; 2,3 ; 2,4)
Domaine D : (3,0 ; 3,1 ; 4,1 : 4,0 ; 3,0)
Domaine E : (2,1 ; 2,3 ; 3,2 ; 2,1)
Domaine F : (1,1 ; 2,2 ; 2,0 ; 1,1)
(j'espère que je ne me suis pas gourré ? parce qu'à la main ... !!!)
On remarquera que, si on repère tous les points de coordonnées utiles cités
au moins une fois dans la définition d'un domaine,
certains d'entre eux ne seront pas présents dans la définition de certains
autres domaines, comme par exemple le point (2,2) qui n'est pas noté pour le
domaine E,
malgré qu'il fasse partie de la limite de son domaine, parce parce qu'il
n'est pas un des "bouts" d'un des segments "signifiants" de définition de ce
domaine.
[ Il y a aussi le problème de la connectivité reconnue où non entre le
domaine A et le domaine C, parce que situés en coin l'un de l'autre.
Je ne suis pas le décisionnaire en cette matière, et donc traiterai les deux
cas ultérieurement :o)) ]
Donc dans mon exemple, voulant générer un tableau donnant en entrée, pour
chaque domaine, la liste de ceux qui lui sont contigus
(ou connectés selon le vocable courant), je désirerais obtenir le résultat
suivant (s'il n'y a pas d'erreurs) :
Tab(1,1) : "A" Tab (1,2) = "B,F"
Tab(1,2) : "B" Tab (2,2) = "A,C,E,F"
Tab(1,3) : "C" Tab (3,2) = "B,D,E"
Tab(1,4) : "D" Tab (4,2) = "C"
Tab(1,5) : "E" Tab (5,2) = "B,C,F"
Tab(1,6) : "F" Tab (6,2) = "A,B,C,E"
Bon, "dans la vie réelle", et c'est pourquoi je me suis adressé à vous,
l'univers en question a à peu près une dimension de 400000 x 400000 unités ;
le nombre de domaines est de ~ 200 / 1200 (selon la résolution choisie),
la longueur des parcours de définition de chacun des domaines avoisine les
1000 points, (bon y'en a à 50 mais c'est un miracle)
et c'est pourquoi je cherche des solutions me permettant d'échapper à
l'explosion combinatoire.
Pasque la méthode force brute, heu .. j'ai pas les moyens.
De plus (et ce devait être ma deuxième question), certains points (de
définition de domaine) sont modifiables dynamiquement :
comment ajuster les résultats le plus rapidement possible, en évitant
d'avoir à tout recalculer
(problème de l'effet de bord d'une modif, et du minima de recalcul, genre
feuille excel) ?
Et en plus j'ai aussi le cas ou un point n'est pas un point :o), mais un
cercle représentant l'appartenance à une classe (d'un ensemble flou).
Bonjour les segments et les trajectoires limites !, surtout qu'en vrai on
n'est pas en linéaire dans les segments, qui ne sont que conceptuels.
Je vois surtout du cubique.
Enfin bon. La masturbation intello, c'est un marché qui existe encore.
Vala, je ne vous demande pas de faire mon projet, mais j'ai besoin d'un
sérieux coup de main.
Je suis juste un chômiste bénévole en milieu associatif, et je crois que
beaucoup mettent des espoirs sur ... mes gloires passées.
En effet, je traitais efficacement ce genre de problèmes au début de la
CFAO, dont j'ai été un des primo-acteurs il y a ... 35 ans.
Mais malheureusement, la vie faisant son ouvre, pour diverses raisons
(honte, je suis passé à l'info de gestion!)
ma progression dans ce domaine typique a été inexistante (eh oui, Peter was
here ;o) ! );
Je n'ai pas avancé. Et donc maintenant je recule ...
et bien sûr impossible de remettre la main tant sur le coin de mon cerveau
qui, tel une bite, sautait sur tout ce bougeait,
que sur les outils idoines de l'époque que j'ai certainement sauvegardés et
forcément oubliés. Sob.
Bon je ne vais tout de même pas me flageller.
Mon désir du désir de culture reste intact.
Après avoir débuté la rédaction de ce problème, j'ai réfléchi (oui, merci ,
çà m'arrive encore)
et il m'est approximativement revenu une méthode que j'utilisais à l'époque
: (si je ne me trompe pas), que je traduis ci-après :
- Pour chaque domaine :
-
- Pour chaque segment limitrophe de ce domaine
- Parcourir paramétriquement le segment (voir le problème de
l'ajustage du pas)
- Pour chaque point déterminé par le pas, créer un
vecteur et faire un produit mixte avec ... (je ne me rappelle plus quoi !)
- Selon le résultat négatif, nul ou positif, on
détermine si le point est à l'intérieur, à l'extérieur ou à la limite ;
-- (dans mon cas, c'est la limite qui m'interpelle)
- Si (dans ce qui m'intéresse) on est sur la
limite, var_connexion_ de ces _domaines = 1
- inscription itérative en table de la connexion
trouvée (ch=ch.+','+ str(asc(n)))
- exit loop diverses et toutes ces sortes de
choses
- Sinon, boucle ALL
- après on élimine les doublons (provenant de la commutativité de la
fonction testée) dans chaque chaîne du tableau résultant.
(ah ça facile j'ai un jeu d'enfer de traitement des chaînes ... ué c'est
sous VFP mébon).
Bon j'ai simplifié à l'extrême, mais je voudrais savoir, me planté-jé, ou
bien dans quel état j'erre ?
S'il y a des algo récents permettant d'améliorer la chose, je suis preneur !
Merci d'avance pour vos pistes.
Gérard.
Jean-Marc Bourguet
[...]
Je mettrais tous les segments constituants tes frontières de région dans
une structure de donnée à accès spacial (R-Tree, KD-tree, QuadTree...).
Ensuite, je ferais une boucle sur tous les sommets. Je ferais une
recherche des segments présents dans un intervalle autour du sommet courant
(Sc, Spc et Ssc étant les sommets précédant et suivant le sommet courant)
(la taille de l'intervalle dépend de l'incertitude sur la position). La
recherche peut retourner
- des sommets. St étant un sommet trouvé, Spt et Sst les sommets suivant
et précédant. Les régions ont une frontière commune si Spc ou Ssc est sur
St-Spt ou sur St-Sst, ou si Spt ou Sst est sur Sc-Spc ou sur Sc-Ssc.
- des segments (St1-St2). Les régions ont une frontière commune si Spc ou
Ssc est aussi sur St1-St2, ou si St1 ou St2 est sur Sc-Spc ou sur Sc-Ssc.
Temps d'exécution: batir la structure plus un nombre de recherche dedans
proportionnel aux nombres de points. Je doute qu'il y a moyen de faire
beaucoup mieux.
A+
--
Jean-Marc
Site de usenet-fr: http://www.usenet-fr.news.eu.org
GérarD
news:874oxoj...@news.bourguet.org...
Désolé pour le retard à ma réponse, je n'étais pas trop disponible.
Merci pour ces idées.
Je n'avais pas entendu parler des r-tree et consorts, mais il me semble,
après une rapide lecture sur le sujet, que c'est quelque chose du même genre
qu'on utilisait empiriquement déjà autrefois pour gérer les problèmes
d'optimisation spatiale (genre comment mettre le plus de palettes en bois de
formats divers dans un camion, et comment organiser ces camions pour faire
le moins de tournées quand on a un certain nombre de clients à livrer ; on
avait créé effectivement des structures de données assez particulières, va
falloir que je me replonge dans des vieux documents (que je ne suis même pas
censé encore posséder), pour éviter de refaire le monde, et adapter le tout
à l'outil dont je dispose : VFP (monde xbase, requêtage puissant, mais
gestion de matrices inexistant)).
J'ai pensé ajouter une étape d'élagage discriminante : révéler les
non-connexions évidentes (genre module utilisé pour le rafraichissement des
écrans, ou méthode utilisée par Ajax). Il est possible rapidement de
calculer les extrémums en x et y de n'importe quelle zone, et de générer un
rectangle de recouvrement correspondant. Les zones dont les rectangles de
recouvrement n'ont pas de surface commune (et çà c'est facile et rapide)
seront d'office déclarés non connectables et exclus de la liste de recherche
de contigüité quand on est sur un sommet N.
GérarD.