|
|
Hallo!
Ich habe folgende Aufgabenstellung bekommen, hab aber diesmal keine Ahnung wie ich überhaupt anfangen soll.
Folgendes Problem:
Ich haben ein Set von n Punkten und ein Set von m Dreicke in der Ebene gegeben. Die Dreiecke sind so gegeben das kein Dreieck ein anderes schneidet und kein Dreick liegt in einem anderen Dreieck und es ist auch kein Punkt eines Dreiecks ein Punkt eines anderen Dreiecks. Die Punkte sind so gegeben, dass kein Punkt auf einer Kante oder auch auf einem Eckpunkt des Dreiecks liegt. Die Punkte sind durch ihre Koordinaten gegeben bzw die Dreiecke durch die Koordinaten der Eckpunkte. Aufgabenstellung ist es nun für jeden Punkt aus der Menge n festzustellen ob er sich innerhalb eines Dreiecks befindet und wenn ja in welchem. Es soll ein effizienter Algorithmus gefunden werden. Einziger Anhaltspunkt, es sollte was mit Hilfe der konvexen Hülle realisiert werden, da wir diesen Algorithmus gerade durchgenommen haben!
Hat irgendjemand eine Idee, wie ich hier anfangen könnte?
Mit bestem Dank!
LG Daniel
|
|
