Algorithmus gesucht, um Schnittpunkt(e) zwischen einem Kreis u. einer Geraden zu bestimmen. |
| 12.03.2004, 12:42 | JWone | Auf diesen Beitrag antworten » | ||||||
| Algorithmus gesucht, um Schnittpunkt(e) zwischen einem Kreis u. einer Geraden zu bestimmen. Nachdem mir unter Geometrie niemand weiterhelfen konnte versuche ich es hier nochmals.. Ich hoffe Ihr könnt mir weiterhelfen 
! Ich suche nach einem möglichst allgemeingültigen (damit meine ich möglichst wenige Fallunterscheidungen) und sehr Pärformanten Algorithmus um die/den Schnittpunkt(e) zwischen einem Kreis gegeben durch (x-x0)^2 + (y-y0)^2 = r^2 M=(x0,y0) und einer Geraden y = mx + c zu bestimmen. Der Algorithmus sollte möglichst wenige Multiplikationen enthalten, da ich diesen auf einem System mit nur sehr geringer Rechenleistung in Echtzeit lösen möchte. Die Gerade kann auch gerne durch Ortsvektoren beschrieben werden. Ich suche nach einem anderen Lösungsweg, als dem gleichsetzen beider Gleichungen und lösen des quadratischen Gleichungssystems. Gibt es eine Lösung über eine Matrizenmultiplikation oder ähnlich trickreiches? Danke für eure Hilfe & Gruss Jan |
||||||||
| 12.03.2004, 13:25 | Ben Sisko | Auf diesen Beitrag antworten » | ||||||
| RE: Algorithmus gesucht um Schnittpunkt(e) wischen einem Kreis u. einer Geraden zu Bestimmen. Ich glaube nicht unbedingt, dass jemand dir helfen kann, nur weil du´s jetzt in nem anderen Unterforum postest. 
Ich wüsste keinen anderen Ansatz als das Gleichsetzen und dann Lösen. Wie kommst du auf die Matrixmultiplikation, ist das nur ne spontane Idee? Eine Matrix ist von ihrer Natur her etwas Lineares, steht für lineare Gleichungssysteme und lineare Abbildungen. Gruß vom Ben |
||||||||
| 12.03.2004, 13:59 | jama | Auf diesen Beitrag antworten » | ||||||
Matrizenrechnung ist doch die Wunderwaffe für alles bei der Programmierung :P
Wenn es immer Schnittpunkte gibt, kannst Du auch dementsprechend rechnen (lassen) und die anderen möglichen Fälle nicht beachten. Was anderes außer das Einsetzen der Geradengleichung in die Kreisgleichung fällt mir nicht ein: http://www.matheboard.de/thread.php?goto...st&threadid=580 Was für einem Spiel soll das denn überhaupt zugute kommmen? Irgendwie kommen in letzter Zeit öfters solche Programmiererfragen ... Gruß, Jama |
||||||||
| 12.03.2004, 14:13 | JWone | Auf diesen Beitrag antworten » | ||||||
| RE: Algorithmus gesucht um Schnittpunkt(e) wischen einem Kreis u. einer Geraden zu Bestimmen. Hallo Ben, Sorry für das 2te Posten, aber immerhin hast Du jetzt darauf reagiert ;o). Also wieso komme ich auf Matrizenmultiplikation oder änliches (warscheinlich habe ich mich dabei nicht ganz sauber ausgedückt). Ich habe beim suchen nach einer Lösung meines Problems Dr. Google gefragt und bin unter anderem auf ein änliches Problem gestoßen das in Vektorieller Form gelöst wurde. Dies habe ich aber nicht verstanden. Leider habe ich den Linke gerade nicht parat, falls ich Ihn nohmals finde werde ich Ihn hier posten. Ich glaube die Lösung des Problems basiert eher auf einer Paramteterdarstellung des Kreises und einer Darstellung der Geraden durch Ortsvektoren. Im Grunde steckt auch bei diesem Verfahren ein Lösen der Gleichungen dahinter, allerdings reduziert sich durch die Schreibweise die Anzahl der nötigen Rechenschritte enorm. Vielleicht Hast Du jetzt doch noch eine Idee, oder kennst irgend eine gute Literatur Danke & Gruss Jan ____________________________________________________________ Hallo Jama, Du hast Recht ;o), ich benötige diesen Algorithmus für die Physik-Engine eines Pinballspiels. Dabei muss ich den Kollisionspunkt zwischen einer sich bewegenden Kugel und einer Rundung berechnen. Die Bewegung der Kugel wird linear approximiert, das heißt ich habe eine Alte- und eine Neue-Kugel-Position vorliegen und möchte den exakten Kollisionspunkt der Kugel mit der Rundung (Kreis) bestimmen. Es gibt daher auch drei unterschiedliche Lösungen: Es gibt keinen, einen oder zwei Schnittpunkte. Hier muss ich Jedenfalls unterscheiden. Ich hoffe dennoch auf einen schnelleren Algorithmus als auf das lösen der Quadratischengleichung mit der PQ-Formel oder ähnlichem.. Gruss Jan //EDIT by sommer87: Bitte Doppelposts vermeiden. EDIT nutzen!! |
||||||||
| 12.03.2004, 17:26 | Ben Sisko | Auf diesen Beitrag antworten » | ||||||
Also ich setz mal deinen Parameteransatz ganz naiv um: Hm, 2 Gleichungen, 2 Variablen(Parameter), also hat man höchstens eine Lösung. Oder unendlich viele. Bin verwirrt. Könnte es was damit zu tun haben, dass du den Kreis oBdA in den Koordinatenursprung gelegt hast? Aber das könnte man ja so modellieren und müsste dann nur die Vektoren bei der Darstellung der Geraden relativ dazu entsprechend wählen. Das ändert ja die Struktur der Gleichungen nicht. Ich seh im Moment meinen Fehler nicht. Sonst irgendjemand?? Gruß vom Ben |
||||||||
| 12.03.2004, 17:46 | Drödel | Auf diesen Beitrag antworten » | ||||||
Ich denke IWone meint mit M(x0,y0) nicht den Koordinatenursprung, sondern vielmehr Wobei ein Pinballspiel mit "anderer Perspektive" wäre auch mal ganz nett ;-) Kugel ist fest, nur der Rest bewegt sich. |
||||||||
| Anzeige | ||||||||
|
|
||||||||
| 12.03.2004, 18:01 | Ben Sisko | Auf diesen Beitrag antworten » | ||||||
Damit meinte ich die Parameterdarstellung vom Kreis. Die ist für den Einheitskreis, also Radius 1 und Mittelpunkt 0. |
||||||||
| 12.03.2004, 18:43 | JWone | Auf diesen Beitrag antworten » | ||||||
Hallo, habe nochmals über das Problem nachgedacht, und habe mit der Paramterdarstellung noch keine Lösung gefunden. Habe aber eine neue Idee. Wie sieht es damit aus die Gesamte Funktion Lapace zu transformieren, und die DGL darüber zu lösen? Vielleicht gibts für mich bei der Berrechnung noch etwas Nachhilfe :P Ich glaube das müsste funktionieren, aber die Durchführung scheitert bei mir. Danke & Gruss Jan |
||||||||
| 12.03.2004, 18:47 | Ben Sisko | Auf diesen Beitrag antworten » | ||||||
Also ich muss zugeben, dass ich mich mit der laplace-Transformation nicht so auskenne, aber wo siehst du da eine DGL? Wie genau hast du dir das vorgestellt? |
||||||||
| 12.03.2004, 18:58 | JWone | Auf diesen Beitrag antworten » | ||||||
Eine Quadratische-Gleichung ist ein Differential-Gleichung 2ter Ordnung, oder? Also sollte ich diese auch über Laplace lösen können, glaube ich zumindest.. Habe so etwas seit meinem Studium auch nicht mehr gemacht.. 
Weiss hier irgendwer weiter? Jan |
||||||||
| 12.03.2004, 18:59 | Poff | Auf diesen Beitrag antworten » | ||||||
Ich kann dir zwar nichts anbieten, sehe aber recht klar, dass NUMERISCHE Methoden zur Berechnung der Schnittstelle hier das Richtige sein dürften. Ich denke dass dort auch eine Lösung zu finden sein dürfte, die deinen Vorstrellungen genügen könnte. ... |
||||||||
| 12.03.2004, 19:01 | BlackJack | Auf diesen Beitrag antworten » | ||||||
RE: Algorithmus gesucht um Schnittpunkt(e) wischen einem Kreis u. einer Geraden zu Bestimmen.
nein, das glaube ich nicht, da sinus-berechnungen so ungefähr das langsamste sind, was ein PC so draufhat. ein sinus kann mal schnell 100 takte dauern, während multiplikationen höchsten ein paar (~3) takte braucht, und selbst wurzelziehen (was du ja nicht so oft wirst machen müssen) braucht weniger takte (~70). (die takte beziehen sich auf alte penitums, bei neueren processoren und neueren processorarchitekturen (pipelining etc) werden es wahrscheinlich weniger takte sein.) aber gehe ich recht in der annahme, das die gerade eine bande und der kreis die kugel ist? also dann würde ich es so machen, erstmal den abstand des mittelpunktes des kreises von der gerade zu bestimmen; wenn er kleiner ist als der radius, ist die kugel sozusagen zu weit gerollt (in die wand hinein). dann könntest du noch bestimmen, wie weit die kugel in die wand hineingerollt ist, und daraus und aus der letzten position der kugel genau die position bestimmen, bei der die kugel die wand genau berührt. |
||||||||
| 12.03.2004, 20:08 | JWone | Auf diesen Beitrag antworten » | ||||||
Das denke ich auch. Leider habe ich mit der Numerik so meine Schwierigkeiten. Wie kann ich dort vorgehen? Ich dachte daran die Funktion wirklich erst mal Laplace zu transformieren, ich weiß das es irgend eine Möglichkeit gibt um DGLs mit Hilfe eines Laplace-Integrals zu lösen. Das Integral könnte ich über eine Reihe nähern.. ------------------------------
Ich arbeite bei trigonometrische Funktionen sowieso mit einem LookUp-Table. Sinus u. Kosinus machen mir bisher keine Sorgen.
Mein Problem hat eine Andere Ursache, die "Collision Detection" und "Collision Response" an einer Wand habe ich bereist ganz gut im Griff ;0) Im Moment arbeite ich an der "Collision Detection" der Kugel an einem Kreis. Das heisst, das Bestimmen eines Kollisionspunktes einer sich "bewegenden" Kugel und dem Kreis. Die Position der Kugel wird in meinem Bewegungsmodell periodisch bestimmt. Es liegen mir immer diskrete Kugelpositionen (neueKugelKoordinate u. altKugelKoordinate) vor. Für mein Modell muss ich im Fall einer Kollision zwischen einem Kreis (oder einfach einer Rundung) den exakten Kollisionspunkt bestimmen. Die Bewegung der Kugel in einem "Bewegungsintervall" wird dabei von mir linear approximiert --> die Gerade. Der Kreis ist das Hinderniss. Soviel zum Kontext der Problemstellung 
Gruss & Danke für die bisherigen Beiträge Jan |
||||||||
| 12.03.2004, 20:25 | Ben Sisko | Auf diesen Beitrag antworten » | ||||||
In einer DGL 2. Ordnung kommt die 2. Ableitung vor, nicht notwendigerweise ein Quadrat. Entweder verwechselst du hier was oder hast mir gänzlich unbekannte Methoden, quadratische Gleichungen und DGLen in Beziehung zu setzen. |
||||||||
| 12.03.2004, 21:07 | JWone | Auf diesen Beitrag antworten » | ||||||
Ist doch aber eine Differentialgleichung, oder?
Mit (x-x0)^2+(y-y0)^2=r^2 und y=mx+c folgt (x-x0)^2+(mx+c-y0)^2-r^2 = 0 das heisst X^2 steckt drin und in mx steckt auch irgendwie die Ableitung drin. Ist nicht unbedingt eine DGL 2ter Ordnung, aber laut der Definition soweit ich das verstehe eine DGL. Gruss, Jan |
||||||||
| 13.03.2004, 02:26 | Ben Sisko | Auf diesen Beitrag antworten » | ||||||
Naja, m ist halt die Steigung der Geraden, aber da du die ja kennen solltest, bringt dich ein DGLsansatz nicht weiter. Du kennst ja schon die Ableitung (m) und die Funktion der Gerade. m hat nix zu tun mit der Ableitung der quadratischen Funktion. Eine DGL setzt eine Ableitung mit der Funktion in Beziehung und sucht dann Funktionen, die diese erfüllen. In deinem Fall musst du einfach eine quadratische Gleichung lösen, das hat soweit erstmal nix mit DGLen zu tun. Und wenn dann wäre es eh eine erster Ordnung
Gruß vom Ben |
||||||||
| 14.03.2004, 18:05 | BlackJack | Auf diesen Beitrag antworten » | ||||||
@JWone: zu deinem problem: sehe ich das richtig, dass du 2 kreise hast (die kugel und die kreisförmige bande), von denen du jeweils mittelpunkt und radius kennst und daras den berührpunkt errechnen willst? wenn ja, geht das doch so recht einfach: du errechnest, welche steigung eine gerade hätte, die zwischen den mittelpunkten der kreise gezogen würde. aus dieser steigun berechnest du über m=tan(a) den winkel, und errechnest aus diesem und einen radius, welche x/y-werte du auf den mittelpunkt addieren musst, um zu dem berührpunkt zu gelangen. ist nciht so einfach zu beschreiben, aber die berechnung sollte nicht allzu schwierig sein. wenn ich dein problem richtig verstanden habe, kann ich ja mal pascal-code liefern, der den berührpunkt zweier kreise berechnet. (hab sowas ähnliches schonmal gemacht). |
||||||||
| 14.03.2004, 21:06 | JWone | Auf diesen Beitrag antworten » | ||||||
@BlackJack: Nein, das komplette Programmier-Problem ist etwas komplexer. Zu komplex als das es Sinn machen würde es komplett hier darzustellen. Falls es Dich interessiert, schicke ich Dir gerne mehr Infos darüber. Allerdings sprengen diese Erklärungen den Rahmen dieses Forums, glaube ich zumindest ;o) Mir geht es im Grunde nur darum eine Funktion zu schreiben, die (wieso auch immer
) das Folgende bewirkt.Parameter sind der Kreismittelpunkt, der KreisRadius, die Steigung der Geraden m, und der Y_Achsenabschnitt c dieser Geraden. Der Rückgabewert dieser Funktion soll ein Array mit den Schnittpunkten zwischen Kreis und der Geraden sein. Vielleicht hilft ein kleines Stückchen Pseudo-Code: public Point[] getCircleIntersections(Point Kreismittelpunkt, long KreisRadius, long fm, long fc) { Point intersection[]; //Referenz auf ein Poin-Array // Hier kommt die Berechnung... ... return intersection; //Falls es keinen Schnittpunkt gibt, return null } Ich habe das ganze bereits mit einer aufgelösten quadratischen Gleichung implementiert. Die Berrechnung ist aber leider zu langsam für mein System, daher versuche ich immer noch einen "schnelleren" Lösungsweg zu finden. Gruss Jan |
||||||||
| 26.04.2004, 17:58 | @home | Auf diesen Beitrag antworten » | ||||||
| Kreis Linie Schnittberechnung Wie währe es mit Vektorrechnung? Ist doch eigentlich gar nicht so schwer. Orthogonalen Vektor der Geraden mit Hesse'scher Normalform berechnen, Normieren. Vektor Pm - P2 (von der Geraden <Ortsvektor>) darauf abbilden (Skalarprodukt) und somit Orthogonale bestimmen, die durch den Kreismittelpunkt Pm geht (Skalarprodukt der Orthogonalen == 0). Danach mit Phytagoras Den O Vektor mit dem Radius subtrahieren ( natürlich |V|) und ... fertig. Die Schnittpunkte sind jetzt Vektor +- Phytagoras. Ist übrigens in vielen Büchern der GDV nachzulesen ... |
||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
