Reprise du message précédent :
Ahhhhh, les archis fous de SQY
 
http://www.leparisien.fr/images/20 [...] 40x280.jpg

Tes polygones sortent d'où ? Tu pourrais pas utiliser un ST_Intersect/ST_Difference  de PostGIS par exemple ( http://postgis.refractions.net/doc [...] ction.html ). Je ne sais pas trop comment ça se comporte si tes géométries sont une collection de polygones par contre...

 
Je plussoie  

je vois pas comment tu atteins n^2 (si n est le nombre de polygones) avec un nombre arbitraire de recouvrement (et pas simplement 2 à chaque fois)

Je crois que vous avez pas compris le pb, j'ai accès à postgis, mais j'ai un nombre arbitraire de recouvrement par zone. genre on jette un tas de polygones les uns sur les autres et il faut partitionner la chose.

De toutes façon la géométrie en info c'est la merde, c'est tout le bonheur des nombres à virgule flottante, mais au carré parce que c'est en 2D, tous les objets ont 36 façons de dégénérer, moi je touche pas à ça sans une bibliothèque bien écrite.

n!

Effectivement, si à chaque intersection tu te crées un grand nombre de petits polygones d'intersection, c'est pas vraiment borné (je crois que c'est borné par la n2 * factorielle du nombre de points moyen par polygone, à vue de nez).

voilà d'où la recherche d'un algo malin pour par re-faire des calculs d'intersection inutiles.

ptain, mais ils sont tous mauvais perdants ou c'est moi ? http://elections.lefigaro.fr/flash [...] tur-pm.php

D'ailleurs, par curiosité. C'est quoi le besoin fonctionnel pour avoir à partitionner ?  
Et quid des recouvrements ? (si un polygone est inclus dans un autre, voir même si un polygone est inclus dans un autre, qui est inclus dans un autre ) ?

c'est juste copé qui se montre plus, maintenant que sarko laisse de la place.

 
Tu commences par tester si y'a intersection entre les polygones 2 à 2 (ce qui est rapide vu que t'as une prépasse avec les bounds), sans calculer l'intersection.
 
Tu construis une graph avec pour sommet les polygons et pour arrêtes les intersections.
 
Tu calcule la liste des cliques maximales du graphe : http://en.wikipedia.org/wiki/Bron% [...] _algorithm
 
Pour chaque clique :
  - Tu calcule les intersections complètes avec un algo +/- naïf (du genre je prends 2 polys, je calcule l'intersection et je remet le tout dans le tas, puis je prends le poly suivant que je teste avec chacun des précédents, etc...) comme tes cliques seront normalement petites ça devrait passer. Tu oublie pas de tagger tes polys générés pour savoir d'ou ils viennent (untel poly = A&B&!C).
  - Dans le graphe, tu remplace le polygone d'un sommet par ce polygone moins tout les autres membres de la clique en cours, et tu annote les arrêtes de graphe pour y mettre le poly correspondant à l'intersection de polygones sommets de l'arrête moins les polygones du reste de la clique en cours. (Si t'as une clique A, B, C, tu auras A&!B&!C, !A&B&!C, !A&!B&C en sommets et A&B&!C, !A&B&C, A&!B&C en arrêtes).
 
Tu récolte tout les polys attachés à ton graph.
 
C'est pas super malin-malin, mais le calcul des cliques est assez simple et ça réduira déjà pas mal la complexité (et probablement la taille du dataset à garder chaud en ram).

calculer l'histogramme d'une carte thématique par exemple. ou son maximum.

Tes données thématiques sont rattachés a des surfaces, mais est ce que ces surfaces  peuvent être réduis en un ou plusieurs  points ( commune centre, quartier,ilot, département,... ) ?
Auquel cas tu n'as plus qu'a rechercher a combien de polygones appartiennent ces points.

non, je n'ai pas une partition naturelle du plan sinon j'en serai pas là, il y aurait zéro intersection et ça ferait 2 mois que j'ai mon maximum.

ça aurai été trop beau

ceci dit, si tu peux te passer du résultat exact , tu peux prendre un point arbitrairement tous les x mètres et calculer les intersections avec les polygones,ce n'est pas cher.

C'est MBDA en mode camouflage ?

Banque    
Tondeuse    
poussière  
aspirateur  
Bière    
 
...ça va, le reste du programme est réalisable.

j'ai réfléchi, mais ça me fait chier, j'ai 3-4 usages du partitionnement exact, alors je me lance.

tu achètes une maison ?

Non, je profite de mes vacances pour faire du nettoyage.
La banque c'est pour faire coucou à la conseillère (et prendre le machin e-carte bleue), j'y étais pas allé depuis 5 ans...

'tain la vache, y'a 17800 intersections.

uniquement deux a deux , ou au total ?

2à2 (la matrice d'adjacence a 2*17800 entrées)

il est à mi-chemin, toujours pas tombé

'tain ce plan d'incident qu'on a, avec un truc pareil, je vois pas pourquoi on se ferait chier à maintenir le site en ligne. C'est à peine si on a pas une procédure pour envoyer les T-shirts au clients lésés.

http://www.wired.com/epicenter/201 [...] is-wallet/ fuck fuck fuck

Ca doit faire bizarre de voir ça à sa fenêtre

 

aye, arrivé

Moi j'ai été voir la mienne aussi (et ça faisait 5 ans aussi, la dernière fois c'était entre les 2 tours des présidentielles de 2007). Je lui ai demandé de me prêter des sous pour acheter la voiture. Non seulement son taux était tout pourri mais en plus elle pouvait pas me prêter tout. Je sais pas si elle a bien compris qu'elle venait de prochainement perdre un client.
Alors qu'à La Banque Postale, ils me prêtent tout, avec un taux imbattable, sans beaucoup de paperasse, et en virant/prélevant sur mon compte courant à moi. Ça me ferait presque renouer avec la Poste, tiens.
 

Fig. 1: La région parisienne, toujours attractive.

P'tain. Tu vois ça d'où ?

le calcul de la solution exact risque de consommer un peu de temps chez tes copains d'amazon

good, j'ai une seule immense composante connexe qui contient tout le graphe.  
 
ils ont pas du tout décidé de m'emmerder.

A mon avis, y'a pas moyen pour une solution exacte, sauf à utiliser une lib spécialisée comme dit hephaestos (et même là, c'est probablement une solution approchée). Maintenant, une solution pas exacte est p-ê suffisante pour des histogrammes et autres statistiques.

mais vous ramez ou quoi ? vous savez à quelle vitesse ça avance une intersection ? il me faut 30s pour faire le n^2 (sauf que ce connard est topologique et du coup il renvoie une intersection même si seules les frontières interceptent)

 
30s pour une intersection en n^2 entre 2 polygones c'est pas normal  

du pied de la tour

bonjour, j'arrive la gueule enfarinée et je réponds à côté ...