Ořezání libovolného 2D polygonu polygonem

[Manox]

Ahoj,

už hodně dlouhou dobu řeším tenhle problém. Používal jsem Weiler Atherton algoritmus a všechno to vypadá dobře. Bohužel jen na papíře a přednáškách ze škol. Ovšem nikde jsem nenašel nějaké řešení pro speciální případy a s těmi mám obrovské problémy. Hlavně pokud leží nějaké vrcholy jednoho polygonu na druhém. Pak je to celé špatně. Udělal jsem nějaké vlastní úpravy, ale vždycke se najde nějaký případ co to nepokryje. Nevíte náhodou někdo o nějakém návodu, co funguje ve všech případech ? Díky

[Dr.Sid]

Napsal jsem celkem funckni system na obecne operace nad polygony ve 2D. Bohuzel je to komercni. Zadny specialni algoritmus to neni, spis rozbiti na mensi jednoduche ulohy.

- prevest polygony na 2 bodove usecky. Dale se pracuje jen s useckami. Plosna povaha vstupnich polygonu se momentalne ignoruje.
- narezat krizici se usecky. Osetruji se specialni pripady bod na bodu, bod na hrane, nebo obecny hrana vuci hrane.
- vytvoreni vsech vzniklych dilku pres projiti grafu usecek s prednosti nejlevejsiho vychodu. Napriklad kdyz prekryju do krize dav obdelniky, vznikne 5 neprekryvajicich se dilku, plus dil ktere predstavuje okoli. Kazda hrana se pouzije 2x, v kazdem smeru jednou (podle toho se pozna jestli se muze pouzit nebo ne).
- detekce ze kterych zdroju kazdy dilek vznikl (pres bod v plose, coz je celkem rychle)
- aplikace logickych pravidel pro vytrizeni dilu (pokud delam prunik, vezmu jen ty dily ktere lezi v obou zdrojich a podobne)

Je to relativne pomale, nektere kroky by jiste slo sloucit. Ale praveze ta uloha je tak slozita, a ma tolik moznych variant, je snazsi testovat a ladit jednotlive kroky.

[johnnash]

Tady jsou reseny specialni pripady pro Weiler Athertona http://pierloic.free.fr/clip/clip.html.