Suchen Sie die längste gerade Linie zwischen zwei Punkten auf der Oberfläche des Polygons

8

Meine Form ist ein leicht konkaves Polygon, und ich möchte den maximalen Durchmesser kennen. Ich stelle mir eine gerade Linie zwischen zwei Punkten auf der Oberfläche des Polygons vor, so dass die Linie nicht außerhalb des Polygons verläuft.

Gibt es dafür einen allgemeinen Algorithmus?

In meinem Fall interessiert mich 2D. Meine Formen sind Tumore in medizinischen Bildern. Wir können also auch annehmen: 1 Der Schwerpunkt befindet sich immer innerhalb des Polygons. 2 eine hohe Scheitelpunktdichte, dh der nächste Scheitelpunkt liegt immer nahe am vorherigen.

mathematics computational-geometry polygon Jiggunjer
quelle
1
Es gibt rotierende Bremssättel, aber das funktioniert nur für konvexe Polygone. Andernfalls können Sie es als Basis für eine Brute-Force-Lösung verwenden.
Ratschenfreak
3
Nun, wenn O (n ^ 2) kein Problem ist, dann testen Sie alle Punktpaare
joojaa
2
Eigentlich ist es etwas komplizierter: Stellen Sie sich 2 Räume vor, die durch einen schmalen Korridor verbunden sind. Der größte Durchmesser endet an den Wänden in den verschiedenen Räumen und endet nicht an irgendwelchen Punkten.
Ratschenfreak
1
Suchen Sie einen Algorithmus, der im allgemeinsten Fall funktioniert, oder kann er beispielsweise auf den 2D-Fall beschränkt werden? Dies ist möglicherweise einfacher zu lösen, wenn weitere Informationen oder Einschränkungen zur Eingabe vorliegen. Sie verwenden das Wort Polygon, das möglicherweise nur auf 2D hinweist. Auch die von Ihnen verknüpfte Frage legt den 2D-Fall nahe. Reicht es auch aus, Scheitelpunkt-Scheitelpunkt-Abstände zu berücksichtigen, oder benötigen Sie korrekte Ergebnisse für Fälle wie den in seinem Kommentar erwähnten Ratschenfreak ?
Nero
2
Ich mache mir auch Sorgen um eine C-Form mit sehr schmaler Dicke, aber einem großen, offenen Innenraum. und so ein großer Krümmungsradius. Sein Durchmesser (wie Sie ihn definieren) wäre sehr klein, da er nur ein Kurzschluss wäre, der der Krümmung des C folgt. Ein Krebsknoten von der Größe der Innengröße wäre jedoch ziemlich besorgniserregend. Vielleicht ist es also die konvexe Hülle, deren Durchmesser Sie berechnen möchten.
Wyck

Antworten:

1

Ich habe keine genaue Antwort darauf, da die Antwort alles andere als trivial ist. Ich würde vorschlagen, dass Sie sich die rechnerische Geometrie ansehen, da dies eindeutig ein Sichtbarkeitsproblem darstellt - ich vermute, dass es bereits eine Lösung gibt. Meine eigene Idee wäre: Finden Sie für jedes Liniensegment im Polygon die sichtbaren Teile der anderen Liniensegmente und wählen Sie dann das Punktpaar aus, das am weitesten voneinander entfernt ist. Inspirierender Link: Wikipedia zum Sichtbarkeitspolygon .

darüber hinaus
quelle