Posts

Showing posts from May, 2012

Union of polygons

Image
I should have settled with a graphics library of some sort, but I did not. So now I have all sorts of problems some of these libraries have one function call away. Unfortunately many library creators do expect to be paid if you do a commercial product using their code. I find this to be fair, but not knowing how much or for how long just stir me away.

My current problem is a simple one: I have collection of 2D polygons and I want to obtain the union of all of them. Sometimes it is a bigger polygon, sometimes a set of disconnected areas. It turns out that non-convex polygons make the solution harder than I expected. As I am writing code in Processing (Java) I could used JavaGeom, but it is based in GPC library. I could use JTS library, but I was lost in the process of learning how to integrate it with my code, but this was before I learned the problem took me longer to get it coded than learning another library. You have been warned!

Update: If you can settle with integer coordinates, y…

Another week, another problem

Image
The project I am working on at the moment requires solving several computer graphics problems. I mentioned a while ago the polygon offsetting problem. Today my problem is about placing polygons on pages to be printed. I want to make the listing as short as possible, thereby packing the polygons in fewer pages is desired.

Trying not to reinvent the wheel I googled around first. Of course the first problem of the googling thing is to figure out what is the popular name of the problem you are interested on (and believe me, I am yet to find an "original" problem never thought and wrote about it before). My first searches suggested Cutting stock problem, but  it was not exactly my case. It is a pity as in 2007 a dynamic programming solution was published. So moving on I found the best fit to be the Bin packing problem.  Again, an NP hard problem.

Wikipedia article suggested the heuristic of the first fit algorithm, that is known to provide good (but not optimal) solutions withou…