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

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.

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).

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

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/

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.

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.

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 )

À 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.)

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.)

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.

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.

https://github.com/mapbox/polylabel peut être utile (javascript et C ++). Implémentation C # ici: https://gist.github.com/dfaivre/acfef42cdbf411555956e9eba65dd30d .

Question SO originale ici: /programming//a/38522611/79113