Ich versuche gerade, die abgeschnittenen Zellen von einer Polygon-Voronoi-Kreuzung zu erhalten.

Hier ist was ich bisher habe:

Ich habe ein Polygon und habe einige Punkte darin berechnet, um ein Voronoi-Diagramm zu berechnen. Die roten Linien in der Abbildung unten sind die Voronoi-Kanten. Dann habe ich einen Algorithmus verwendet, um die Eckpunkte von jeder Zelle zu erhalten, und jetzt muss ich die Ecken in die richtige Richtung bringen (im Uhrzeigersinn), um das Zellenpolygon zu erzeugen.

Found Corners für eine Zelle

Zunächst habe ich diese Methode verwendet:

private List<Vector> sortClockwise(List<Vector> points)
    {
        points = points.OrderBy(x => Math.Atan2(x.X, x.Y)).ToList();
        return points;
    }

aber in einigen speziellen konkaven Polygonen funktioniert dies nicht und die richtige Reihenfolge wird verwechselt.

Hat jemand einen Vorschlag oder einen Hinweis, wie dies am einfachsten zu bewerkstelligen ist? Bedenken Sie, dass die Polygonpunkte bereits in der richtigen Reihenfolge sind und die voronoi-Ecken vertauscht sind und nach den Polygonpunkten sortiert werden müssen.

Meine Idee

Ersten Polygonpunkt in Zellecken findenehen Sie entlang der Polygonrichtung und prüfen Sie, ob sich der Punkt der voronoi-Scheitelpunkte auf dieser Linie befindewenn ja: Endpunkt der gefundenen Voronoi-Kante abrufen und nach gemeinsamen Voronoi-Kanten suchen.wenn gemeinsame Kanten gefunden werden, nimm immer die am besten geeignetedo bis zum ersten Punkt

Ist das der einzige Weg, wie ich das machen könnte?

EDIT - UPDATE

Okay, ich habe jetzt eine Art halbe Antwort.

Wie ich schon sagte, ich habe alle Eckpunkte, die zu einer der voronoi-Zellen gehören, aber die Reihenfolge ist immer noch durcheinander, so dass ich dachte, ich könnte sie vom Schwerpunkt aus wie folgt nach Winkel sortieren:

private List<Vector> sortClockwiseBySentroid(List<Vector> points, Vector center)
    {
        points = points.OrderBy(x => Math.Atan2(x.X - center.X, x.Y - center.Y)).ToList();
        return points;
    }

Aber das funktioniert nicht immer. Hier sind die Beispiele, wann es funktioniert und wann nicht. Das Problem ist, dass bei konkaven Kanten der Winkel vom Zentorid zur Ecke manchmal kleiner ist als der, den ich wirklich brauche. Irgendwelche Vorschläge, wie man das behebt?

Hier arbeitet es

Hier funktioniert es nicht ...