Berechnung der Fläche von aeinfach unregelmäßig Polygonist trivial. Betrachten Sie jedoch das sich selbst schneidende Polygon ABCDEF, das links unten dargestellt ist:

                   

Wenn wir die verknüpfte Formel über dem Durchlaufen der Punkte in Polygonreihenfolge verwenden, erhalten wir eine Fläche von 0. (Die Fläche im Uhrzeigersinn löscht die Fläche gegen den Uhrzeigersinn.)

Wenn wir jedochSortieren Sie die Punkte radial um einen Mittelpunkt und berechnen Sie die Fläche, erhalten wir die falsche Fläche des Polygons ABEDCF rechts oben.

Wie finde ich den sichtbaren Bereich eines sich selbst schneidenden Polygons am besten? (Wenn die Antwort die Erstellung von Phantompunkten für jede Kreuzung erfordert, geben Sie bitte Einzelheiten an, wie Sie die Kreuzungen am besten finden und wie Sie sie dann in der richtigen Reihenfolge durchqueren.)

Diese Frage stellte sich bei der Untersuchung von Randfällen für meine Lösungdiese Frage.

Bereich definieren

Ich definiere den 'Bereich' als die Menge der sichtbaren Pixel, wenn das Polygon mit den Regeln "ungleich Null" oder "gerade Null" gefüllt wird. Für beides werde ich eine Antwort akzeptieren, obwohl beides besser wäre. Beachten Sie, dass ich das ausdrücklich tuenicht Definieren Sie den Bereich für die Selbstüberlappung, um den Überlappungsbereich zweimal zu zählen.