webentwicklung-frage-antwort-db.com.de

Wie kann man am schnellsten den "visuellen" Mittelpunkt eines unregelmäßig geformten Polygons finden?

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

Hier ist eine Lösung, die die Pufferung im Inneren verwendet:

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

Wenn dies verwendet werden soll, wie kann der Puffer effektiv und schnell gefunden werden? Wenn ein anderer Weg verwendet werden soll, welcher ist dann?

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

47
Mikhil

Wenn Sie das Polygon in ein binäres Bild konvertieren können, können Sie die im Bereich der Bildverarbeitung vorhandene Grundlage verwenden, z. B .: Ein schneller Skelett-Algorithmus Auf Blockdargestellte binäre Bilder .

Dies ist jedoch im allgemeinen Fall aufgrund von Diskretisierungsfehlern und zusätzlicher Arbeit nicht wirklich sinnvoll.

Vielleicht finden Sie diese nützlich: 

BEARBEITEN: Vielleicht möchten Sie nach dem Punkt suchen, der den Mittelpunkt des größten Kreises im Polygon darstellt. Es ist nicht notwendigerweise immer in dem beobachteten Zentrum, aber die meiste Zeit würde wahrscheinlich das erwartete Ergebnis liefern, und nur in leicht pathologischen Fällen etwas, das völlig daneben liegt.

10
Reunanen

Ich habe in MapBox eine sehr gute Lösung mit dem Namen Polylabel gefunden. Die vollständige Quelle ist auch auf Github verfügbar.

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

enter image description here

Bestimmte Details deuten darauf hin, dass dies eine praktische Lösung sein kann:

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

Für unseren Anwendungsfall benötigen wir keine exakte Lösung - wir sind dazu bereit. Handeln Sie etwas Präzision, um mehr Geschwindigkeit zu erreichen. Wenn wir ein Etikett auf Für eine Karte ist es wichtiger, dass sie in Millisekunden berechnet wird als mathematisch perfekt sein.

Ein kurzer Hinweis zur Verwendung. Der Quellcode ist für Javascript sofort einsatzbereit. Wenn Sie jedoch beabsichtigen, dieses mit einem "normalen" Polygon zu verwenden, sollten Sie es in ein leeres Array einschließen, da die Funktionen hier GeoJSONPolygons anstelle von normalen Polygonen, d. 

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

Wie wäre es mit:

Wenn sich der Schwerpunkt des Polygons innerhalb des Polygons befindet, verwenden Sie es, ansonsten:

1) Ziehen Sie eine Linie vom Schwerpunkt durch das Polygon, indem Sie das Polygon in zwei gleich große Hälften teilen

2) Das "visuelle Zentrum" ist der Punkt auf halbem Weg zwischen dem nächstgelegenen Punkt, an dem die Linie den Umfang berührt, und dem nächsten Punkt, der den Umfang in die Richtung schneidet, die vom Schwerpunkt weggeht

Hier sind ein paar Bilder, um es zu veranschaulichen:

 enter image description here

 enter image description here

7
T.Austin
7
Arron S

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

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

Um ein einfaches UI-Label zu platzieren, kann es auch ausreichend sein, den Begrenzungsrahmen des Polygons (ein Rechteck, das durch die niedrigsten und höchsten x- und y-Koordinaten eines Scheitelpunkts im Polygon definiert ist) zu berechnen und seinen Mittelpunkt zu erhalten:

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

Dies ist etwas schneller als die Berechnung des Schwerpunkts, was für eine Echtzeit- oder eingebettete Anwendung von Bedeutung sein kann.

Wenn Ihre Polygone statisch sind (sie ändern ihre Form nicht), können Sie auch optimieren, indem Sie das Ergebnis der BB-Mitte/Massenmittelpunktberechnung (relativ zum ersten Scheitelpunkt des Polygons) in der Datenstruktur von speichern das Polygon.

2
safdsas

Berechnen Sie die Mittenposition (x, y) jeder Kante des Polygons. Sie können dies tun, indem Sie die Differenz zwischen den Positionen der Enden jeder Kante ermitteln. Nehmen Sie den Durchschnitt jedes Zentrums in jeder Dimension. Dies ist der Mittelpunkt des Polygons.

2
ire_and_curses

Ich sage nicht, dass dies das schnellste ist, aber Sie erhalten einen Punkt innerhalb des Polygons. Berechnen Sie das Gerade Skelett . Der Punkt, den Sie suchen, ist auf diesem Skelett. Sie können beispielsweise denjenigen mit dem kürzesten normalen Abstand zur Mitte des Begrenzungsrahmens auswählen. 

1

Wie wäre es, wenn Sie den "Inkreis" des Polygons (den größten Kreis, der in ihn hineinpasst) finden und dann das Label in der Mitte zentrieren? Hier sind ein paar Links zum Einstieg:

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

Dies funktioniert höchstwahrscheinlich nicht bei jedem Polygon perfekt. Ein Polygon, das wie ein C aussah, würde das Etikett an einer etwas unvorhersehbaren Stelle haben. Der Vorteil wäre jedoch, dass die Beschriftung immer einen festen Teil des Polygons überlappt.

0
Ryan Lundy