Fighting with computers

Computers are not always friendly.

Tuesday, May 08, 2012

Union of polygons

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, you can use java.awt.Polygon objects and turn them into java.awt.geom.Area objects that accept CSG primitives (union, difference, xor and intersection). It just works.

Update2: Actually, it can all be solved with Java2D framework, even for float values for coordinates. Polygon class is only for integer coordinates, but the GenericPath class accepts float coordinate values, so you can use it for defining Polygon-like contours that can later be united if turned into Area objects. The other detail is that union is not called this way in Area class but "add".

Tuesday, May 01, 2012

Another week, another problem

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 without too much work. The idea is as follows:
  1. First sort all the polygons in descending order of height.
  2. Next, try to fit a polygon in the available pages, leaving it there at the first fit.
  3. If no room was found, add a new page and fit the polygon in that page.
  4. Repeat until all polygons are allocated to a page.
The first results were much better than my naïve, first implementation: If it does not fit in the current page, just open a new one :-)

I have added later a small variation that tries to add the polygon not only at the current orientation but also rotating it 90 degrees. This has improved a bit the efficiency, but I guess the best approach here might be to find the rotation that creates the minimum bounding box for each polygon before attempting to perform the fit.

Still, I can see that there is still a lot of empty space on the pages of my output and that a more thoughtful approach can take advantage of part of it. Any help is appreciated!!!

Update: Nesting problem is the popular name in the CAD environment.