Minkowskidifferenz: Liegt eine Punktmenge in einer Halbkugel durch den Nullpunkt?

12/11/2008 - 07:23 von qysocibixaminuxy | Report spam
Hallo,
ich arbeite an einer Kollisionserkennung.
Ein Test, ob 2 konvexe Polyeder "kollidieren", funktioniert wie folgt
1. Bilde die Minkowskidifferenz der Punkte der beiden Polyeder
2. Schaue, ob diese Punkte derart im Raum 3D liegen, dass es eine
Ebene durch den
Nullpunkt gibt derart, dass alle Punkte auf einer Seite dieser
Ebene liegen.

Es hat sich unvermutet herausgestellt, dass der Test, ob alle Punkte
in einer Halbebene liegen,
gar nicht trivial ist. Irgendwelche iterativen Suchalgorithmen nach
einer Ebene sind
unschön, unsauber und zuverlàssig.

Ist jemand schonmal auf diese Fragestellung gestoßen?
Gruß
ERik
 

Lesen sie die antworten

#1 Markus Sigg
12/11/2008 - 08:25 | Warnen spam
wrote:
Hallo,
ich arbeite an einer Kollisionserkennung.
Ein Test, ob 2 konvexe Polyeder "kollidieren", funktioniert wie folgt
1. Bilde die Minkowskidifferenz der Punkte der beiden Polyeder
2. Schaue, ob diese Punkte derart im Raum 3D liegen, dass es eine
Ebene durch den
Nullpunkt gibt derart, dass alle Punkte auf einer Seite dieser
Ebene liegen.

Es hat sich unvermutet herausgestellt, dass der Test, ob alle Punkte
in einer Halbebene liegen,
gar nicht trivial ist. Irgendwelche iterativen Suchalgorithmen nach
einer Ebene sind
unschön, unsauber und zuverlàssig.

Ist jemand schonmal auf diese Fragestellung gestoßen?
Gruß
ERik



Du könntest nach Algorithmen schauen, die den Hüllkegel
(mit Spitze in 0) der Punkte bestimmen. Dann guckst Du
Dir seinen Öffnungswinkel an.

Stichworte: Hüllkegel, Kegelhülle, enclosing cone

Gruß,
Markus

Ähnliche fragen