Algorithmus zum zeichnen eines Polygons (2D)?
-
Um z. B. zu entscheiden, ob ein Punkt innerhalb eines Polygons liegt, betrachtet man die Summe der Winkel zwischen dem zu untersuchenden Punkt und allen Eckpunkten des Polygons.
Ist die Winkelsumme Null, so liegt der Punkt außerhalb des Polygons.
Bei überschneidungsfreien Polygonen beträgt die Winkelsumme für einen inneren Punkt 360°; bei sich überschneidenden Polygonen (wie etwa das Pentagramm) haben Punkte auf der Überschneidungsfläche ein Vielfaches davon.
-
Beim Dreieck ist der Ansatz mit den Winkeln aber nicht empfehlenswert, da es viel schnellere Algorithmen gibt. Unter www.geometryalgorithms.com findest Du was dazu.
Aber Dein Vorschlag ist doch nicht wirklich, Pixel für Pixel auf dem Bildschirm durchzugehen und zu prüfen, ob er sich innerhalb eines der zu zeichnenden Polygone befindet, oder? Das wäre doch absolut langsam... pro Pixel und pro Polygon wären dann etliche atan2's nötig.
Nein, man geht einfach jedes Polygon durch (dabei sollte es schon in Form von Dreiecken vorliegen) und zeichnet es Zeile für Zeile.
-
Ich habe ja auch keineswegs behauptet, daß der Algorithmus schnell sei.
Jedoch glaube ich, daß die bisherigen Lösungsvorschläge nur für die besonders gutartigen, konvexen Polygone problemlos funktionieren.
Aber was machst Du z. B. bei der mit "?" markierten Innenfläche des Pentagramms? Ausfüllen oder nicht? Und wie ist die Dreieckszerlegung?.........../|.......... ..........|*|.......... ..........|**\......... .--------/---+-------.. ..\*****|????|*****/... ....\***|?????\**/..... ......\/??????|/....... ......|*\????/|........ ...../****\/***\....... ....|****/..\**|....... ....|**/......\|....... ....|/.................
-
Original erstellt von Krösus:
Und wie ist die Dreieckszerlegung?Algo dafür:
solange in der Polylist nicht alles Dreiecke
nimm zwei Eckpunkte eine Polys
teile das Poly an der Verbindungslinie, wenn die keine Begrenzungslinie des Polys schneidetSo, jetzt kannste los-/zerlegen!
-
Original erstellt von Krösus:
Aber was machst Du z. B. bei der mit "?" markierten Innenfläche des Pentagramms?Ein Pentagramm stellt wohl eine Ausnahme dar. Ich glaube auch nicht, dass man es ohne "innere" Füllung (da, wo die Fragezeichen sind) irgendwie mit nur 5 verschiedenen Punkten darstellen kann. Entweder ganz ausfüllen (dann wäre es ein "normales" Polygon) oder - wenn Du die Fragezeichen nicht ausgefüllt haben willst - in 5 Dreiecke zerlegen.
-
Ein beliebiges Polygon einfach so in Dreiecke zu legen ist nicht so trivial, wie man es sich vielleicht denkt. Es darf einige Schritte, die nicht zu einfach sind. Der erste Schritt waere das Polygon in konvexe Polyone zu zerlegen, die dann sehr leicht zu triangulieren sind. Aber fuer das einen effizienten Alg. findet ist sehr schwer. Es wird dann dauer auf eine monotone Zerlegung ausgewichen, die rel einfach ist...blabla...einfach nicht so einfach. Aber wenn das Polygon eh nur aus 5 vertices besteht dann sollte jeder Triangulierungs-Alg. ausreichen.~tOmUsA
-
Original erstellt von tOmUsA:
Ein beliebiges Polygon einfach so in Dreiecke zu legen ist nicht so trivial, wie man es sich vielleicht denkt. [...]Selbst wenn es sehr kompliziert ist, so ist es doch viel sinnvoller eine solche Routine per Poly laufen zu lassen, als per Pixel eine Menge Zeit zu verschwenden.
-
Original erstellt von TGGC:
Ok, schreib ein Framework dazu!Was wie wo? Ich hab wollt nur ein Tip geben wie ihr die Diskussion lösen könnt, denn irgendwie dreht ihr euch im Kreis, denn beide behaupten stur ihre Lösung sei schneller.
-
Original erstellt von Lars:
[quote]Original erstellt von TGGC:
[qb]Ok, schreib ein Framework dazu!Was wie wo? Ich hab wollt nur ein Tip geben wie ihr die Diskussion lösen könnt, denn irgendwie dreht ihr euch im Kreis, denn beide behaupten stur ihre Lösung sei schneller.[/QB][/QUOTE]
Aber wie soll man das denn vergleichen, wenn nicht beide Routinen in dem selbem Framework laufen müssen? ICh behaupte ausserdem nix, ich sag nur wie es ist ;).
-
Dann entwerft doch beide zusammen ein Framework.
-
Original erstellt von Lars:
Dann entwerft doch beide zusammen ein Framework.Wieso, doofe Vergleich war doch deine Idee!
-
ich habe es schon öfters für mich getestet, beides nimmt sich nichts in performance.
bei meiner methode ist es lediglich einfacher, weil man convexe und concave polys zeichnen kann mit leichten code modifizierungen
die optimierung zum Zero-overdraw ist auch möglich (wie mit scanline algo)
rapso->greets();
