Algorithme pour trouver un polygone centroïde irrégulier (point d'étiquette)

13

J'ai besoin de trouver un centroïde (ou un point d'étiquette) pour les polygones de forme irrégulière dans Google Maps. Je montre InfoWindows pour les colis et j'ai besoin d'un endroit pour ancrer l'InfoWindow qui est garanti d'être à la surface. Voir les images ci-dessous.

texte alternatif texte alternatif

En réalité, je n'ai besoin de rien de spécifique à Google Maps, je cherche juste une idée de la façon de trouver automatiquement ce point.

Ma première idée a été de trouver le "faux" centroïde en prenant les lat et lngs moyens et en plaçant des points au hasard à partir de là jusqu'à ce que j'en trouve un qui coupe le polygone. J'ai déjà le code de point de polygone. Cela me semble tout simplement "hacky".

Je dois noter que je n'ai accès à aucun des codes côté serveur générant la géométrie, donc je ne peux rien faire comme ST_PointOnSurface (the_geom).

Jason
la source

Réponses:

6

Rapide et sale: si le "faux" centroïde n'est pas dans le polygone, utilisez le sommet le plus proche de ce point.

Dandy
la source
Je n'y avais pas pensé. Idéalement, j'aimerais ce point dans le polygone et non sur le bord, mais c'est peut-être ce à quoi je me rabat.
Jason
Une fois que vous avez trouvé un point de bord, vous pouvez couper un petit carré centré à ce point avec le polygone, puis choisir le centre de gravité de l'intersection. Lorsque le carré est suffisamment petit, il est garanti qu'il s'agit d'un point intérieur (bien qu'il soit bien sûr très proche d'un bord).
whuber
@Jason Si vous utilisez le vrai centroïde, vous risquez moins de rencontrer ce problème. Cela ne devrait pas être trop difficile de traduire rapidement quelque chose en JavaScript: github.com/cartesiananalytics/Pipra/blob/master/src/…
Dandy
Bien que ma solution (rayons de faux centroïde) fonctionne la plupart du temps, je pense que cette solution fonctionnerait probablement mieux en raison de sa simplicité et du fait que vous êtes assuré de trouver un point au moins sur le bord, et pourrait facilement changer qu'il soit à l'intérieur du polygone avec très peu d'effort.
Jason
3

Vous voudrez peut-être regarder ceci: http://github.com/tparkin/Google-Maps-Point-in-Polygon

Il semble utiliser un algorithme Ray Casting qui devrait correspondre au cas que vous avez présenté.

Il y a un article de blog à ce sujet ici. http://appdelegateinc.com/blog/2010/05/16/point-in-polygon-checking/

DavidF
la source
Si vous vouliez l'implémenter côté serveur, JTS (Java) et Geos (C) implémentent cette fonctionnalité.
DavidF
Oui, j'aurais probablement dû ajouter que j'ai déjà le code pour déterminer si mon centroïde "calculé" est dans le polygone ou non. Ce que je veux en fait, c'est un moyen de créer un centroïde à l'intérieur du polygone.
Jason
3

Un algorithme ESRI (plus ancien) calcule le centre de masse et, après l'avoir testé pour l'inclusion dans le polygone, le déplace horizontalement si nécessaire jusqu'à ce qu'il se trouve à l'intérieur du polygone. (Cela peut être fait de plusieurs manières selon les opérations fondamentales disponibles dans votre environnement de programmation.) Cela a tendance à produire des points d'étiquette assez proches du centre visuel du polygone: essayez-le sur l'illustration.

whuber
la source
1

J'ai résolu mon problème en étendant le code epoly populaire à partir de http://econym.org.uk/gmap . Fondamentalement, ce que j'ai fini par faire était:

  • Créez une série de rayons qui partent du "faux centroïde" et s'étendent à chaque coin et côté (8 au total)
  • Créez de façon incrémentielle un point 10,20,30 ... pour cent en bas de chaque rayon et voyez si ce point est dans notre polygone d'origine

Code époly étendu ci-dessous:

google.maps.Polygon.prototype.Centroid = function() {
var p = this;
var b = this.Bounds();
var c = new google.maps.LatLng((b.getSouthWest().lat()+b.getNorthEast().lat())/2,(b.getSouthWest().lng()+b.getNorthEast().lng())/2);
if (!p.Contains(c)){
    var fc = c; //False Centroid
    var percentages = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]; //We'll check every 10% down each ray and see if we're inside our polygon
    var rays = [
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getSouthWest().lng())]}),
        new google.maps.Polyline({path:[fc,b.getNorthEast()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,b.getSouthWest()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),b.getSouthWest().lng())]})
    ];
    var lp;
    for (var i=0;i<percentages.length;i++){
        var percent = percentages[i];
        for (var j=0;j<rays.length;j++){
            var ray = rays[j];
            var tp = ray.GetPointAtDistance(percent*ray.Distance()); //Test Point i% down the ray
            if (p.Contains(tp)){
                lp = tp; //It worked, store it
                break;
            }
        }
        if (lp){
            c = lp;
            break;
        }
    }
}
return c;}

Encore un peu hacky mais ça semble marcher.

Jason
la source
Cette méthode échouera pour certains polygones tortueux. Par exemple, mettez en mémoire tampon la polyligne {{0, 9}, {10, 20}, {9, 9}, {20, 10}, {9, 0}, {20, -10}, {9, -9} , {10, -20}, {0, -9}, {-10, -20}, {-9, -9}, {-20, -10}, {-9, 0}, {-20, 10}, {-9, 9}, {-10, 20}, {0,9}} de moins de 1/2. Il est également inefficace par rapport à la méthode QAD de Dandy, par exemple.
whuber
1

Un autre algorithme «sale» pour le faire:

  • Prenez la boîte englobante de la géométrie (Xmax, Ymax, Xmin, Ymin)

  • Boucle jusqu'à ce qu'un point aléatoire ( Xmin+rand*(Xmax-Xmin), Ymin+rand*(Ymax-Ymin) ) soit trouvé dans la géométrie (en utilisant Google-Maps-Point-in-Polygon )

julien
la source
+1 car cela peut avoir une bonne chance de toucher la deuxième fois. Tant que votre "aléatoire" est reproductible à chaque fois pour ne pas déranger l'utilisateur, c'est également une solution valable. Les chances qu'il n'atteigne pas un point valide bientôt sont minces, surtout si vous commencez avec un bon point de supposition.
Dandy
1
@Dandy: En fait, dans certains cas, cela peut être un très mauvais algorithme. Prenons par exemple un ruban diagonal étroit. Ceux-ci existent dans la pratique (par exemple, de longues parcelles de façade routière) et peuvent facilement occuper moins de 0,1% de la zone de délimitation (parfois beaucoup moins). Pour être raisonnablement sûr (95% de confiance) de frapper un tel polygone avec cette technique, il faudrait environ 3 000 itérations.
whuber
@Whuber: Si vous choisissez un mauvais emplacement de départ, cela peut prendre un certain temps pour se terminer. Si vous considérez également que 95% des clics seront hypothétiquement sur des géométries plus souhaitables, cela ne peut être un problème que 5% du temps. De plus, comme pour une autre question GIS.se, si la performance est l'objectif, il n'y a jamais de solution unique, il est préférable de changer de tactique en fonction de l'heuristique. Il n'y a aucune raison d'exécuter ceci pour 3000 itérations. Vous pouvez toujours renflouer votre QAD après 10. Je pense que cela vaut la peine d'essayer celui-ci pour quelques itérations car l'emplacement peut être plus souhaitable.
Dandy
@Dandy: Mais quel est le problème avec votre solution QAD? Vous pouvez même le modifier un peu en vous déplaçant du point d'étiquette d'essai d'origine vers le sommet le plus proche dans un tampon interne du polygone: toujours QAD mais maintenant garanti d'atterrir sur un emplacement interne de l'entité d'origine. BTW, votre stratégie de renflouement rapide est bonne. Chaque fois que je code une sonde aléatoire comme celle-ci, je précalcule le rapport de la zone de l'entité à celle de sa boîte englobante, je l'utilise pour trouver le temps de réussite attendu et avertir immédiatement l'utilisateur si cela peut être long.
whuber
@Whuber l'heuristique du rapport de surface est une excellente idée parce que vous calculez à peu près le centroïde lorsque vous calculez la surface. Quant au problème avec ma solution QAD: elle est à fleur de peau. Si je choisis ce point et le tampon comme vous le dites, ce "petit" rayon peut être plus grand que la longueur à travers cette section étroite. Il y a toujours un cas d'angle. Autant de choses à considérer, juste pour faire un ballon qui encombrera l'interface utilisateur et obscurcira la géométrie de toute façon. Il vaut probablement mieux choisir le sommet le plus haut ou le plus bas.
Dandy
1

À la lumière de votre récente clarification selon laquelle vous préféreriez un emplacement strictement intérieur, vous pouvez sélectionner n'importe quel point de la transformation de l'axe médian qui ne se trouve pas également sur la limite du polygone. (Si vous n'avez pas de code pour un MAT, vous pouvez l'approcher en tamponnant négativement le polygone. Une recherche binaire ou sécante produira rapidement un petit polygone intérieur qui se rapproche d'une partie du MAT; utilisez n'importe quel point sur sa frontière.)

whuber
la source
Je comprends ce que vous disiez à propos de l'utilisation du bord d'une géométrie de telle sorte que le bord se trouve à l'intérieur du polygone d'intérêt. Je ne comprends pas comment vous allez créer cette arête / sommet. La seule chose à laquelle je peux penser est de créer un triangle virtuel en coupant un rayon perpendiculaire du point d'intérêt au segment opposé au segment du point sélectionné. Le point médian entre ces deux points pourrait être le sommet de ce triangle virtuel.
Dandy
@Dandy: Cela va au cœur du problème. Il existe plusieurs façons de procéder en fonction de ce que fait votre SIG en mode natif. Par exemple, une fois que vous avez trouvé un rayon qui coupe l'entité d'origine dans un ensemble de longueurs positives, cette intersection sera une union disjointe de segments de ligne. Utilisez le centre de l'un de ces segments. Une autre façon est de commencer par n'importe quel point de l'entité (de préférence près de son milieu, ce que votre méthode QED a accompli), de créer un petit polygone simple (par exemple, carré) centré là, de l'intersecter avec l'entité d'origine, de choisir l'unique connecté composant ...
whuber
(suite) ... contenant le point de départ, et choisissez récursivement un centre pour ce composant. De nombreuses méthodes seront disponibles lorsque votre SIG vous permettra de parcourir les séquences de sommets décrivant la frontière de l'entité. Si les tampons négatifs sont pris en charge, vous pouvez trouver de manière itérative un ensemble de points intérieurs à distance maximale (le «squelette», qui est un sous-ensemble du MAT). C'est un peu cher mais assez facile à programmer et produit d'excellents points d'étiquette.
whuber
0

Pourquoi ne pas utiliser le centroïde uniquement pour la position verticale (latitude)? Ensuite, vous pouvez positionner l'étiquette horizontalement en choisissant la longitude moyenne à cette latitude . (Pour cela, vous devez trouver la valeur de longitude pour un bord de polygone à une latitude spécifique, ce qui ne devrait pas vous poser de problème).

Faites également attention aux formes en U et aux formes plus complexes. :) Peut-être pour ceux-ci, choisissez la moyenne de la paire de longitudes la plus à droite (chaque paire correspondrait à une tranche du polygone), puisque la fenêtre d'information est orientée de cette façon?

Cela vous donne également un peu plus de contrôle sur le positionnement; par exemple, il peut être judicieux de positionner la fenêtre d'informations à 66 ou 75% verticalement, afin de laisser plus de polygone visible. (Ou peut-être pas! Mais vous avez le bouton à modifier.)

Dan S.
la source
0

Que diriez-vous d'utiliser simplement le point sur lequel l'utilisateur a cliqué pour le sélectionner, s'il est sélectionné par l'utilisateur qui est.

Dandy
la source
Il peut être sélectionné par un clic de souris ou une requête non spatiale, donc cela ne fonctionnera pas toujours.
Jason
0

J'essaie de résoudre ça aussi. J'ai imposé une condition à mes polygones pour qu'ils ne puissent pas avoir de lignes de croisement qui entrent dans ce que je vais décrire.

Donc, mon approche utilise la triangulation. Prenez un sommet aléatoire (prendre éventuellement un sommet à l'extrême N, E, W ou S peut simplifier les choses).

À partir de ce sommet, tracez des lignes jusqu'au sommet un sommet plus loin, c'est-à-dire si votre sommet est le sommet 3, regardez le sommet 3 + 2.

Construisez une ligne entre votre sommet d'origine et ce sommet. Si la ligne construite:

  1. ne traverse aucune autre ligne et
  2. son point médian n'est pas en dehors du polygone

Ensuite, vous avez construit un triangle à l'intérieur du polygone. Si le sommet réussi était n + 2, alors votre triangle est {n, n + 1, n + 2}, que nous appellerons {v, v1, v2}. Sinon, essayez le sommet suivant et continuez jusqu'à ce que tous les sommets aient été essayés.

Lorsque vous trouvez un triangle, trouvez le centre de celui-ci en prenant une ligne allant du sommet v au milieu de v1 et v2. Le milieu de cette ligne est garanti d'être à l'intérieur du triangle et à l'intérieur du polygone.

Je n'ai pas encore codé cela, mais je peux voir, en y réfléchissant, qu'un polygone avec des lignes croisées provoquera en fait des conditions exotiques où cela ne fonctionne pas. Si c'est le type de polygones dont vous disposez, vous devez tester chaque segment de ligne sur le polygone et vous assurer qu'il n'est pas traversé. Évitez les segments de ligne croisés et je pense que cela fonctionnera.


la source