[Delphi]Controleren of polygonen overlappen

[douweh]

Ik heb het volgende probleem, ik wil dus een functie bouwen, die twee "array of TPoint" accepteert,
en dan check of ze overlappen..

Ik neem aan dat hier al een oplossing voor is gevonden,
zou iemand mij op weg kunnen heklpen... evt in pseudo code?

[toraq]

Zo moeilijk is dat niet hoor, je hoeft alleen van elk punt van de ene polygoon te kijken of die in de andere ligt.

[douweh]

Ja, zo ver was ik al wel,
maar heb je ook enig idee hoe ik dan van een punt check of het in een polygoon valt?

[douweh]

Is er eccht niemand die mij heier mee kan helpen?

[kvdveer]

polygonen zijn op te splitsen in heel veel driehoeken.

Voor een driehoek moet je dus kunnen bepalen of een punt in die driehoek valt. Dat is niet zo moeilijk. Het splitsen in driehoeken is lastiger.

edit:
je sig werkt trouwens niet

[kvdveer]

splitsen in driehoeken doe je als volgt:

Een makkelijke methode is

neem een punt (2), neem een punt dat er een voor ligt (1), en neem een punt dat een verder ligt(2). Die drie punten vormen samen een driehoek.
Punt (2) verwijder je vervolgens uit je polygoon. Daarmee ga je door totdat je nog maar 3 punten over hebt.

[The - DDD]

Ja, en dan ben je er natuurlijk nog niet he.

Je moet ook kijken over er een overlapping plaats vind als een punt niet in een ander polygoon valt...

Neem de volgende polygonen:
[x1,y1,x2,y2,x3,y3]

A: 0,0,0,1,1,0
B: 0,2,2,0,1,-1

Die punten check gaat goed, geen enkel punt ligt in een ander polygoon, maar deze twee overlappen dus wel.

Hier:
http://www.psky.com/polygonintersection.htm
staat alle wiskunde die je nodig hebt, veel succes.

Er zijn dus 4 mogelijkheden:
1: Geen overlap.
2: kruising van lijnen, met geen punten in andere polygoon
3: kruising van lijnen, met 1 of meer punten in andere polygoon
4: volledige insluiting van andere polygoon, alle punten van de 1 zitten in de ander.

Oh ja en je hebt ook nog twijfel gevallen. Stel dat twee punten van de ene polygoon exact op 2 punten van de andere vallen. Verder is er geen lijn kruising. Heb je dan wel of geen overlappend polygoon?

Toch niet zo simpel als dat je aanvankelijk dacht. Of niet