Kollision von 2 Dreiecken |
| 06.08.2005, 23:26 | Simeon | Auf diesen Beitrag antworten » | ||||
| Kollision von 2 Dreiecken ich verzweifle noch an diesem mist. Ich versuch seit einer Woche rauszukriegen wie man das ausrechnet. Also: Aufgabenstellung: Ich muss rausfinden ob 2 beliebig geformte und rotierte Dreiecke miteinander Kollidieren. Gegeben: Beim einen Dreieck weiß ich die Koordinaten. Beim anderen weiß ich die Koorinaten von seinem Schwerpunkt als 0,0 gesehen und den Ortsvector um den der Schwerpunkt des Dreiecks vom echten 0,0 verschoben ist. Gesucht: Kollision oder eben nicht. Bitte helft mir, ich krieg das einfach nicht gebacken! |
||||||
| 06.08.2005, 23:29 | Egal | Auf diesen Beitrag antworten » | ||||
Mal versuchen zu sortieren. Du hast 2 (identische?) Dreiecke und weisst von einem die Koordinaten und vom anderen nichts ausser dem Schwerpunkt im Vergleich zum Ursprung? |
||||||
| 06.08.2005, 23:46 | Simeon | Auf diesen Beitrag antworten » | ||||
Nein die Dreiecke sind alle total variable, ich sagte doch beliebig geformt und beliebig gedreht. Es sieht also so aus:  http://www.ppc-zone.de/drei.jpg |
||||||
| 06.08.2005, 23:51 | Egal | Auf diesen Beitrag antworten » | ||||
Ich fürchte ich muss dir mitteilen das dein Problem nicht lösbar ist. Insbesondere deswegen weil die Angaben für dein eines Dreieck nicht ausreichend sind ums vollständig zu beschreiben. |
||||||
| 06.08.2005, 23:54 | Simeon | Auf diesen Beitrag antworten » | ||||
Das stimmt aber nicht. Bei welchem Dreieck soll es denn nicht ausreichend sein? |
||||||
| 06.08.2005, 23:57 | jovi | Auf diesen Beitrag antworten » | ||||
Kannst Du die Angaben mal komplett hinschreiben ? Wenn alles Grüne gegeben ist, dann sind doch beide Dreiecke bekannt ? |
||||||
| Anzeige | ||||||
|
|
||||||
| 07.08.2005, 00:00 | Egal | Auf diesen Beitrag antworten » | ||||
Ein Dreieck bei dem Ich ausser dem Umkreismittelpunkt und dem Radius des Umkreises nichts kenne ist eben nicht eindeutig bestimmt. Ich kann 3 beliebige Puntke auf dem Kreis immer zu einem Dreieck verbinden und hätte somit das Kriterium erfüllt das die entsprechenden Angaben bekannt wären. |
||||||
| 07.08.2005, 00:04 | jovi | Auf diesen Beitrag antworten » | ||||
Ich hab das so verstanden, dass von beiden Dreiecken die Eckpunkte bekannt sind. |
||||||
| 07.08.2005, 00:08 | Egal | Auf diesen Beitrag antworten » | ||||
Dann hätte ich zumindest eine wenn auch nicht unbedingt nur schöne Lösung. |
||||||
| 07.08.2005, 00:11 | Simeon | Auf diesen Beitrag antworten » | ||||
Sind ja in gewisser weise auch alle bekannt. Der Vector, ist ja nichts weiter als ein Verschiebevector der praktisch für das eine Dreieck nur den Nullpunkt irgendwo anders hin verschiebt, und von diesem neuen Null-Punkt aus, der gleichzeitig immer der Schwerpunkt des Dreiecks ist, gehe ich denn die Abstande ab. Diese Abstände sind kein Radius o.ä. sondern Koordinaten, da steht doch hinter Abstand (x,y) also ist alles bekannt was ich brauche um es zu 100% beschreiben zu können! |
||||||
| 07.08.2005, 00:14 | jovi | Auf diesen Beitrag antworten » | ||||
Mach doch bitte mal ein konkretes Beispiel, ich bin mir nicht ganz sicher was du mit rotiert und Kollision meinst. |
||||||
| 07.08.2005, 00:19 | Simeon | Auf diesen Beitrag antworten » | ||||
Lol, ich hab doch ne Zeichnung gemacht, und in der ist natührlich keine Kollision. Das rotieren denk dir einfach weg, damit meinte ich nur das das Dreieck nicht unbedingt die Spitze oben haben muss sondern eben alles total variabel ist, aber wärend der Berechnung ob sie Kollidieren rotiert natührlich garnichts, da wird einfach nur gefragt ob die kollidieren oder nicht. Ich weiß nicht was ich da für ein Beispiel geben soll, da oben ist doch eins, da wird nicht mit Zahlen gerechnet sondern nur mit Buchstaben wenn du das mit "Beispiel" meinst. |
||||||
| 07.08.2005, 00:26 | JochenX | Auf diesen Beitrag antworten » | ||||
ich hab das jetzt nicht alles genau verstanden, was ihr da redet; erst mal zur aufgabenstellung: du willst also nur herausfinden, ob diese dreiecke einen punkt gemeinsam haben? nennst du das "kollidieren"? vorschlag: dreiecke seien ABC, DEF bevor ich mehr sage, erst mal die frage: eckpunkte sind alle bestimmbar (s. skizze) (?) oder verstehe ich da die angaben nicht (?) |
||||||
| 07.08.2005, 00:27 | jovi | Auf diesen Beitrag antworten » | ||||
du verwendest doch mehrere Koordinatensysteme - sind die zueinander verdreht ? Ja mit Beispiel hatte ich Zahlen gemeint, aber du willst es allgemein bestimmen, ob sie sich schneiden oder ? |
||||||
| 07.08.2005, 00:48 | Simeon | Auf diesen Beitrag antworten » | ||||
So also ich habs versucht zu verdeutlichen: Beispiel mit Zahlen: (Dort gibt es keine Kollision) http://www.ppc-zone.de/drei1.jpg (Da sind halt die Koordinaten der Eckpunkte von dem einen Dreieck relativ zu dem Vector dessen Spitze als 0,0 genutzt wird.) ACHJA: Ich hatte mich geirrt, der Vector zeigt NICHT zum Schwerpunkt wie man sieht, aber das ist ja auch für die Aufgabe unwichtig! Beispiele was Kollision ist und was nicht: http://www.ppc-zone.de/drei2.jpg Und ja ich möchte eine allgemeine Lösung, also ohne Zahlen sondern mit Buchstaben. |
||||||
| 07.08.2005, 01:01 | jovi | Auf diesen Beitrag antworten » | ||||
O.k. jetzt habe ichs verstanden. Kollision ist also wenn sich mindestens eine der Seiten des 1.Dreiecks mit mindestens einer der Seiten des 2. Dreieckks schneiden. Dann musst du also testen, ob sich die den Seiten entsprechenden Strecken schneiden - also maximal 9 Tests. |
||||||
| 07.08.2005, 01:04 | Simeon | Auf diesen Beitrag antworten » | ||||
Ja aber wie mach ich das im Detail? 
|
||||||
| 07.08.2005, 01:19 | jovi | Auf diesen Beitrag antworten » | ||||
Mein Vorschlag: 1.) die Punkte in ein gemeinsames Koordinatensystem bringen 2.) Jede der 6 Seiten parametrisieren, also etwa so mit 3.) Dann die Seiten des 1. Dreiecks mit denen des 2. schneiden Das ergibt dann jeweils ein lin. Gleichungssystem. Falls eine eindeutige Lösung für t und v existiert und t und v jeweils zwischen 0 und 1 liegen, dann schneiden sie sich. |
||||||
| 07.08.2005, 01:24 | Simeon | Auf diesen Beitrag antworten » | ||||
Und jetzt nochmal bitte für einen dummen 11. Klässler. 
Ich scheitere ja schon dabei das in ein gemeinsames Kood. System zu konvertieren 
|
||||||
| 07.08.2005, 01:40 | jovi | Auf diesen Beitrag antworten » | ||||
Da musst du dann schon etwas konkreter werden, wie deine Daten vorliegen - so wie ich deine Zeichnungen verstehe musst du nur die Punkte des vom Vektor verschobenen Dreiecks jeweils mit den Vektor addieren. In deinem Beispiel auf der Zeichnung: (0/1) + (2/-2) = (2/-1) (-1/-1) + (2/-2) = (1/-3) (1/-1) + (2/-2) = (3/-3) |
||||||
| 07.08.2005, 01:48 | Simeon | Auf diesen Beitrag antworten » | ||||
Achso, ja soweit hab ich das schoma verstanden und was genau ist dieses parametrisieren und der Rest? |
||||||
| 07.08.2005, 01:53 | jovi | Auf diesen Beitrag antworten » | ||||
die 2 Punkte der Strecke seien (x1/y1) und (x2/y2), dann wäre so eine Parametrisierung der Strecke (x1/x2) + t * (x2-x1/y2-y1) mit 0<=t<=1 das bedeutet, jedes t zwischen 0 und 1 entspricht einem Punkt der Strecke. |
||||||
| 07.08.2005, 01:57 | Simeon | Auf diesen Beitrag antworten » | ||||
Das sieht ja merkwürdig aus und was bringt mir das? Sorry aber wie gesagt hatte das nochnet inner Schule. |
||||||
| 07.08.2005, 02:01 | jovi | Auf diesen Beitrag antworten » | ||||
Nun kannst du 2 solche Strecken gleichsetzen und damit testen, ob sie sich schneiden 
Ein Gleichungssystem mit 2 Unbekannten hattest du ja sicher schon in der Schule oder ? Versuche einfach mal damit 2 Dreiecksseiten deines Beispiels zu schneiden - dann können wir dir sagen ob es richtig ist. |
||||||
| 07.08.2005, 02:16 | Simeon | Auf diesen Beitrag antworten » | ||||
Ja aber ich frag mich wie du auf die Gleichung kommst, sie ist doch richtig so oder?  http://www.ppc-zone.de/para.jpgDie sieht so...naja die sieht irgendwie anders aus als erwartet. Und ja ich kann 2 Gleichungen mit 2 Unbekannten lösen. Aber das da oben is keine Gleichung, wo is das "=" ? Und wenn du sie wie ganz oben gleichsetzt hab ich ja eine Gleichung mit 2 Unbekannten. Also sowas ham wa nochnet gemacht. |
||||||
| 07.08.2005, 02:27 | JochenX | Auf diesen Beitrag antworten » | ||||
verwechselst du heir vielleicht brüche mit 2-komponentigen vektoren? 2 komponenten, am ende 2 gleichungen, für jede komponente eine..... das was du da stehen hast ist übrigens so keine gleichung du musst jeweils eine seite eines dreieckes mit einer seite des anderen vergleichen (d.h. gleichsetzen) was du hier an sich machst: du bildest die geraden, die die seiten der dreiecke enthalten (erkennst du die form aus der geometrie? ortsvektor + vielfaches des richtungsvektors) dann kannst du die geraden paarweise schneiden (eine gerade eines dreiecks mit einer des anderen dreiecks) der schnittpunkt ist aber nur dann ein kollisionspunkt, wenn er innerhalb der seitenstrecke liegt und nicht irgendwo außerhalb (die gerade ist ja viel mehr als die seite) jetzt mal weiterdenken mfg jochen ps: hattest du überhaupt schon vektoren und diese geometrischen dinge? |
||||||
| 07.08.2005, 02:37 | Simeon | Auf diesen Beitrag antworten » | ||||
Nö, ich hatte noch keine Vectorrechnung bringe sie mir jedoch gerade bei wie auch den Gauß-Jordan-Algorythmus, den ich gerade gelernt hab. Und ja, ich hab gedacht jovi meint Brüche. Denn ich hab Probleme damit das es 2 Punkte und 2 Vectoren sein sollen also ganz oben als jovi mit latex die Vectoren geschrieben hat, da gabs ja v0 und v1. Aber wieso wird eine linie durch 2 Vectoren beschrieben das versteh ich nicht! Schließlich ist der Vector an sich ja scho ne Linie. Die hat aber einen ganz variablen Schaft, daher sieht das ganze für mich ein wenig verwirrend aus. |
||||||
| 07.08.2005, 02:41 | JochenX | Auf diesen Beitrag antworten » | ||||
ehrlich gesagt, glaube ich, dass es dann schwer wird, dass zu erklären wieso machst du solche aufgaben zum beginn der vektorrechnung? also ohne nötiges wissen aus der vektorrechnung führt dieser ansatz kaum zum erfolg.... wenn du sie dennoch machen willst, dann schau dir folgende themen an: -vektoren in der reellen ebene -geraden in parameterdarstellung (mit vektoren) -schnit solcher geraden mfg jochen |
||||||
| 07.08.2005, 02:49 | Simeon | Auf diesen Beitrag antworten » | ||||
Du siehst es falschrum *g* Ich will nicht mit solchen Aufgaben die Vectorrechnung lernen. Sondern ich muss die Vectorrechnung lernen (das war mir ja von Anfang an klar) um die Aufgabe zu lösen. Ich versuch seit einer Woche ne Kollisionsabfrage dafür hinzubekommen und auf dieser langen "Reise" hab ich halt das ein oder andere der Vectorrechnung usw gelernt. Ich wäre dir wirklich sehr dankbar wenn du das einfach nochmal kurz erläuterst und die Aufgabe zuende führst. Es geht mir hier nämlich weniger darum ein mathematisches Problem zu lösen sondern darum Kollisionen zu überprüfen in einer Welt aus Dreiecken. (Für ein Programm) Aber ich werd natührlich trotzdem versuchen Infos über die von dir genannten Themen zu finden. |
||||||
| 07.08.2005, 03:24 | JochenX | Auf diesen Beitrag antworten » | ||||
hmm, nein, rechnen kannst du das selbst; implementieren musst du es dann sowieso selbst ich poste dir noch mal "das Kochrezept" hier, aber dafür musst du wirklich erst mal etwas vektorrechnung verstehen: 1) geraden aufstellen, die die seiten enthalten (ergibt für jedes dreieck 3 seiten) und zwar mittels der beiden punkte durch die sie gehen der ortsvektor des einen ist der stützvektor, der vektor von diesem punkt zum anderen der richtungsvektor 2) jeweils eine gerade eines dreiecks mit einer des anderen schneiden (9 kombinationen) 3) unter der annahme, dass wir keine parallelen seitenpaare haben: 9 schnittpunkte, diese müssen auf kollisionen geprüft werden sobald eine kollision gefunden ist, muss nicht weitergerechnet werden, dann positiv negativ, wenn alle 9 kombinationen keine kollision liefern dazu: ein schnittpunkt ist dann eine kollision, wenn er zusätzlich zu den beiden seitenverlängernden geraden auf beiden seiten selbst liegt er liegt (jeweils!) auf der seite selbst wenn der zugehörige parameter zwischen 0 und 1 liegt sollte ein paralleles seitenpaar vorliegen: identisch => positiver befund nicht identisch => dieses seitenpaar kann ignoriert werden mfg jochen ps: @jovi, wenn du wieder ausgeschlafen zurück bist schaus dir doch noch mal an, genau so meintest du das, oder? |
||||||
| 07.08.2005, 07:15 | Simeon | Auf diesen Beitrag antworten » | ||||
Gut habs gelernt, ich wäre sehr erfreut wenn ihr mal eben rübergucken könntet, ob das so richtig ist.  http://www.ppc-zone.de/sys2.jpgSo jetzt prüf ich ob s und t beide zwischen 0 und 1 liegen. Wenn ja setze ich sie in die Gleichung bei der ich beide Geradengleichungen gleichgesetzt habe ein und wenn die Gleichung auf geht also auf beiden Seiten das gleiche steht gibt's ne Kollision, sonst nicht. Und das mache ich halt mit allen Seiten. *hofft das es richtig ist und die Nacht nicht umsonst war* mfg Simeon |
||||||
| 07.08.2005, 12:22 | jovi | Auf diesen Beitrag antworten » | ||||
@LOED: genauso habe ich das gemeint.
@Simeon: scheint alles richtig zu sein - viel Erfolg bei deinem Programm ! 
Ja genau, nur musst du natürlich vorher testen , ob dein Nenner bei t = ... 0 wird. Dann sind die beiden Seiten parallel zueinander und du musst noch testen ob die Eckpunkte einer Seite in der anderen liegen.
Das scheint mir unnötig zu sein. |
||||||
| 07.08.2005, 12:42 | JochenX | Auf diesen Beitrag antworten » | ||||
deinem computer ist das bei 9 berechnungen schnurzpiepe vermutlich, aber zumindes handrechner und eigentlich das gebot der elegantheit eines programmes sollten beachten: kollision gefunden => positiv und ENDE |
||||||
| 07.08.2005, 22:15 | AD | Auf diesen Beitrag antworten » | ||||
@jovi Ich sehe ein kleines Problem bei deinem Vorgehen, falls eines der Dreiecke vollständig in dem anderen Dreieck enthalten sein sollte. Aber vielleicht habe ich das beim Überfliegen des Threads auch übersehen...
|
||||||
| 07.08.2005, 22:19 | JochenX | Auf diesen Beitrag antworten » | ||||
sollte kein problem geben arthur ich wüsste auch nicht, wo du da eines sehen willst? liegt ein dreieck komplett im anderen gibt es keine kollision und wir errechnen auch keine mfg jochen |
||||||
| 07.08.2005, 22:22 | AD | Auf diesen Beitrag antworten » | ||||
Naja, ich (und vielleicht andere auch) betrachte als "Dreieck" nicht nur die Umfangslinie, sondern auch das Innere. Und dann bedeutet dieser Fall sehr wohl eine Kollision. Aber das muss uns Simeon erzählen, wie er diesen Fall behandelt sehen will. |
||||||
| 07.08.2005, 22:26 | JochenX | Auf diesen Beitrag antworten » | ||||
doch auch ich wurde belehrt:
und dann wirds klar, dass das nicht unter kollision fällt ich hatte auch einen anderen ansatz |
||||||
| 07.08.2005, 22:34 | AD | Auf diesen Beitrag antworten » | ||||
Wie gesagt, hatte den Thread nur überflogen. 
|
||||||
| 07.08.2005, 23:10 | Ben Sisko | Auf diesen Beitrag antworten » | ||||
Vielleicht kannst du mit ein oder zwei Sätzen noch erklären, worum es in deinem Programm geht, Simeon? |
||||||
| 08.08.2005, 00:09 | Simeon | Auf diesen Beitrag antworten » | ||||
Hey Leute, ich hab da nochmal ne Frage, wenn man meine Formeln daoben mal genauer beguckt fällt auf das P1P2.x nicht 0 sein darf. Was mach ich denn wenn es eine Kollision gibt die so aussieht "+" also wien Plus, dann ist bei dem senkrechten ja P1P2.x 0 obwohl es ne Kollision gibt. Wie kann ich denn das Problem umgehen? @Ben Sagte ich doch schon, es soll Kollisionen erkennen. 
|
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
