Polygon berechnen

[cumi]

Sali Zeme

Ich hab da wiedermal ein intressantes Problem (oder hoff ich zumindest).

Also ich möchte auf einem TBitMap32 (<--- ohne Canvas!!!) ein Polygon berechnen. Und dann jeden Punkt mit einer verschiedenen Transparenz einfärben, welche mit einwenig Vektorgeometie ermittelt wird.

Ich muss also für jeden Punkt auf meinem TBitMap32, welches im Polygon liegt ein paar Berechnungen druchführen und diesen dann färben.

Das Polygon kann für den Anfang mal konvex sein. Und wenns dann konkav wird zerleg ich es falls notwenig einfach in Dreiecke.

Mir sind dazu bis jetzt zwei Varianten eingefallen:
1. Ich habe eine Formal hergeleitet (über das Vektorprodukt) mit welcher ich überprüfen kann ob der gesuchte Punkt inerhalb oder ausserhalb des Polygons liegt. Dies dauert jedoch einwenig und ich muss es für jeden Punkt ausrechnen. (also eigentlich reicht es ja bei jeder Zeile von links den ersten und von rechts den letzten zu finden und dann sind die dazwischen (weil konvex) auch drinn)
2. Ich berechne mit Vektorgeometrie der erste und leste Punkt jeder Zeile uns dann sind alle Punkte dawischen auch im Polygon (weil konvex).

Diese Varianten sind aber leider ziemlich mühsam zum implementieren und erstnoch langsam.

Hatt jemand eine bessere Idee? Welche ev. schon implementiert ist (Sprachen: Delphi, C++, Java oder so)?

Vielen Dank für eure Hilfe!

Grüsse cumi

[dizzy]

Mir würde da spontan auch nichts besseres zu einfallen. Hier sind noch 2 Varianten zur Prüfung ob ein Punkt in ein Polygon gehört, evtl. lässt sich da ja was abgucken und die Geschwindigkeit verbessern.
Die G32 bietet zudem auch Funktionen an um Polygone zu zeichnen, jedoch nehme ich an, dass sie deinem Wunsch nach entsprechender variabler Transparenz nicht ganz gerecht werden. Aber du kannst damit ja z.B. zunächst ein schwarzes Poly auf weissen Grund zeichnen (offscreen), und schon hast du alle Punkte die zum Poly gehören - nämlich die schwarzen. Anhand derer kann man dann ja weiter machen.

Gruss,
Fabian

[cumi]

hoi dizzy, vielen dank für deine hile. Du warst der, der mir der geniale Tipp von der GR32 gegeben hast, damal beim Mandelbrot ^^

Die offscreen-Variante gefällt mir nicht so, da ich die Berechnung vom effektiven zeichnen möglist loslösen möchte und beim berechnen immer ein BitMap zu instanzieren ist ja auch nicht besonders schlau.

Vielen Dank aber für den Link. Die zweite Varinate dort sieht super aus. Ich denke die ist schneller, als dijene, dich ich von meinen Berechnung abgeleitet hätte.

Da ich eine konvexe Figur habe werde ich es so machen, dass ich bei jeder Zeile von links beginne und den ersten Punkt und analog von rechts den letzten Punkt der Zeile suche und diese und die dazwischenliegenden "anmale".
Zudem denke ich, dass es schlau wäre, du bestimmen, in welchem Feld (also ein recheckiger Ramen um das Polygon machen) sich das Polygon befindet und nur dort drinn zu prüfen.

Fällt sonst noch jemandem eine Verschnellerung ein?

Danke für eure Hilfe!
cumi

[Flogo]

Hey cumy,
bist du mittlerweile schon weitergekommen? Ich hab mich vor kurzem auch mit Polygonen beschäftigt und hänge grade an dem Problem ein konkaves Polygon in mehrere konvexe zu zerlegen

Zitat von cumi:

Das Polygon kann für den Anfang mal konvex sein. Und wenns dann konkav wird zerleg ich es falls notwenig einfach in Dreiecke.

Hast du das schon hinbekommen? Wie siehts mit dem Rest aus? funktioniert alles? Wenn nicht kann ich dir vllt mit meinem bisherigen Code aushelfen.

[cumi]

Hoi Flogo

Nein, ich bin eigentlich nicht wirklich weiter gekommen. Ich habe es dann auf die "billige" Art programmiert und einfach ein TBitmap genommen und dort mit der Canvas.Polygon Funktion das Polygon gezeichnet und dann das ganze Pixelweise übertragen. Dies ist jedoch ziemlich langsam, da der Zugriff auf einen Pixel von einem TBitmap ziemlich langsam ist.
Doch da der Efekt sowieso nicht so gut aussieht, wie ich es mir erhofft habe, habe ich dann nicht mehr weiter programmiert.

Wie man so ein konkaves Polygon zerlegt kann ich dir nicht gleich aus dem Stehgreif sagen, aber vielleicht überleg ich mir das in den nächsten zwei Tagen noch (ich habe gleich Ferien).

Grüsse cumi

[Flogo]

Mein Ansatz dabei war

Code:

erstelle Liste der Linien
schneide jede Linie mit jeder
bei einem Schnittpunkt (x) ungleich den Start (s) und Endpunkten (e) 
  zerlege beide Linien in zwei Teile (s)->(x) und (x)->(e)

Das ganze klingt mir aber noch irgendwie zu uneffektiv.
Liste aller Linien heißt ja schon dass die Punkte alle doppelt vorkommen und dann jede Linie mit jeder zu schneiden dauert sicher auch seine Zeit.
Außerdem weiß ich nicht wie ich nachher feststellen soll in welcher Reihenfolge ich die Linien wieder zusammensetzten muss um die richtigen Polygone zu erhalten