Was ist für einen Punkt in einem konkaven Polygon der nächstgelegene Punkt außerhalb des Polygons?

Question

Ich habe einen Punkt innerhalb eines konkaven Polygons und ich möchte den nächsten Punkt zu finden, die nur außerhalb des Polygons ist. Ich habe die Antwort implementiert in: For a point in an irregular polygon, what is the most efficient way to select the edge closest to the point?, aber das findet den nächsten Punkt auf einer Polygonkante, nicht außerhalb des Polygons.

ich versuchte, gerade innerhalb des Polygons auf der Kante zu dem Punkt, die Linie von dem Punkt erstreckt, aber es gibt Fälle, in denen das nicht funktionieren.

Irgendwelche Vorschläge?

BEARBEITEN: Um es klarer zu machen, habe ich einen Punkt innerhalb eines konkaven oder konvexen Polygons, und ich möchte einen Punkt außerhalb des Polygons finden, so nah wie möglich an dem Punkt im Inneren. In der unteren Abbildung möchte ich den roten Punkt finden. Es muss nicht perfekt in der Entfernung minimiert werden, sondern muss nur draußen und nicht zu weit vom ursprünglichen Punkt entfernt sein. Vielleicht um einen festen Betrag?

Answer 1

Ansatz mit Verlängerung der Linie nach außen gut genug für die meisten Fälle sieht

Wenn Sie feststellen, dass der nächste Punkt Ecke, nur um äußere Punkt bei Winkelhalbierende äußeren Winkel.

Answer 2

Im Fall, dass Sie mehrere Abfragen können Sie die Voronoi diagram des Polygons berechnen (es gibt eine CGAL implementation). Dann können Sie nachsehen, in welcher Voronoi-Zelle der Abfragepunkt liegt. Sie erhalten die nächstgelegene Eingangskante als Standort für diese Zelle. Wenn Sie das Voronoi-Diagramm auch außerhalb des Polygons berechnen, können Sie einfach einen Punkt in der Nähe dieser Stelle von den Kanten außerhalb der Zelle nehmen.