Algorithmus zum Auffinden eines unregelmäßigen Polygonschwerpunkts

13

Ich muss in Google Maps einen Schwerpunkt (oder Beschriftungspunkt) für unregelmäßig geformte Polygone finden. Ich zeige InfoWindows für Pakete und brauche einen Platz, um das InfoWindow zu verankern, das sich garantiert auf der Oberfläche befindet. Siehe Bilder unten.

Alt-Text Alt-Text

In Wirklichkeit brauche ich nichts Google Maps-spezifisches, sondern suche nur nach einer Idee, wie man diesen Punkt automatisch findet.

Meine erste Idee war es, den "falschen" Schwerpunkt zu finden, indem ich die durchschnittlichen Breiten und Längen und die zufällig platzierten Punkte von dort aus nehme, bis ich einen finde, der das Polygon schneidet. Ich habe bereits den Point-in-Polygon-Code. Das kommt mir einfach furchtbar "hackig" vor.

Ich sollte beachten, dass ich keinen Zugriff auf den serverseitigen Code habe, der die Geometrie ausgibt, sodass ich nichts wie ST_PointOnSurface (the_geom) tun kann.

Jason
quelle

Antworten:

6

Schnell und schmutzig: Wenn sich der "falsche" Schwerpunkt nicht im Polygon befindet, verwenden Sie den nächsten Scheitelpunkt zu diesem Punkt.

Dandy
quelle
Ich hatte nicht darüber nachgedacht. Idealerweise würde ich diesen Punkt im Polygon und nicht am Rand mögen, aber darauf könnte ich zurückgreifen.
Jason
Wenn Sie einen Kantenpunkt gefunden haben, können Sie ein kleines Quadrat, das an diesem Punkt zentriert ist, mit dem Polygon schneiden und dann den Schwerpunkt der Schnittmenge auswählen. Wenn das Quadrat klein genug ist, handelt es sich garantiert um einen inneren Punkt (obwohl es sich natürlich sehr nahe an einer Kante befindet).
Whuber
@ Jason Wenn Sie den realen Schwerpunkt verwenden, ist die Wahrscheinlichkeit, dass dieses Problem auftritt, geringer. Sollte nicht zu schwer sein, etwas schnell in JavaScript zu übersetzen: github.com/cartesiananalytics/Pipra/blob/master/src/…
Dandy
Während meine Lösung (Strahlen von falschem Schwerpunkt) die meiste Zeit funktionieren wird, denke ich, dass diese Lösung aufgrund ihrer Einfachheit und der Tatsache, dass Sie garantiert mindestens einen Punkt am Rand finden und sich leicht verschieben können, wahrscheinlich am besten funktioniert es ist mit sehr geringem Aufwand innerhalb des Polygons zu sein.
Jason
3

Möglicherweise möchten Sie Folgendes überprüfen: http://github.com/tparkin/Google-Maps-Point-in-Polygon

Es scheint einen Ray Casting-Algorithmus zu verwenden, der dem von Ihnen vorgestellten Fall entsprechen sollte.

Hier gibt es einen Blogbeitrag dazu. http://appdelegateinc.com/blog/2010/05/16/point-in-polygon-checking/

DavidF
quelle
Wenn Sie dies auf der Serverseite implementieren wollten, implementieren sowohl JTS (Java) als auch Geos (C) diese Funktionalität.
DavidF
Ja, ich hätte wahrscheinlich hinzufügen sollen, dass ich bereits den Code habe, um festzustellen, ob mein "berechneter" Schwerpunkt innerhalb des Polygons liegt oder nicht. Was ich eigentlich möchte, ist eine Möglichkeit, einen Schwerpunkt zu erstellen, der sich innerhalb des Polygons befindet.
Jason
3

Ein (älterer) ESRI-Algorithmus berechnet den Massenmittelpunkt und verschiebt ihn nach dem Testen auf Einbeziehung in das Polygon bei Bedarf horizontal, bis er innerhalb des Polygons liegt. (Dies kann auf viele Arten geschehen, je nachdem, welche grundlegenden Operationen in Ihrer Programmierumgebung verfügbar sind.) Dies führt dazu, dass Beschriftungspunkte ziemlich nahe am visuellen Zentrum des Polygons erzeugt werden: Probieren Sie es in der Abbildung aus.

whuber
quelle
1

Ich habe mein Problem gelöst, indem ich den populären epoly-Code von http://econym.org.uk/gmap erweitert habe . Im Grunde war das, was ich getan habe:

  • Erstellen Sie eine Reihe von Strahlen, die vom "falschen Schwerpunkt" ausgehen und sich zu jeder Ecke und Seite erstrecken (insgesamt 8).
  • Erstellen Sie schrittweise einen Punkt 10, 20, 30 ... Prozent pro Strahl und prüfen Sie, ob dieser Punkt in unserem ursprünglichen Polygon liegt

Erweiterter epoly Code unten:

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;}

Immer noch ein bisschen verrückt, aber es scheint zu funktionieren.

Jason
quelle
Diese Methode schlägt bei einigen gewundenen Polygonen fehl. Beispiel: Puffern Sie die Polylinie {{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}} um weniger als 1/2. Es ist zum Beispiel auch ineffizient im Vergleich zu Dandys QAD-Methode.
Whuber
1

Ein anderer 'schmutziger' Algorithmus, um das zu tun:

  • Nehmen Sie den Begrenzungsrahmen der Geometrie (Xmax, Ymax, Xmin, Ymin)

  • Schleife, bis ein zufälliger Punkt ( Xmin+rand*(Xmax-Xmin), Ymin+rand*(Ymax-Ymin) ) in der Geometrie gefunden wird (mit Google-Maps-Point-in-Polygon )

julien
quelle
+1, weil dies eine faire Chance auf einen Treffer beim zweiten Mal haben kann. Solange Ihr "Zufall" jedes Mal reproduzierbar ist, um den Benutzer nicht zu ärgern, ist dies auch eine gültige Lösung. Die Wahrscheinlichkeit, dass es nicht bald einen gültigen Punkt erreicht, ist gering, besonders wenn Sie mit einem guten Schätzpunkt beginnen.
Dandy,
1
@Dandy: Tatsächlich kann dies in einigen Fällen ein wirklich schlechter Algorithmus sein. Betrachten Sie zum Beispiel ein schmales Diagonalsplitter. Diese sind in der Praxis vorhanden (z. B. lange Straßenfronten) und können leicht weniger als 0,1% des Begrenzungsrahmens (manchmal weitaus weniger) einnehmen. Um mit dieser Technik einigermaßen sicher (zu 95% sicher) auf ein solches Polygon zu treffen, wären etwa 3.000 Iterationen erforderlich.
Whuber
@Whuber: Wenn du einen schlechten Startort auswählst, kann es eine Weile dauern, bis der Vorgang abgeschlossen ist. Wenn Sie auch davon ausgehen, dass 95% der Klicks auf wünschenswertere Geometrien abzielen, ist dies möglicherweise nur in 5% der Fälle ein Problem. Auch wie bei einer anderen GIS.se-Frage, bei der Leistung das Ziel ist, gibt es nie eine einzige Lösung. Daher ist es am besten, die Taktik auf der Grundlage von Heuristiken zu ändern. Es gibt keinen Grund, dies für 3000 Iterationen zu beenden. Sie können immer nach 10 Uhr zu meinem QAD aussteigen. Ich denke, es lohnt sich, diesen für ein paar Iterationen auszuprobieren, da der Ort möglicherweise wünschenswerter ist.
Dandy
@Dandy: Aber was ist los mit deiner QAD-Lösung? Sie können es sogar geringfügig ändern, indem Sie vom ursprünglichen Versuchsbeschriftungspunkt zum nächsten Scheitelpunkt in einem internen Puffer des Polygons wechseln: noch QAD, aber jetzt garantiert an einer internen Position des ursprünglichen Features. Übrigens ist Ihre Strategie der baldigen Rettung eine gute. Immer wenn ich eine Zufallsprobe wie diese codiere, berechne ich das Verhältnis der Fläche des Features zu der des Begrenzungsrahmens vor, nutze dies, um die erwartete Zeit bis zum Erfolg zu ermitteln, und warne den Benutzer sofort, wenn es lang sein könnte.
whuber
@Whuber die Flächenverhältnis-Heuristik ist eine gute Idee, da Sie den Flächenschwerpunkt gerade erst berechnen, wenn Sie die Fläche berechnen. Was das Problem mit meiner QAD-Lösung angeht: Es ist am Rande. Wenn ich diesen Punkt wähle und ihn puffere, wie Sie sagen, kann dieser "kleine" Radius größer sein als die Länge über diesen schmalen Abschnitt. Es gibt immer einen Eckfall. So viel zu beachten, nur um einen Ballon zu erstellen, der die Benutzeroberfläche überfüllt und die Geometrie trotzdem verdeckt. Wahrscheinlich ist es besser, den höchsten oder niedrigsten Scheitelpunkt zu wählen.
Dandy
1

In Anbetracht Ihrer jüngsten Klarstellung, dass Sie eine rein interne Position bevorzugen, können Sie jeden Punkt in der medialen Achsentransformation auswählen, der sich nicht auch an der Grenze des Polygons befindet. (Wenn Sie keinen Code für eine MAT haben, können Sie ihn durch negatives Puffern des Polygons approximieren. Bei einer binären oder sekantenbasierten Suche wird schnell ein kleines inneres Polygon erzeugt, das einem Teil der MAT nahekommt. Verwenden Sie einen beliebigen Punkt an der Grenze.)

whuber
quelle
Ich verstehe, was Sie über die Verwendung der Kante einer Geometrie gesagt haben, sodass sich die Kante im Inneren des interessierenden Polygons befindet. Ich verstehe nicht, wie Sie diese Kante / Scheitel erstellen würden. Ich kann mir nur vorstellen, ein virtuelles Dreieck zu bilden, indem ich einen senkrechten Strahl vom interessierenden Punkt zum Segment gegenüber dem Segment des ausgewählten Punkts schneide. Der Mittelpunkt zwischen diesen beiden Punkten könnte die Spitze dieses virtuellen Dreiecks sein.
Dandy
@ Dandy: Das bringt es auf den Punkt. Es gibt viele Möglichkeiten, dies zu tun, je nachdem, was Ihr GIS nativ tut. Wenn Sie beispielsweise einen Strahl gefunden haben, der das ursprüngliche Feature in einem Satz positiver Länge schneidet, ist dieser Schnitt eine disjunkte Vereinigung von Liniensegmenten. Verwenden Sie die Mitte eines dieser Segmente. Eine andere Möglichkeit besteht darin, mit einem beliebigen Punkt des Features zu beginnen (vorzugsweise in der Nähe seiner Mitte, wie es Ihre QED-Methode erreicht hat), ein kleines einfaches Polygon (z. B. ein Quadrat) zu erstellen, es mit dem ursprünglichen Feature zu schneiden und das eindeutige verbundene Element auszuwählen Komponente ...
whuber
(Fortsetzung) ... enthält den Startpunkt und wählt rekursiv einen Mittelpunkt für diese Komponente. Es gibt eine Vielzahl von Methoden, mit denen Sie in Ihrem GIS die Scheitelpunktsequenzen durchlaufen können, die die Feature-Grenze beschreiben. Wenn negative Puffer unterstützt werden, können Sie iterativ eine Reihe von Innenpunkten mit maximalem Abstand finden (das "Skelett", eine Teilmenge der MAT). Dies ist ein wenig teuer, aber ziemlich einfach zu programmieren und erzeugt ausgezeichnete Beschriftungspunkte.
whuber
0

Warum nicht den Schwerpunkt nur für die vertikale Position (Breitengrad) verwenden? Anschließend können Sie das Etikett horizontal positionieren, indem Sie den durchschnittlichen Längengrad bei diesem Breitengrad auswählen . (Dazu müssen Sie den Längengrad für eine Polygonkante bei einem bestimmten Breitengrad ermitteln, was Ihnen keine Probleme bereiten sollte.)

Achten Sie auch auf U-Formen und komplexere. :) Wählen Sie unter Umständen den Durchschnitt des äußersten rechten Längenpaars (jedes Paar würde einem Schnitt des Polygons entsprechen), da das Infofenster so ausgerichtet ist.

Dies gibt Ihnen auch ein wenig mehr Kontrolle über die Positionierung. Beispielsweise kann es hilfreich sein, das Infofenster vertikal auf 66 oder 75% zu positionieren, um mehr vom Polygon sichtbar zu machen. (Oder es kann nicht! Aber Sie haben den Knopf zu zwicken.)

Dan S.
quelle
0

Wie wäre es, wenn Sie nur den Punkt verwenden, auf den der Benutzer geklickt hat, um ihn auszuwählen, wenn er vom betreffenden Benutzer ausgewählt wurde?

Dandy
quelle
Es kann per Mausklick oder nicht räumlicher Abfrage ausgewählt werden, sodass dies nicht immer funktioniert.
Jason
0

Ich versuche das auch zu lösen. Ich habe meinen Polygonen die Bedingung auferlegt, dass sie keine sich kreuzenden Linien haben dürfen, die in das eingehen, was ich beschreiben werde.

Mein Ansatz verwendet also Triangulation. Nehmen Sie einen zufälligen Scheitelpunkt (möglicherweise nehmen Sie einen Scheitelpunkt am äußersten Punkt N, E, W oder S, um die Dinge zu vereinfachen).

Zeichnen Sie von diesem Scheitelpunkt Linien zu dem einen Scheitelpunkt entfernten Scheitelpunkt, dh wenn Ihr Scheitelpunkt Scheitelpunkt 3 ist, schauen Sie auf Scheitelpunkt 3 + 2.

Konstruieren Sie eine Linie von Ihrem ursprünglichen Scheitelpunkt zu diesem Scheitelpunkt. Wenn die konstruierte Linie:

  1. kreuzt keine andere Linie und
  2. sein Mittelpunkt liegt nicht außerhalb des Polygons

Dann haben Sie ein Dreieck konstruiert, das sich innerhalb des Polygons befindet. Wenn der erfolgreiche Eckpunkt n + 2 war, ist Ihr Dreieck {n, n + 1, n + 2}, was wir als {v, v1, v2} bezeichnen. Wenn nicht, versuchen Sie es mit dem nächsten Scheitelpunkt und fahren Sie fort, bis alle Scheitelpunkte ausprobiert wurden.

Wenn Sie ein Dreieck finden, ermitteln Sie dessen Mittelpunkt, indem Sie eine Linie vom Scheitelpunkt v zum Mittelpunkt von v1 und v2 ziehen. Der Mittelpunkt dieser Linie liegt garantiert innerhalb des Dreiecks und innerhalb des Polygons.

Ich habe dies noch nicht codiert, aber ich kann sehen, wie ich darüber nachdenke, dass ein Polygon mit sich kreuzenden Linien tatsächlich einige exotische Zustände hervorruft, bei denen dies nicht funktioniert. Wenn dies die Art von Polygonen ist, die Sie haben, müssen Sie jedes Liniensegment auf dem Polygon testen und sicherstellen, dass es nicht gekreuzt wird. Überspringen Sie Liniensegmente, die gekreuzt sind, und ich denke, es wird funktionieren.


quelle