Ich muss den größten eingeschriebenen Kreis eines konvexen Polygons finden. Ich habe viele Sites durchsucht und habe festgestellt, dass dies mithilfe der Delaunay-Triangulation möglich ist. Ich habe einen ... gefundenFade in der CGAL-Diskussion mit einem Algorithmus, der CGAL verwendet:

Sie können dies mit CGAL leicht berechnen:

erechnen Sie zunächst die Delaunay-Triangulation der Punkt

Dann iteriere auf allen endlichen Flächen der Triangulation. Für jede endliche Fläche f

compute its circumcenter clocate c in der Triangulation (um die Dinge zu beschleunigen, können Sie einen Eckpunkt von f als Starthinweis für die Punktposition angeben)wenn das von locate (c, hint) zurückgegebene Gesicht endlich ist, dann liegt das Umkreiszentrum c in der konvexen Hülle der Punkte, also ist f ein Kandidatwenn f solch ein Kandidatengesicht ist, berechne seinen quadratischen Umkreis, behalte nur das Gesicht mit dem minimalen quadratischen Umkreis.

Das CGAL-Handbuch (Kapitel 2D-Triangulation, zusammen mit ein paar Dingen aus dem Kernel) zeigt alle grundlegenden Funktionen, um dies zu tun.

Ich war ein bisschen verwirrt mit dem letzten Teil dieses Algorithmus. Wenn ich es lese, verstehe ich daraus, dass der minimale Umkreis der Triangulationsfläche der Radius für den größten eingeschnittenen Kreis ist. Aus Beispielen für Polygone mit Delaunay-Triangulation geht jedoch hervor, dass selbst der kleinste Umkreis manchmal nicht in das Polygon passen kann. Wie kann dieser also denselben Radius haben wie der größte Inkreis?