Wie finde ich am schnellsten den "visuellen" Mittelpunkt eines unregelmäßig geformten Polygons?

Question

Ich muss einen Punkt finden, der ein visuelles Zentrum eines unregelmäßig geformten Polygons ist. Mit visuellem Zentrum meine ich einen Punkt, der visuell in der Mitte eines großen Bereichs des Polygons zu sein scheint. Die Anwendung besteht darin, ein Etikett in das Polygon einzufügen.

Hier ist eine Lösung, die in Pufferung verwendet:

https://web.archive.org/web/20150708063910/http://proceedings.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

Wenn diese verwendet werden soll, was eine effektive und schnelle Art und Weise, den Puffer zu finden? Wenn es anders geht, was ist das?

Ein gutes Beispiel für wirklich harte Polygone ist ein riesiges dickes U (geschrieben in Arial Black oder Impact oder eine solche Schriftart).

Answer 1

Wenn Sie das Polygon in ein binäres Bild umwandeln kann, dann können Sie die Grundlage verwenden, die auf dem Gebiet der Bildverarbeitung vorhanden ist, z.B .: A Fast Skeleton Algorithm on Block Represented Binary Images.

Aber das ist im allgemeinen Fall wegen Diskretisierungsfehlern und zusätzlicher Arbeit nicht wirklich vernünftig.

Aber vielleicht finden Sie diese nützlich:

• Straight skeleton of a simple polygon
• Determining the Skeleton of a Simple Polygon in (Almost) Linear Time

EDIT: Vielleicht sind Sie für den Punkt suchen möchten, dass das Zentrum des größten Kreises in der enthaltenen Polygon. Es ist nicht unbedingt immer im beobachteten Zentrum, aber die meiste Zeit würde wahrscheinlich das erwartete Ergebnis liefern, und nur in leicht pathologischen Fällen etwas, das völlig ausfällt.

Answer 2

Dieses Problem wäre wahrscheinlich analog zum Auffinden des "Massenschwerpunkts" unter Annahme einer gleichmäßigen Dichte.

EDIT: Dieses Verfahren funktioniert nicht, wenn das Polygon hat „Löcher“

Answer 3

Berechne die Mittelposition (x, y) von jeder Kante des Polygons. Sie können dies tun, indem Sie den Unterschied zwischen den Positionen der Enden jeder Kante ermitteln. Nehmen Sie den Durchschnitt jedes Zentrums in jeder Dimension. Dies wird die Mitte des Polygons sein.

Answer 4

Ich glaube, wenn Sie das Polygon zurück in seine Scheitelpunkte gebrochen und dann eine Funktion angewendet haben, um die größte konvexe Hülle zu finden, und dann die Mitte dieser konvexen Hülle finden, würde sie genau mit der "scheinbaren" Mitte übereinstimmen.

die größte konvexe Hülle der Eckpunkte gegeben Finding: Look under the Simple Polygon paragraph.

Durchschnitt der Eckpunkte der konvexen Hülle die Mitte zu finden.

Answer 5

Wenn ich den Punkt des Papiers verstehe, mit dem Sie verlinkt haben (ein ziemlich interessantes Problem, btw), ist diese "innere Pufferung" -Technik etwas analog zur Modellierung der fraglichen Form aus einem Stück Zucker, das durch Säure aufgelöst wird von den Kanten in. (z. B. wenn der Pufferabstand zunimmt, bleibt weniger von der ursprünglichen Form übrig) Das letzte verbleibende Bit ist der ideale Ort, um ein Etikett zu platzieren.

Wie dies leider in einem Algorithmus zu erreichen, ich ist nicht ganz klar ....

Answer 6

Könnten Sie das Etikett an dem naiven Zentrum (des Begrenzungsrahmens, vielleicht), und dann bewegen sie basieren an den Schnittpunkten der lokalen Polygonkanten und dem BB des Labels? Bewegen Sie sich entlang der Normalen der Schnittkanten, und wenn sich mehrere Kanten schneiden, summieren Sie ihre Normalen für die Bewegung?

Nur Raten hier; Bei dieser Art von Problem würde ich wahrscheinlich versuchen, es iterativ zu lösen, solange die Leistung nicht allzu wichtig ist.

Answer 7

Haben Sie sich mit der Schwerpunktformel befasst?

http://en.wikipedia.org/wiki/Centroid

http://en.wikipedia.org/wiki/K-means_algorithm

Answer 8

Wie wäre es mit der Suche nach dem "Inkreis" des Polygons (der größte Kreis, der in das Polygon passt), und dann zentriert man das Etikett in der Mitte? Hier sind ein paar Links, die Sie zu erhalten begonnen:

http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/144373.html?1219439473

Dies wird nicht perfekt funktionieren auf jedem Polygon, höchstwahrscheinlich; Ein Polygon, das wie ein C aussah, würde das Label an einer etwas unvorhersehbaren Stelle haben. Aber der Vorteil wäre, dass das Etikett immer einen festen Teil des Polygons überlappen würde.

Answer 9

Nicht viel Zeit, um dies jetzt zu erarbeiten oder zu testen, aber ich werde versuchen, mehr zu tun, wenn ich eine Chance bekomme.

Verwenden Sie Zentroide als Ihre primäre Methode. Testen Sie, ob der Schwerpunkt innerhalb des Polygons liegt. Wenn nicht, zeichne eine Linie durch den nächsten Punkt und auf die andere Seite des Polygons. Platzieren Sie in der Mitte des Abschnitts dieser Linie, die sich innerhalb des Polygons befindet, Ihr Label.

Da der Punkt, der dem Schwerpunkt am nächsten ist, wahrscheinlich ein ziemlich großes Gebiet einbindet, denke ich, dass dies zu ähnlichen Ergebnissen wie in Kyralessas Kreisen führen könnte. Natürlich könnte das verrückt werden, wenn Sie ein Polygon mit Löchern hätten. In diesem Fall würden die Inkreise wahrscheinlich viel besser sein. Auf der anderen Seite wird für die typischen Fälle die (schnelle?) Schwerpunktmethode verwendet.

Answer 10

Ich sage nicht, dass dies die schnellste ist, aber es wird Ihnen einen Punkt innerhalb des Polygons geben. Berechnen Sie die Straight Skeleton. Der Punkt, nach dem du suchst, ist auf diesem Skelett. Sie könnten zum Beispiel diejenige auswählen, die den kürzesten Normalabstand zur Mitte der Begrenzungsbox hat.

Answer 11

Die Centroid-Methode wurde bereits mehrfach vorgeschlagen. Ich denke, dass dies eine ausgezeichnete Ressource ist, die den Prozess (und viele andere nützliche Tricks mit Polygonen) sehr intuitiv beschreibt:

http://paulbourke.net/geometry/polygonmesh/centroid.pdf

Auch für die Platzierung ein einfaches UI-Label, kann es ausreichend sein, nur den Begrenzungs berechnen Schachtel des Polygons (ein Rechteck von dem niedrigsten und höchsten x und y Koordinaten eines beliebigen Scheitelpunkt in dem Polygon definiert ist), und sein Zentrum immer auf:

{ 
    x = min_x + (max_x - min_x)/2, 
    y = min_y + (max_y - min_y)/2 
} 

Dies ist etwas schneller als der Schwerpunkt berechnet wird, die möglicherweise wichtig für eine Echtzeit- oder eingebettete Anwendung.

Beachten Sie auch, dass wenn Ihre Polygone statisch sind (sie ändern nicht die Form), könnten Sie optimieren, indem Sie das Ergebnis der BB-Mitte/Schwerpunkt-Berechnung (relativ zum ersten Scheitelpunkt des Polygons) speichern die Datenstruktur des Polygons.

Answer 12

Sie Mitte der Masse (oder Center of Gravity) können Verfahren, die im Bauwesen verwendet wird, hier ist eine nützliche Verbindung von wikipedia:

http://en.wikipedia.org/wiki/Center_of_mass

Answer 13

Wie wäre:

Wenn die Zentroid des Polygons ist innerhalb des Polygons, dann verwenden Sie es, sonst:

1) Erweitern Sie eine Linie aus dem Schwerpunkt durch das Polygon das Teilen des Polygons in zwei Hälften der gleichen Fläche

2) Das „Sehzentrum“ ist der Punkt, auf halben Weg zwischen dem nächsten Punkt, an dem die Linie den Umfang berührt und den nächsten Punkt um den Umfang in Richtung Schneid vom Schwerpunkt weg

Hier ist ein paar Bilder illustrieren es:

Answer 14

ich habe eine sehr gute Lösung für dieses Problem von MapBox gefunden Polylabel genannt. Die vollständige Quelle ist auf ihrem Github auch verfügbar.

Im Wesentlichen versucht es, das visuelle Zentrum des Polygons zu finden, wie T Austin sagte.

Bestimmte Details legen nahe, dies eine praktische Lösung sein kann:

Leider Berechnung [die ideale Lösung] ist sowohl komplex als und langsam. Die veröffentlichten Lösungen für das Problem erfordern entweder Constrained Delaunay Triangulation oder die Berechnung eines geraden Skeletts als Vorverarbeitungsschritte - beide sind langsam und fehleranfällig.

Für unseren Anwendungsfall brauchen wir keine genaue Lösung - wir sind bereit, mit etwas Präzision zu handeln, um mehr Geschwindigkeit zu erhalten. Wenn wir eine Karte auf eine Karte platzieren, ist es wichtiger, dass sie in Millisekunden als berechnet wird, um mathematisch perfekt zu sein.

Eine kurze Notiz über die Verwendung obwohl. Der Quellcode funktioniert gut für Javascript aus der Box aber wenn Sie sich mit diesem mit einem „normalen“ Polygon beabsichtigen, dann sollten Sie es in einem leeren Array wickeln wie die hier Funktionen GeoJSONPolygons nehmen eher als normale Polygone dh

var myPolygon = [[x1, y1], [x2, y2], [x3, y3]]; 
var center = polylabel([myPolygon]);