Detecteer punt in een vorm

[Roberto Molvado]

Een geometrisch probleempje.
 
In videogame-ontwikkeling bestaat iets dat een "EventOnLocation" wordt genoemd, oftewel, iets dat getriggered wordt zodra een object een locatie binnenkomt. Ik zit nu al een tijdje na te denken over een algoritme die zoiets kan doen.
Ik ben op zoek naar de oplossing voor het volgende:
 
We hebben een "mesh", een 3D vorm, bestaande uit [ itex ] n [ /itex ] punten. Deze punten [ itex ] P_1, P_2, ... , P_n [ /itex ] geven als het ware de buitenste laag aan van dit object. De vraag is nu of een gegeven punt [ itex ] Q [ /itex ] zich wel of niet binnen deze "mesh" bevindt.
 
Onderstaande afbeelding laat een voorbeeld zien. Het paarse punt is [ itex ] Q [ /itex ]
 
Alvast bedankt voor elke suggestie!

[317070]

Het hangt ook wat af van de eigenschappen van je vorm (convex? zelf-snijdend? Genus?) om efficiëntere algoritmes te gebruiken.
 
In het algemene geval kun je best alle facetten (faces) van je figuur berekenen, en tellen hoeveel van die vlakken een willekeurige lijn van je punt naar oneindig snijdt. Als dat een oneven aantal is, zit je punt in de figuur, anders ligt ze erbuiten.
 
Let, er zijn wel veel edge-cases die moeten opgelost worden (wat als de lijn op een vertex snijdt? Of op een edge?)
 
Problemen als deze kun je vaak onverwacht efficiënt oplossen, maar de algoritmes zelf zijn niet altijd even eenvoudig. Dit is een standaardboek over dit soort problemen: http://www.amazon.com/Computational-Geometry-Applications-Mark-Berg/dp/3540779736

[Roberto Molvado]

Dank je voor je reactie.
 
In principe zou het gaan om elke vorm. Dus ook om een donut-vorm of een bol met een grote deuk erin. (Dus niet convex?)
 
Ik moest die methode die je voorstelt wel even vijf keer lezen voor ik het begreep en het lijkt interessant! Klopt het dat één zo een "scan" genoeg is voor elke situatie, mits het gaat om een gesloten vorm?

[317070]

Ik moest die methode die je voorstelt wel even vijf keer lezen voor ik het begreep en het lijkt interessant! Klopt het dat één zo een "scan" genoeg is voor elke situatie, mits het gaat om een gesloten vorm?

Ja, 1 scan over al je faces is voldoende. Meer zelfs, je vorm mag uit verschillende delen bestaan en ook oneindig bevatten! Als ik me goed herinner moest je vorm gesloten en orienteerbaar zijn.
 
Het kan waarschijnlijk efficiënter door je mesh als een bepaalde datastructuur op te slaan, waardoor je efficiënt alle snijpunten tussen je mesh en een lijn vindt. Moest je je mesh opslaan in een BVH-tree ( https://en.wikipedia.org/wiki/Bounding_volume_hierarchy) hoef je zelfs niet alle faces af te lopen.