[C#, convex hull]Meerdere polygons

[Verwijderd]

Ik ben in de voorbereiding van een functie voor het maken van een convex hull van een serie van polygons.
Nu ben ik me aan het inlezen en ik denk dat ik Grahams scan het beste kan gebruiken.
Dit algoritme gebruikt de punten van de polygon om de convex hull te bepalen.
Nu wil ik hetzelfde doen voor meerdere polygons die om elkaar heen liggen en waarbij er een heleboel 'binnen in' kunnen liggen en dus niet mee doen voor de convex hull bepaling.

Nu is mijn vraag hoe ik dit het beste kan doen:

• Gewoon alle punten van alle polygons gebruiken en daar de convex hull van bepalen;
• Eerst bepalen welke polygons binnen in liggen en dan die niet meenemen;
• Eerst een merge uitvoeren van alle polygons en dan van de resulterende polygon de convex hull bepalen;
• Andere mogelijkheid waar ik nog niet aan gedacht heb

De keuze zal gemaakt worden op basis van snelheid. In de praktijk zal het voorkomen dan deze functie op heel veel polygons moet werken.
Voor de beeldvorming: Bijv. de convex hull bepalen van alle postcodegebieden van Nederland.

Graag lees ik jullie gedachten hier over.

Paul

[.oisyn]

Hebben we het over een 2D of een 3D convex hull? Je hebt het over postcodegebieden, wat een 2D convex hull impliceert, dus daar ga ik maar even vanuit. In het geval van 2D is een convex hull in O(N log N) verwachte tijd te berekenen. Ik weet niet over hoeveel vertices je het hebt, maar ik vermoed dat verts filteren die in polygonen liggen niet zo heel veel invloed zal hebben op het totale proces (that is, het berekenen van de convex hull is wel sneller, maar de rest van de tijd verdoe je met het vinden van polygonen in polygonen, wat ook minimaal O(N log N) zal kosten)

[Verwijderd]

Ik heb inmiddels een werkend stukje code en inderdaad gaat het best snel en heeft het geen zin om eerst uit te zoeken welke punten niet meegenomen hoeven te worden.
10 miljoen random punten worden in 40 sec verwerkt.
Overigens gaat het om 2D.

Bedankt voor het meedenken.