[C#/alg] Polygoon afsnijden/combineren

[Verwijderd]

Ik heb een polygoon (PointF array), waarvan ik een ander polygoon af wil snijden of combineren. Beide polygonen kunnen convex of concaaf zijn. Over het algemeen zullen de polygonen die afgesneden worden gewone vierhoeken en driehoeken zijn, het resultaat zal meestal een n-gon worden. Het resultaat wordt op een later moment in mijn prog weergegeven op het scherm.

ff subtract visualiseren.


Ik heb aardig wat uurtjes in zoeken zitten, maar ik kan gewoon geen goed algoritme vinden om dit te realiseren. Ik ben al zelf bezig geweest om te kijken of ik zelf een goed algoritme kan bedenken, maar ik krijg het idee dat ik hiervoor toch echt te kort schiet (of ik bekijk het gewoon te moeilijk...).

Ik kan dmv van crossings test (lijnen in de polygoon overlappen elkaar niet, dus dit werkt altijd goed) wel bepalen of een punt in de polygoon ligt en ik kan ook wel snijpunten berekenen, ik kan echter geen goede methode bedenken om de punten in goede volgorde toe te voegen aan het PointF array.

Heeft iemand misschien een idee of eventueel voorbeeld code waarmee dit gerealiseerd kan worden?

Bij voorbaat dank.

[Xiphalon]

volgens mij moet het zo kunnen:
Itereer met de klok mee over de lijnen
zit er een kruising in? Dan die lijn opknippen op het snijpunt en het snijpunt toevoegen.
Daarna tegen de klok in het andere object itereren, en de vertices toevoegen tot je weer een snijpunt met het originele object hebt. (of tot je een vertex tegenkomt wat buiten het originele object ligt, whatever sneller is)

Hoe dit algorithme werkt met bijv 2 rechthoeken in een + vorm (dus - en | over elkaar heen) weet ik niet.

[Feyd-Rautha]

Een beroemde naam voor dergelijke problemen is 'Sutherland'. Je moet misschien eens zoeken naar algoritmes die hij ontworpen heeft en ook op de term 'clipping'.

Het 'Sutherland-Hodgman' algoritme kun je wel gebruiken denk ik.

[ Voor 17% gewijzigd door Feyd-Rautha op 01-05-2007 09:44 ]

[Janoz]

De voorbeelden die je hier plaatst zijn nog redelijk simpel. Als je polygonen altijd met de klok mee gedefinieerd zijn en je weet op welke positie in de puntlijst de snijpunten komen dan kun je de punten op het polygon dat je uitsnijdt tegen de klok in doorlopen. Het wordt pas echt spannend wanneer je met je 'knippende' polygon het orginele polygon doormidden knipt.

[Verwijderd]

Feyd-Rautha schreef op dinsdag 01 mei 2007 @ 09:42:
Een beroemde naam voor dergelijke problemen is 'Sutherland'. Je moet misschien eens zoeken naar algoritmes die hij ontworpen heeft en ook op de term 'clipping'.

Het 'Sutherland-Hodgman' algoritme kun je wel gebruiken denk ik.

Ahum, ik geloof dat ik gewoon verkeerd gezocht heb. Da's bij mij vaak het probleem, ik weet vaak niet de juiste woorden om op te zoeken.

Thanks, ik ga er gelijk aan werken.

[Verwijderd]

Janoz schreef op dinsdag 01 mei 2007 @ 09:46:
Het wordt pas echt spannend wanneer je met je 'knippende' polygon het orginele polygon doormidden knipt.

Dat is theoretisch in mijn case niet onmogelijk, maar zal in de praktijk vrijwel nooit voorkomen.

Janoz schreef op dinsdag 01 mei 2007 @ 09:46:
Als je polygonen altijd met de klok mee gedefinieerd zijn...

Dat is momenteel niet het geval, denk dat het te maken heeft met de input, de simpele tekeningen die ingevoerd behoren te worden werken vanaf de linkeronderhoek (links naar rechts en onder naar boven), terwijl de computer juist vanaf de linkerbovenhoek tekent. Dat is overigens ook één van die punten die ik mijn prog uit de wereld wil helpen, maar da's niet relevant voor dit topic.

[Janoz]

Lijkt me toch redelijk relevant. Hoe is dan nu daadwerkelijk het polygoon gedefinieerd? Zeker als de polygonen niet convex zijn ben ik erg benieuwd hoe de edges dan zijn gedefinieerd. Er zijn namelijk wel meerdere mogelijkheden om van een groep punten een polygoon te maken zonder dat edges elkaar kruisen.

[Verwijderd]

Tegen de klok in?

[PrisonerOfPain]

Feyd-Rautha schreef op dinsdag 01 mei 2007 @ 09:42:
Het 'Sutherland-Hodgman' algoritme kun je wel gebruiken denk ik.

Sutherland-Hodgman kan enkel clippen tegen convex polygonen. Om willekeurige polygonen te clippen word over het algemeen Weiler-, een verbetering van Weiler-Atherton-, clipping algorithme gebruikt. Een duidelijke omschrijving word gegeven in Computer Graphics, principles and practices; een bijbel op dit gebied.

[Janoz]

Of polygonen met de klok mee of tegen de klok in gedefinieerd zijn iz natuurlijk lood om oud ijzer. Wat ik meer bedoelde bij mijn algorithme omschrijving was dat er iig een volgorde gedefinieerd was. Of betekent het vraagteken dat je eigenlijk niet weet hoe ze zijn gedefinieerd?

@ hieronder: Welke volgorde?

[ Voor 5% gewijzigd door Janoz op 01-05-2007 10:40 ]

[Verwijderd]

De punten liggen op volgorde in de array.

[ Voor 48% gewijzigd door Verwijderd op 01-05-2007 10:44 ]

[.oisyn]

Hoe wil je de case handlen waarin poly B zich geheel in poly A bevindt? Je krijgt dan een gat in het resultaat A-B.

[Grijze Vos]

Verwijderd schreef op dinsdag 01 mei 2007 @ 10:37:
De punten liggen op volgorde in de array.

[afbeelding]

Je berekent de snijpunten met je oude figuur. Dan kijk je welke nieuwe punten in je oude figuur liggen. Die voeg je dan toe aan je lijst in counterclockwise volgorde, tussen je oude punten.

Ik weet niet hoe je input in elkaar steekt natuurlijk, maar zoals hierboven gezegd moet je speciale gevallen voorbeelden staan wel even bekijken.

Dus in je voorbeeld dan heb je rechthoek AFGH, en zet je er een rechthoek in. Dan worden B en E berekend als zijnde snijpunten, en C en D zijn de punten die in je oude rechthoek liggen. Dan weet je dat je B na A moet invoegen, en E voor F, vervolgens moet je nog even bepalen in welke volgorde C en D horen te liggen, en dan ben je klaar. (Als je er niet uitkomt, kun je gewoon een optie proberen, bijv. DE, en er dan achter komen dat BD en CE elkaar snijden. Dan weet je dus dat het CD moet zijn.

Maar het lijkt me dat je ook wel vooraf kunt berekenen welke volgorde het moet zijn.

[ Voor 34% gewijzigd door Grijze Vos op 01-05-2007 12:15 ]

[Verwijderd]

@.oisyn
In principe worden die op een andere manier afgehandeld, deze worden direct op het scherm getekend.

@Grijze Vos
Dat gaat niet helemaal op als de clip op een hoek van de polygon ligt, omdat er dan een punt teveel in staat, het punt dat in de clip valt, wat overigens wel eenvoudig te bepalen is en alsnog verwijdert kan worden.

[ Voor 54% gewijzigd door Verwijderd op 01-05-2007 12:31 ]

[.oisyn]

darkmage schreef op dinsdag 01 mei 2007 @ 09:37:
volgens mij moet het zo kunnen:
Itereer met de klok mee over de lijnen
zit er een kruising in? Dan die lijn opknippen op het snijpunt en het snijpunt toevoegen.
Daarna tegen de klok in het andere object itereren, en de vertices toevoegen tot je weer een snijpunt met het originele object hebt. (of tot je een vertex tegenkomt wat buiten het originele object ligt, whatever sneller is)

Wel even opletten dat het snijpunt pakt dat het eerst komt in het geval dat meerdere edges van de ene polygoon een edge van de andere snijden, en dat je begint met een vertex van de subject polygoon dat niet in de clippingpolygoon ligt (anders krijg je B-A ipv A-B )

Hoe dit algorithme werkt met bijv 2 rechthoeken in een + vorm (dus - en | over elkaar heen) weet ik niet.

Dit algoritme werkt idd niet als het resultaat complex is (gaten danwel eilanden)

Verwijderd schreef op dinsdag 01 mei 2007 @ 12:20:
@.oisyn
In principe worden die op een andere manier afgehandeld, deze worden direct op het scherm getekend.

Dan is het algoritme dat darkmage beschreef in de post die ik zojuist quotte het makkelijkst denk ik.

[ Voor 20% gewijzigd door .oisyn op 01-05-2007 16:19 ]

[MrBucket]

Wat misschien ook nog een ingang is om dit probleem beter behapbaar te maken: de Doubly-Connected Edge List. Dit is een datastructuur die speciaal bedoeld is om efficient en intuitief planaire subdivisies (maw: een verzameling aangrenzende polygonen) mee op te bouwen, op te slaan en operaties op uit te voeren.

Voor de gelinkte pagina, zie met name de onderwerpen t/m "The objects" (maar dit is lang niet de enige bron van informatie over deze datastructuur - misschien is er zelfs wel een library voor in C#)

--edit
En nog een ideetje: als je de polygonen A en B opsplitst in een verzameling x-monotone* polygonen, dan bestaat elk van deze x-monotone polygonen uit een 'simpele' ketting van edges aan de bovenkant en een 'simpele' ketting van edges aan de onderkant. Snijpunten tussen twee van deze kettingen kunnen in lineaire tijd gevonden worden, en ook het uitrekenen van de 'hoogste' cq. 'laagste' combinatie van twee kettingen is een redelijk triviaal probleem.

* De definitie die hier wordt gegeven is:
Monotone Polygon - An x-monotone polygon is a simple polygon with the following property: if you sweep a vertical line from the leftmost point [of the polygon] to the rightmost point, [at any position within the sweep] the sweep line will intersect with exactly two segments [of the polygon].

[ Voor 44% gewijzigd door MrBucket op 01-05-2007 22:20 ]

[.oisyn]

MrBucket schreef op dinsdag 01 mei 2007 @ 22:00:
Wat misschien ook nog een ingang is om dit probleem beter behapbaar te maken: de Doubly-Connected Edge List. Dit is een datastructuur die speciaal bedoeld is om efficient en intuitief planaire subdivisies (maw: een verzameling aangrenzende polygonen) mee op te bouwen, op te slaan en operaties op uit te voeren.

Een DCEL is nuttig om topologie te beschrijven bij meerdere polygonen. Aangezien je er nu maar 1 hebt geeft een array van vertices net zoveel informatie als een DCEL . Bovendien is het bijhouden van een DCEL erg foutgevoelig, je moet goed opletten dat je geen referentie vergeet te wijzigen (en ga de fout maar eens vinden als je het dan toch wel bent vergeten).

[ Voor 13% gewijzigd door .oisyn op 02-05-2007 10:58 ]

[Verwijderd]

Op één of andere manier zijn er altijd wel weer haken en ogen aan elke manier die ik geprobeerd heb. De enige manier die ik enigszins werkend heb gekregen is een weiler-atherton-achtig algoritme, maar die manier (zoals ik het gedaan heb) is zo inefficient als de p*st.

De theoriën kloppen allemaal en met het oog is het simpel op te lossen. Waar ik echter elke keer weer tegenaan loop is, hoe weet ik waar ik moet beginnen met zoeken naar snijpunten? Hoe ga ik bepalen waar ze ingevoegd moeten worden? Ik kan vele voorbeelden bedenken waar één van de twee polygonen niet de ideale vorm heeft. Dit is wel op te lossen, maar vereist veel meer loops.

Voorbeeld:


Nu kan je wel zeggen, de input moet er ook aan aangepast zijn, nou wat als de input deze vorm heeft?



Welk punt zit op index 0 in mijn array van punten?

Er zijn trouwens ook bar weinig voorbeelden in C#/VB.NET over dit onderwerp te vinden op internet, alleen voorbeelden in wazig C...

Soort van ideëen of verbeteringen zijn welkom...

[.oisyn]

Verwijderd schreef op vrijdag 04 mei 2007 @ 13:28:
De theoriën kloppen allemaal en met het oog is het simpel op te lossen. Waar ik echter elke keer weer tegenaan loop is, hoe weet ik waar ik moet beginnen met zoeken naar snijpunten?

Gewoon het eerste punt dat niet in het clippingpolygoon ligt

Hoe ga ik bepalen waar ze ingevoegd moeten worden?

Je moet niet invoegen, je moet gewoon een nieuwe lijst maken, en tijdens het aflopen voeg je gewoon aan het eind van die lijst toe.

[Verwijderd]

Tja, dat resulteert er volgens mij in dat je de clipping polygon minimaal twee keer achter elkaar moet doorlopen om de juiste volgorde te achterhalen. Laten we het dan nog niet hebben over clipping polygon edges die meerdere subject polygon edges doorkruisen, waardoor het helemaal een chaos wordt. Of ik moet het wederom verkeerd begrijpen...

[MicroWhale]

In principe maakt het niet uit waar het beginpunt van je polygon ligt, als je maar weet welke kant je polygon op draait. Mocht je dit niet weten, kun je door een "inside" van elk punt van een snijdend polygon op een ander polygon kijken of het bij de verzameling punten hoort die aan het polygon toegevoegd dient te worden.

Bij mijn vorige werkgever was hier iemand fulltime mee bezig (geografische informatie) en hij kwam telkens nieuwe problemen tegen. Mede omdat er ook "gaten" in polygonen konden zitten, wat de boel nog een stuk complexer maakt.

[Verwijderd]

@MrWilliams:
Inderdaad ztten er veel haken en ogen aan dit proces. Ikzelf houd me bezig met GeoGrafische informatie (GIS) en dit is een veel voorkomend probleem. Uiteraard zijn er oplossing voor. Binnen GIS is bijv. de regel dat een polygon zich NIET mag kruisen. Dit lost al een heleboel problemen op. Verder werken we ook met de volgorde. Met de klok mee is een vlak, tegen de klok is een gat in een vlak.
@Dominique:
Als je je probleem geografisch kunt oplossen dan zijn er veel (kant-en-klare) oplossing voor dit probleem. Zoek maar een op [google]GIS clipping[/google].
Je kunt sowieso eens kijken bij www.mapwindow.org, daar hebben we dit probleem voor 98% opgelost.

[Janoz]

Het makkelijkste is om er voor te zorgen dat al je polygonen convex zijn. Dit is redelijk simpel te bereiken door niet convex polygonen op te delen in convex polygonen. Op een ander niveau kun je vervolgens wel bijhouden welke polygonen horen bij welk orgineel polygon. Wanneer je convex polygonen zijn de algorithmen een stuk makkelijker. Het bepalen of een punt binnen een ander polygon ligt is dan heel simpel te doen door uit te rekenen of een punt rechts (of links bij tegen de klok in) van alle edges ligt. Het overlappen van 2 polygonen is kijken of een punt van de ene polygon in de ander ligt en/of een punt van de ander in de ene ligt.

[.oisyn]

MrWilliams schreef op vrijdag 04 mei 2007 @ 15:10:
In principe maakt het niet uit waar het beginpunt van je polygon ligt, als je maar weet welke kant je polygon op draait.

Exact. In feite hoeft een polygoon niets meer te zijn dan een lijst van vertices in de juiste volgorde. Met welke vertex hij begint doet er niet toe.

Bij mijn vorige werkgever was hier iemand fulltime mee bezig (geografische informatie) en hij kwam telkens nieuwe problemen tegen. Mede omdat er ook "gaten" in polygonen konden zitten, wat de boel nog een stuk complexer maakt.

Ik ben er ook fulltime mee bezig, maar dan in 3d. Nog leuker . Bij mij maakt de output overigens niet zo heel veel uit omdat er toch getrianguleerd moet worden - het gaat dus alleen om het oppervlak van het subject, niet om de inhoud. Ik kan dus een bsp tree maken van de clipping volume en daarmee stukjes van het subject volume afhakken. Overigens is de inhoud hiermee ook wel weer te achterhalen als je van het subject ook een bsp maakt. Dit is eigenlijk gewoon CSG voor polytopen.

[ Voor 9% gewijzigd door .oisyn op 04-05-2007 15:44 ]

[Verwijderd]

Waarom krijg ik het dan niet voor elkaar ?

[.oisyn]

Misschien dat je het morgen wel weet...

[Verwijderd]

Daar hoop ik ook op