Springen naar inhoud

punt in veelhoek


  • Log in om te kunnen reageren

#1

leopardinho

    leopardinho


  • 0 - 25 berichten
  • 3 berichten
  • Gebruiker

Geplaatst op 17 mei 2004 - 11:09

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.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2


  • Gast

Geplaatst op 17 mei 2004 - 14:32

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

#3


  • Gast

Geplaatst op 17 mei 2004 - 14:48

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.

#4

Elmo

    Elmo


  • >1k berichten
  • 3437 berichten
  • VIP

Geplaatst op 17 mei 2004 - 14:55

Zoiets?:

Beschouw de vierhoek ABCD in het positieve quadrant alsvolgt:

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.

#5


  • Gast

Geplaatst op 17 mei 2004 - 15:15

Zoiets?:

Beschouw de vierhoek ABCD  in het positieve quadrant alsvolgt:

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...larPolygon.html

#6

Elmo

    Elmo


  • >1k berichten
  • 3437 berichten
  • VIP

Geplaatst op 17 mei 2004 - 15:24

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:





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures