# Polygon Clipping

## Recommended Posts

edit:
the jittering algorithm appears to fail in 0.1% of all cases
I'll try to find a better way

I implemented this polygon clipping algorithm
[url="http://en.wikipedia.org/wiki/Weiler%E2%80%93Atherton_clipping_algorithm"]http://en.wikipedia....pping_algorithm[/url]

here you can see it working
[media]http://www.youtube.com/watch?v=xRj53EceY10[/media]

solving degenerate cases is very troublesome though
at first I tried to handle every degenerate case properly but it seems to be very hard to impossible
since I don't need 1000% accuracy (I am fine with up to 0.5 pixel of jittering) I decided to randomly move polygon points until all degenerate cases are gone but I must have overlooked something

I am trying to get this to work since months so I decided to ask for help

the algorithm is supposed to subtract a polygon from another polygon and returns a list of polygons as a result of this subtraction
how it works:
1. create linked lists of vertices from both polygons
2. randomly move vertices until they are not on top of any lines
3. calculate all intersection points twice (once for each polygon) and connect them
4. insert intersection points into linked list of vertices
5. start at any intersection point and move through the linked list, swap list if another intersection point is reached

is there any easier way to deal with degenerate cases?

sidenote: I also tried java topology suite but for some reason it is a few tenthousand times slower (no exaggeration)

#### Share this post

##### Share on other sites
I haven't implemented it (every time I try to tackle polygon clipping, I get the same problems with degeneracy!), but this paper might be of help: [url="http://cadanda.homestead.com/CAD_A_3_1-4_48.PDF"]http://cadanda.homestead.com/CAD_A_3_1-4_48.PDF[/url]

It seems to work, at least judging from this: [url="http://zrusin.blogspot.com/2007/01/set-operations-on-paths.html"]http://zrusin.blogspot.com/2007/01/set-operations-on-paths.html[/url]

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account

## Sign in

Already have an account? Sign in here.

Sign In Now

• ### Forum Statistics

• Total Topics
628366
• Total Posts
2982274

• 10
• 9
• 13
• 24
• 11