Das Problem mit dem konvexen Polygon ist ja, dass wir nicht davon ausgehen dürfen, dass die (orangen) Punkte bereits in einer richtigen (gültigen) Reihenfolge vorliegen. Liegen sie nämlich nicht in Reihe, führt das zu "falschen Diagonalen", wie du das Problem treffend benannt hast.
Der Trick ist nun, einfach dafür zu sorgen, dass unsere orangen Punkte immer "in Reihe" liegen.
Wenn man den Prozess vom Finden eines Schnittpunktes lapidar als "Frage" (Im Sinne von, Frage an den Computer) bezeichnet, muss man also blos die sich wiederholenden Fragen in der richtigen Reihenfolge stellen. Denn: Fragen muss ich ja ohnehin. In welcher Reihenfolge ich welche Fragen nun stelle, wird sich also in diesem Punkt auch nicht negativ auf die Laufzeit auswirken. Was für uns natürlich ein wünschbarer Nebeneffekt ist!
Auf die Lösung bin ich gekommen, weil ich mir folgende Szene konkret vorgestellt hatte. Und da ich glaube, dass es so auch anschaulicher und einfacher zu erklären ist, will ich bei diesem Bild bleiben.
Wir stellen uns vor, wir seien eine Ameise, die eine bestimmte Strecke ablaufen soll. Dabei bewegt sich die Ameise nur entlange der geometrischen Strecken, die uns das Quadrat und das Dreieck vorgeben. Auch bewegt sich die Ameise immer nur in der Richtung, in die der Strecken-Vektor zeigt (auf welchem sie sich gerade befindet). Diese Regel ist wichtig - mehr dazu später.
Nach folgendem Rezept, wird die Ameise nun das Polygon garantiert in einer gültigen Reihenfolge ablaufen:
1) Die Ameise schnappt sich einen beliebigen Punkt des Dreieck und prüft diesen darauf, ob sich dieser im Pixel-Quadrat befindet. Denn: Das Rezept funktioniert nur dann, wenn die Ameise garantiert ausserhalb des Pixel-Quadrates startet.
Sollte der gewählte Eckpunkt des Dreieckes tatsächlich im Quadrat liegen, nimmt sie einfach den nächsten und prüft diesen ebenfalls.
Falls sich dann auch beim 3 Eckpunkt herausstellen sollte, dass auch dieser im Quadrat liegt, ist die Aufgabe bereits beendet. Denn dann gilt:
Pixelhelligkeit = Dreiecksfläche.
Ich schreibe das so ausführlich, weil wir an dieser Stelle netterweise ohne Mehraufwand einen "Spezialfall" loswerden.
2) Hat die Ameise nun einen Eckpunkt des Dreiecks (Startpunkt) gefunden, der ausserhalb des Pixelquadrates liegt, läuft sie in Richtung des Strecken-Vektors los (zu den Vektoren später mehr).
3) Die Ameise läuft nun so lange weiter, bis sie auf eine Kreuzung (einen Strecken-Schnittpunkt) trifft. Sollte sie auf dem "zweiten" Eckpunkt des Dreicks angekommen - ohne auf eine Kreuzung getroffen zu sein, läuft sie einfach auf dem neuen Strecken-Vektor weiter. Natürlich auch wieder in der Richtung, in welche der Strecken-Vektor zeigt. Trifft sie aber auf eine Kreuzung, macht sie folgendes: *trommelwirbel* ... Sie markiert die Kreuzung mit einem orangen Punkt (ab hier beginnt das Punktesetzen) und... ... läuft einfach weiter! Dieser Schritt ist in einem gewissen Sinne speziell: Denn nur bei der ersten Kreuzung läuft sie einfach weiter geradeaus. Denn so befindet sie sich nun mit Sicherheit im Quadrat.
4) Die weitere Reise ist nun absolut simpel. Trifft die Ameise auf eine Kreuzung, markiert sie diese mit einem orangen Punkt und biegt ab, in Richtung "Vektoren-Laufrichtung". Um in der Bildsprache zu bleiben: Sie _muss_ abbiegen, darf aber _nicht_ in die Strasse mit der "verbotenen Fahrtrichtung".
Trifft sie auf keine Kreuzung, sonder auf eine Ecke (was anderes ist nicht möglich), markiert sie diese Ecke mit einem orangen Punkt und geht weiter.
5) Erreicht die Ameise eine Kreuzung, die bereits mit einem orangen Punkt markiert ist, ist die Reise beendet und das Polygon in einer "gültigen" Reihenfolge abgelaufen.
Wenn man nun die Ameise beobachtet, dann gehören die Pfade, auf denen sie läuft, entweder zum Dreieck oder zum Quadrat. Aber das ganze interessiert sie gar nicht - und sie weiss davon auch nichts. An einer Kreuzung welchselt sie einfach von Dreickspfad zu Pixelpfad oder umgekehrt.
Am Ende der Prozedur hättest du dann nicht nur die Eckpunkte eines konvexen Polygons, sondern auch eines, bei dem die Punkte garantiert in Reihe liegen - und damit die Flächenberechnung ein Klacks ist.
Einzig müsste man noch testen - nur Falls man keinen einzigen Schnittpunkt gefunden hat, ob einer der Quadratpunkte (es reicht ein einzelner, beliebiger), sich im Dreeick befindet.
Dann gälte: Pixelhelligkeit = 1.0
Das ist die Idee. Konkret für den Algorithmus würde das bedeuten, dass ich immer einen Strecken-Vektor als auserkorenen Kandidaten habe, mit welchem ich dann die anderen Vektoren auf Schnitt kontrolliere. Finde ich den Vektor mit dem räumlich nächsten (wichtig!) Schnittpunkt, wird dieser Vektor zu meinem neuen erkorenen "Haupt-Kadidaten" (mit diesem prüfe ich dann wieder die Anderen).
An dieser Stelle gibt es bestimmt weitere Optimierungsmöglichkeiten, die evident sein müssten. Denn wenn z.B. mein aktueller "Haupt-Kandidat" eine Line des Quadrates ist, muss man ja diesen Vektor nicht mit den weiteren Quadrat-Linien auf Schnitt testen.
Mir schwebt so eine Art verkettete Liste vor, die durchlaufen wird. Treffe ich auf eine Kreuzung, hänge ich etwas in dieser Liste um. Aber die Idee ist noch etwas halbgar und allenfalls zu umständlich. Alternativ könnte man mit geraden und ungeraden Listen-Einträgen (Liste mit Vektoren) arbeiten. Dabei besetzen die Dreicks-Vektoren die ungeraden und die Quadrat-Vektoren die geraden Listeneinträge. gerade auf gerade wird ebenso wenig getestet wie ungerade auf ungerade. Nur so als "Skizze"...
Eine wichtige Sache hatte ich blos gestreift, nicht aber konkret erklärt:
Das Rezept setzt voraus, dass der "Drehsinn" von Quadrat und Dreieck (also deren Vektoren) der selbe ist.
Ich glaube die Grafik zeigt dies recht anschaulich. Wenn ich die Punkte des Dreiecks nach ihren Einträgen im Buffer ablaufe (egal, bei welchem ich auch starte) ergibt sich daraus ja zwangsläufig ein räumlicher Drehsinn. Dieser muss der selbe sein, wie beim Quadrat!
Als Vorbereitung für die Szene muss man also einmal überprüfen, ob der Drehsinn des Dreiecks dem des Quadrates entspricht (letzteres ändert sich ja nicht). Sollte dies nicht der Fall sein, muss man die Vertices des Dreickes im Buffer "rückwärts" auslesen.
Eine weitere Sache habe ich jetzt noch nicht angesprochen, da ich mir auch gar nicht sicher bin, ob deine Idee nicht schneller ist. Aber Falls dir der Ansatz gefällt, müsste man sich noch überlegen, wie man mit der Siutation umgeht, wenn ein Dreickseckpunkt genau auf einer Quadratlinie zu liegen kommt. Ich sehe hier aber bereits Ansätze, wie sich das Problem relativ einfach lösen liese.