Webdesign, Tutorials und mehr - Webmasterpro.de

Kollision zwischen Kreis und Geraden

Sebastian Bechtel, am Mittwoch den 06.10.2010 um 21:09:22

Hi,

ich muss ein Programm schreiben, dass die Bewegung von Kreisen innerhalb eines Polygons simuliert. Dazu habe ich auch schon genau Vorstellungen, allerdings hänge ich an der Kollision zwischen Kreisen und Geraden.

Alle Ansätze die ich bisher gefunden habe basieren auf Vektoren, da ich die in der Schule noch nicht hatte, will ich es auch nicht so lösen.

Mein Ansatz bisher:

Wenn ein Kreis eine Gerade berührt, dann würde die Normale in diesem Punkt durch den Mittelpunkt des Kreises gehen. Um eine entsprechende Funktion dafür zu finden, müsste man die Geradengleichung verwenden und als Steigung -1/m (m ist die Steigung der Geraden) und den Mittelpunkt einsetzen.

Dann könnte man die erhaltene Funktion mit der Geradenfunktion gleichsetzen und einen Schnittpunkt ausrechnen. Wenn sqrt( delta_x^2 + delta_y^2) = r, dann ist es eine Kollision und zwar im Schnittpunkt. Allerdings finde ich das ziemlich aufwändig und ungünstig als Software.

Jemand ne bessere Idee?

Gruß Sebastian

edit

Die Gerade wird übrigens nur durch den Anfangs und Endpunkt beschrieben und der Kreis durch seinen Mittelpunkt und seinen Radius.

edit2

Diesen Netten kleinen Ausdruck habe ich für die x Koordinate des Ausdrucke

Jetzt muss man erst prüfen ob x in Delta x liegt. Ist dies der Fall, muss man das Ergebnis in die Funktion m(x) einsetzen und dann mit dem Pythagoras die Strecke zwischen S und M berechnen und schauen, ob es r ist.

Also im Prinzip für den PC ganz simpel, aber trotzdem total ekelhaft. Für eine etwas kürzere Lösung wäre ich trotzdem glücklich.

Fabian Ziegler, am Donnerstag den 07.10.2010 um 11:12:33

Da kann Dir bestimmt Firebird helfen.

http://www.webmasterpro.de/user/Firebird/

Firebird , am Donnerstag den 07.10.2010 um 11:41:00

Mit elementarer Mathematik wirst Du nicht zu einem (wesentlich) einfacherern Ausdruck kommen. Wenn Du den erst einmal in den PC eingetippt hast, wird das Ergebnis dafür schnell berechnet sein.. die Normale brauchst Du ohnehin spätestens bei der Winkelberechnung für die weitere Bewegung des Kreises. (Eine Erklärung, die Vektorrechnung benutzt, habe ich auf die Schnelle z.B. hier gefunden)

Eine einfachere, aber dafür ungenauere Methode mit längerer Ausführungszeit: Male das Polygon (Mit aktiviertem Antialiasing oder einer Linienstärke von mindestens 2px) und dann male den Kreis punktweise dazu, prüfe aber vor jedem Punkt, ob an dieser Stelle bereits etwas gemalt wurde.

Dir könnte auch noch helfen, dass es in vielen Programmiersprachen Polygon-Klassen gibt, die fertige Methoden für das „Point in polygon“-Problem mitbringen. Von dort solltest Du zumindest Code kopieren können.

Schau ansonsten mal, ob Du im Netz Lösungen für die 1. Aufgabe der 2. Runde des 24. BWINF findest. Dort gab es eine Aufgabe, bei der es darum ging, das Sichtfeld eines Nachtwächters in einem polygonförmigen Museum zu bestimmen. Die Aufgabenstellung ist ja sehr ähnlich.

Sebastian Bechtel, am Donnerstag den 07.10.2010 um 13:02:26

Habe gerade eine Bibliothek gefunden, die mir das Leben versüßt ;-)

http://trac.gispython.org/lab/wiki/Shapely

Damit Kann ich unter anderem Polygone und Punkte abbilden. Kreise gibt es zwar nicht, aber brauch man ja nicht.

Es gibt eine Methode für die kürzeste Distand. Ist diese r, so gibt es eine Kollision mit dem Polygon. Bei Kreisen wäre es entsprechend 2r und man würde halt mit 2 Punkten arbeiten.

Ich glaube man kann damit sogar Vektoren benutzen, habe es aber eben erst gefunden und bin noch am lesen. Dann wäre die Aufgabe natürlich ein Klacks.