WisFaq!

Ligt het punt in de veelhoek?

Hallo,

ik ben op zoek naar een algoritme om te bepalen of een punt al dan niet in een bepaalde veelhoek ligt. het is de bedoeling dat dit algoritme geďmplementeerd wordt in c++. maar als u het gewoon in woorden kan uitleggen dan is dat ook goed.
ik heb al gezocht op internet maar zonder resultaat.

alvast bedankt.

Dirk
17-5-2004

Antwoord

Voorbeeld: driehoek met hoekpunten A(0,0), B(2,0) en C(1,3).
Deze wordt begrensd door de rechten y=0 (door A en B), y=3x (door A en C), y+3x=6 (door B en C).

Het gaat er nu om dat een punt binnen de driehoek ligt als het drie keer aan de goede kant van een zijde ligt.
Herleid de vergelijking van de zijde op 0: Men krijgt dan sx+ty-u=0 voor zekere s,t,u. De punten aan de ene kant van de lijn voldoen aan sx+ty-u0, die aan de andere kant aan sx+ty-u0.
In ons voorbeeld: de punten binnen de driehoek liggen

1. aan dezelfde kant van y=0 als C, dus y0;
2. aan dezelfde kant van y-3x=0 als B, dus y-3x0;
3. aan dezefde kant van y+3x-6=0 als A, dus y+3x-60.

Een veelhoek is convex als er n verbindingslijnen van 2 hoekpunten bestaan (de zijden van de veelhoek) zó dat de andere n-2 hoekpunten telkens aan één kant van de verbindingslijn liggen.

Het algorithme bestaat dus, in het geval van een convexe veelhoek met n hoekpunten, uit het opstellen van de n ongelijkheden waaraan precies de punten binnen de veelhoek voldoen.

Is de veelhoek niet convex, dan wordt het ingewikkelder. Men kan dan het beste de veelhoek opdelen in convexe veelhoeken.

Maar ... zie ook Punt binnen of buiten een veelhoek

hr
17-5-2004