 |
 |
 |
 |
 |
 |
Startseite » Forum » Wann liegt der Punkt auf der Geradenschar
Wann liegt der Punkt auf der Geradenschar
Schüler
Tags: Geometrie, Geradenschar, informatik
 
|
  |
|---|
|
Ich schreibe momentan eine 2D-Kollisions-Engine in C#. Alle Körper die Kollidieren sind Polygone (Eine Liste von Punkten). Nun will ich feststellen wann ein Polygon mit dem anderen kollidiert. Um es einfacher zu machen nehme ich an, dass eines der beiden sich nicht bewegt (beim Abprallen usw. rechne ich dessen Geschwindigkeit natürlich trotzdem mit ein). Um nun eine Kollission zwischen zwei Polygonen zu erkennen habe ich: Punkte des Objekts A vor der Bewegung Punkte des Objekts A nach der Bewegung (vor Bewegung Geschwindigkeit) Punkte des Objekts Jetzt gehe ich alle Punkte des Polygons A durch, da ich immer zwei Punkte habe (aktueller Zustand und nach draufrechnen der Geschwindigkeit) kann ich aus diesen beiden Punkten eine Strecke bilden. Dann gehe ich für jede dieser Strecken alle Punkte des Polygons durch und bilde eine Strecke mit dem nächsten Punkt des Polygons B. Ziel ist es zu prüfen wann ein bewegter Eckpunkt von A mit einer unbewegten Kante (Strecke zwischen zwei Eckpunkten) von kollidiert. Das funktioniert schon wunderbar. Ich habe zwei Strecken, also habe ich auch die beiden Geraden dazu. Ich berechne den Schnittpunkt der Geraden und prüfe ob er noch auf den beiden Strecken oder auserhalb liegt. Jetzt das eigentliche Problem: Ich muss jetzt auch noch prüfen ob (und wann) eine bewegten Kante von A auf eine unbewegte Ecke von trifft. Da das Polygon auch rotieren kann verschiebt sich die Kante mit der Zeit nicht nur nach oben oder unten, sondern die Steigung der Strecke ändert sich auch. Ich habe also eine Geradenschar (eigentlich sogar Streckenschar). Ich muss jetzt: 1. Die Formel für die Streckenschar herausfinden (aus zwei bewegten Punkten) 2. Herausfinden für welches kleinste (Zeit zwischen 0 und der Punkt auf einer Strecke der Schar liegt. Weis leider nicht wie ich das machen soll, weis auch nicht ob das überhaupt möglich ist.  Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Ganz verstehe ich deine Frage nicht, denn es ist doch völlig egal wie verschoben oder verdreht dein Polygon A ist. Deine Bewegung erfolgt doch in kleinen, aber eben doch diskreten Schritten und so prüfts du eben vor jedem Schritt, ob die Polygone sich danach überlappen würden. In der Regel wirst du doch so kleine kleine Bewegungsschritte nehmen, sodass es nicht nötig ist, genau zu ermitteln, welcher Punkt von A genau wo auf welche Kante von trifft oder welche Kante von A wo mit welchem Eckpunkt von kollidiert. Es reicht doch zu wissen, dass bei/nach dem nächsten Zeitschritt eine Kollision erfolgen würde. Du hast also zwei Polygone durch eine orientierte Eckenliste gegeben und musst prüfen, ob es mind. 1 Eckpunkt von A gibt, der innerhalb von liegt ODER ob es mind. 1 Eckpunkt von gibt, der innerhalb von A liegt. Die Überprüfung, ob zwei Polygonkanten einander schneiden, indem man jede von A gegen jede von prüft, ist insofern nicht ganz ausreichend, als sie versagt, wenn etwa ein Polygon zur Gänze innerhalb des anderen liegt. Aber in jedem Fall hast du ein rein statisches planares Problem vorliegen und welches Polygon du dir jetzt wie bewegt vorstellst ist für die Lösung der Aufgabe ja völlig unerheblich - du hast zwei Punktlisten und überprüfst. Die Aufgabe, festzustellen, ob ein Punkt innerhalb eines Polygons liegt, ist nicht so trivial, wie es auf den ersten Blick den Anschein hat. Zum Glück haben sich aber auch schon viele schlaue Köpfe damit auseinandergesetzt, sodass dafür dem Programmierer eine Reihe recht ausgefeilter und vor allem recht effizienter Algorithmen zur Verfügung stehen. Es besteht also keine Notwendigkeit, das Rad neu zu erfinden. Der Jordan-Test mit Bestimmung der Windungszahl ist hier ein Standard-Verfahren, aber es gibt da auch noch eine Reihe von laufzeitoptimierten Verfeinerungen zu entdecken. www.google.com/search?q=punkt+innerhalb+polygon Auch da Thema collision detection ist sicher schon zur Genüge erforscht, sodass hier auch recht effiziente Algorithmen mehr oder weniger fertig in der Literatur zu finden sind. www.google.com/search?q=collision+detection+polygon |
 |
|
Das ist leider nicht die Antwort auf meine Frage, es sind zwei völlig unterschiedliche Dinge ob ich feststelle wann und wo ein Polygon auf ein anderes Polygon treffen wird oder ob sie sich schon längst irgendwo überschneiden. Ich habe schon ein Programm geschrieben welche die von dir vorgeschlagene Methode verwendet. Diese Methode hat jedoch einige Macken: - Ich weis nicht wo genau das Polygon auftrifft, was ich aber wissen muss damit ich es auch wieder heraus bewegen kann (ohne drüber zu iterieren bis es nicht mehr kollidiert) - Ich weis nicht in welchem Winkel es auftrifft und an welcher Stelle. Diese Information benötige ich möglicherwiese an anderen Stellen im Code. - Es kann sich einfach durch ein anderes durch bewegen, bei sehr kleinen und schnellen Objekten wäre das dann mehr die Regel als die Ausnahme, also völlig unbrauchbar. Werde mir aber mal ein par der Suchergebnisse (aus deinem Link) ansehen, vielleicht finde ich ja etwas geignetes und muss nicht erst lange auf dem Holzweg herumirren^^. Würde trotzdem gerne wissen ob meine Methode funktionieren würde, und wann ja wie. |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1251192
1250930