Gemeinsame Fläche von vielen Dreiecken
-
Hallo,
Ich möchte gern die gemeinsame Schnittfläche von einigen Dreiecken berechnen. Die Dreiecke sind als Punktkordinaten 3*(x,y) vorhanden.
Ich dachte mir, ich bilde die Schnittpunkte aller Strecken von 2 Dreiecken, die daraus resultierende Fläche wird mit dem 3ten Dreieck verbunden (auch die Schnittpunkte), das dann mit dem 4ten Dreieck usw. Meine Frage: gibt es einen einfacheren Weg sowas zu tun oder geht das nur so?
-
Dreiecke sind Flächen.
=> Schnittmenge von nichtparallelen Dreiecken
sind Linien (2-dim)wie kommst du da auf Flächen?
Wenn du die Schnittmengen von verschiedenen Dreiecken
betrachtest haben diese i.a. keinen Schnittpunkt
-
er hat doch nur zwei dimensionen.
selbst wenn er drei hätte; nirgendwo steht, daß die dreiecke nicht parallel sein dürften.
-
Ich würd's so machen: die Dreiecke lassen sich als Schnitte von Halbräumen beschreiben. Also auch der Schnitt aller Dreiecke.
Du mußt also alle Halbräume miteinander verschneiden. Das geht vermutlich relativ flott, da man mit ein paar Tricks wahrscheinlich viel wegschneiden kann. Da der Schnitt konvex ist bekommst Du immer maximal zwei Schnittpunkte mit dem vorherigen Konstrukt wenn Du Schnitt für Schnitt eine Halbebene weiter schneidest.
Das klingt als wäre es noch relativ angenehm zu machen. Am Schluß kannste die Fläche einfach durchtriangulieren und die Fläche der Dreiecke berechnen. Das ganze Ding ist ja zum Glück konvex, also kannste einfach einen beliebigen Punkt innen reinsetzen und dann im Uhrzeigersinn (oder auch gegen ;)) die Eckpunkte durchgehen um zu triangulieren. Hört sich für mich nach Aufwand O(n*log n) an oder sowas.
MfG Jester
-
so wie jester es beschreibt wäre es wohl am optimalsten vom codingaufwand und der laufzeit.
Es gibt ein paar wenige implementierungen davon, findet man wenn man nach "c-buffer" sucht denk ich mir. als ich sowas mal implementiert hatte, gab es aber ein kleines problem, es gab nach der zerstückelung wirklich unmengen! an dreiecken die am ende rauskamen und ihre größe variierte sehr stark. deswegen kann man die genauigkeit der flächenerrechnung ein wenig erhöchen, wenn man die dreiecke vom kleinsten zum größten sortiert (nach der zerstückelung)
(war jedenfalls mein ansatz)btw. zum aufbauen des c-buffers ist es optimal, wenn man vom größten dreieck zum kleinstenn arbeitet, weil es dann weniger zerteilungen gibt -> weniger dreiecke -> schneller + genauer.
rapso->greets();
-
Ums noch etwas genauer zu erklären: Ich finde, je nach Position in der Ebene, etwa 3...10 Dreiecke in der Umgebung. Dreiecke, die sich nicht überlappen, werden nicht berücksichtigt. Beispiel:
***************************************** * * * * *** * * **** * * ***** * * **** * * **** * * ************************O**********O********************* *** * ************* * * *** ***************** * * **** ******************** * * * O********************* * * **** ****************** * * **** * *************** * * *** * *********** * * * * ******* * * * * *O * * * * * *** * * * * * *** * * * * * *** * * * * * *** * * * * * *** * * * * * *** * * * * * *** * * * * * *** * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *Die Fläche, d.h. die Punkte (die O's) möchte ich rauskriegen
-
@ scrub
Hab ich ganz übersehen
Ich arbeite z.Zt so viel mit dreiecken in 3d ,
dass ich schon an nichts anderes mehr denkn kann
-
@Mathe Null: Kannst Du mit dem was ich geschrieben habe was anfangen?
-
Teils/teils.
> Da der Schnitt konvex ist bekommst Du immer maximal zwei Schnittpunkte mit dem vorherigen Konstrukt wenn Du Schnitt für Schnitt eine Halbebene weiter schneidest <<
Wenn sich zwei Dreiecke überlappen bekomme ich in den meisten Fällen doch ein Viereck, also 4 Schnittpunkte, oder? Und was meinst du mit Halbebenen?
Also bisher mache ich das so:
1. Dreieck 1 + 2 --> Umrechnen von Eckpunkten der Strecken in allgemeine Geradengleichung --> Gleichsetzen --> Schnittpunkte/Fläche gefunden
2. Dreieck 3 --> Umrechnen von Eckpunkten der Strecken in allgemeine Geradengleichung --> Mit Strecken der vorherigen Form gleichsetzen --> neue Form gefunden usw....Bisher funktioniert das einigermaßen. Ich denke aber es gibt eine bessere Lösung, das scheint mir ziemlich umständlich zu sein.
-
Mit Halbebenen meine ich folgendes:
Wenn Du ne Gerade durch die 2D-Ebene liegst, dann teilt die diesen Raum ja in zwei Halbräume. Jetzt sagst Du, daß einer davon innen liegt, einer außen.
Ein Dreieck kannste jetzt als Schnitt von 3 solchen Halbräumen auffassen.
Wenn Du lauter Dreiecke schneiden willst ist das genauso wir wenn Du diese ganzen Halbräume schneidest.Man sieht halt relativ gut wie das scheiden da funktioniert. Da die Schnittmenge immer konvex ist es so, daß eine Kante des Schnitts eine Gerade schneidet genau dann wenn ein Endpunkt auf der einen Seite liegt und der andere auf der anderen. Ist das nicht der Fall brauchste garnicht schneiden. Weil der Schnitt konvex ist geht der Rand höchstens zweimal über die Schnittgerade. Einmal rüber und wieder zurück. Das gibt dann genau die zwei Schnittpunkte. Mit ein bißchen Glück schneidet das ein paar Eckpunkte ab und ie Schnittfläche wird sogar wieder einfacher.
Dazu müßte es eigentlich auch einiges an fertigen Algorithmen geben.