punt in veelhoek

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer
Berichten: 3

punt in veelhoek

Hallo,

ik ben op zoek naar een algoritme om te bepalen of een punt al dan niet in een bepaalde veelhoek ligt. liefst in c++ maar gewoon in woorden is ook goed.

ik heb al gezocht op internet maar zonder resultaat.

alvast bedankt.

Re: punt in veelhoek

leopardinho schreef:Hallo,

ik ben op zoek naar een algoritme om te bepalen of een punt al dan niet in een bepaalde veelhoek ligt. liefst in c++ maar gewoon in woorden is ook goed.

ik heb al gezocht op internet maar zonder resultaat.

alvast bedankt.
bedoel je daarmee: dat je een veelhoek in een assenstelsel tekent en dat de gebruiker bijv. de coordinaten van een punt moet geven, en zo berekent de computer of het punt wel of niet in de veelhoek ligt?

of, stel, je hebt een veelhoek en een functie f, de computer moet dan berekenen of (x,f(x)) in de veelhoek ligt..?

zulke voorbeelden bedoel je

Re: punt in veelhoek

je hebt een (gegeven) veelhoek een een gegeven punt. dan moet dus bepaald worden of dat punt in de veelhoek ligt.

mijn probleem is dat ik dit moet implementeren in c++ maar ik weet niet hoe dit moet.

Gebruikersavatar
Berichten: 3.437

Re: punt in veelhoek

Zoiets?:

Beschouw de vierhoek ABCD in het positieve quadrant alsvolgt:

Code: Selecteer alles

A--B

|  |

C--D
(waarbij de hoeken CAD etc. niet perso 90 graden hoeven te zijn)

Als je punt (x,y) in het vierkant ligt, dan moet dus gelden dat:

1) x moet rechts van de lijn AC liggen (ter hoogte van y).

2) x moet links van de lijn BD liggen (ter hoogte van y).

3) y moet boven de lijn CD liggen (ter plaatse van x).

4) y moet onder de lijn AB liggen (ter plaatse van x).

Dit is eenvoudig te implementeren, daar alle lijnstukken rechte lijnen zijn (parametriseer met AB = s + t*x of zoiets, en netzo voor de andere lijnstukken).

Uitbreiding naar 5 (of meer) hoeken is niet moeilijk, alleen een kwestie van boekhouden. Een algemeen algoritme, wat werkt voor alle veelhoeken, lijkt me lastiger te construeren.

Re: punt in veelhoek

suyver schreef:Zoiets?:

Beschouw de vierhoek ABCD  in het positieve quadrant alsvolgt:

Code: Selecteer alles

A--B

|  |

C--D
(waarbij de hoeken CAD etc. niet perso 90 graden hoeven te zijn)

Als je punt (x,y) in het vierkant ligt, dan moet dus gelden dat:

1) x moet rechts van de lijn AC liggen (ter hoogte van y).

2) x moet links van de lijn BD liggen (ter hoogte van y).

3) y moet boven de lijn CD liggen (ter plaatse van x).

4) y moet onder de lijn AB liggen (ter plaatse van x).

Dit is eenvoudig te implementeren, daar alle lijnstukken rechte lijnen zijn (parametriseer met AB = s + t*x of zoiets, en netzo voor de andere lijnstukken).

Uitbreiding naar 5 (of meer) hoeken is niet moeilijk, alleen een kwestie van boekhouden. Een algemeen algoritme, wat werkt voor alle veelhoeken, lijkt me lastiger te construeren.
ik denk dat hij een algemene algoritme zoekt, als ik aanneem dat het gaat om regelmatige veelhoeken...dus.. omgeschreven door een cirkel.

je kunt de manier waarop men concludeert dat een punt wel of niet in een cirkel als startpunt nemen..

hier staan nog al wat formules bij.

http://www.wisfaq.nl/top.htm?url=http://ma...larPolygon.html

Gebruikersavatar
Berichten: 3.437

Re: punt in veelhoek

Ik heb nergens gezien dat het om een regelmatige veelhoek moest gaan. Voor die speciale klasse van veelhoeken kan je natuurlijk wel heel snel redelijke afschattingen maken door te kijken naar een set concentrische cirkels, waarvan de grootste net alle punten van de veelhoek omvat, en de kleinste net geeneen meer. Maar ja, dan wordt het een soort kansrekening... :shock:

Reageer