Kurvenabschnitt und Polygone Kollision

26.08.2021, 10:52	Papuga	Auf diesen Beitrag antworten »
Kurvenabschnitt und Polygone Kollision Guten Tag, Meine Frage stammt wahrscheinlich am meisten aus der Kollisionserkennung oder Differentialgeometrie und lässt sich an folgendem Bild gut veranschaulichen: [attach]53535[/attach] Gegen ist ein Kurvenabschnitt $\begin{eqnarray} r(t) \in \mathbb{R^2} \end{eqnarray}$ der nach $\begin{eqnarray} t \end{eqnarray}$ parametrisiert ist. Dabei befindet sich $\begin{eqnarray} t \in [0,T] \end{eqnarray}$ . Zudem sind konvexe Gebiete im $\begin{eqnarray} \mathbb{R^2} \end{eqnarray}$ gegeben, die sich über Ungleichungen der Form $\begin{eqnarray} Ax\leq b \end{eqnarray}$ (mit A=Matrix und b = Vektor) darstellen lassen. Die Frage lautet nun: Wie kann Ich feststellen, dass der Kurvenabschnitt außerhalb der konvexen Hindernisse bleibt? Ob ein Punkt außerhalb der Gebiete ist, lässt sich ja ziemlich einfach feststellen. Man überprüft einfach die Ungleichungen. Leider kann man das nicht für alle Punkte machen, da es unendlich viele sind. Ist das Problem überhaupt lösbar? z.B über Vereinfachungen und weiteren Annahmen über die Kurve und konvexen Gebiete? Mfg Papuga
26.08.2021, 17:09	HAL 9000	Auf diesen Beitrag antworten »
Für allgemeine Kurven sicher schwierig. Was du tun könntest, ist folgendes: Finde ein "einhüllendes Polygon" für deine Kurve, d.h., eins, wo deine Kurve komplett drin liegt. Und falls dieses Polygonfläche disjunkt zu deinen anderen Polygonflächen ist, bist du fertig. Muss natürlich nicht ein einziges Polygon sein, kann auch die Vereinigung mehrerer Polygone sein - am besten konvexer Polygone. Das reduziert das ganze auf folgende Teilprobleme: 1) Feststellen, ob zwei konvexe Polygonflächen disjunkt sind (so einen Algorithmus hast du ja womöglich schon) 2) Finden einer solchen Einhüllung, die "schmal genug" ist, dass sie die gegebenen konvexen Gebiete nicht schneidet. Ok, Teilproblem 2) ist sicher nicht trivial, aber du willst ja auch noch was zu tun haben.
11.09.2021, 13:31	Papuga	Auf diesen Beitrag antworten »
Hey HAL, danke für die Tipps. Vor allem das zweite Teilproblem könnte für eine sehr viel effizientere Kollisionsdetektion sorgen. Ich werde mal versuchen das Problem für bestimmte Vereinfachungen zu lösen. Danke.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »