Fighting with computers

Computers are not always friendly.

Tuesday, April 17, 2012

Of polygon offsetting

Last week I have been researching about a task I initially did not even know the name: Polygon offsetting. A polygon offset (in case you ignored it too) is a computer graphics primitive (though it can be done by hand too) that given a polygon will trace a inner or outer version of it that it is either totally contained inside the polygon or that it will contain it entirely (if you want an outer offset) whose perimeter will be at a constant distance from the perimeter of the initial polygon. And given that I seriously doubt that my explanation is good enough, here you have an image (of an inner offset, gray-line perimeter):


I was looking for an available implementation of this process, as I wanted to be able to use it for an ongoing project. This time Google did not helped much and though I was able to find the question I borrowed the picture above from and that CGAL library did have polygon offset as one of the functions or that there was Clipper library or a Python implementation, none of them really filled the bill.

I was looking for a free implementation given that I am lazy and I did not want to do more work than needed. However, CGAL library license does require a fee for commercial use and it is based in C++ while I wanted to keep the cost low and prototyping using Processing (Java).  Clipper library would have been perfect but Java implementation was not available (C# implementation is available so a Java port may not be a huge endeavor, but 3.500 lines of code is not something I was planning to translate over a weekend).

I ended up doing my crappy implementation based on a very simple idea, that turned out not to be that brilliant:

  1. For each perimeter segment, create a parallel segment of equal length with a given inner offset. 
  2. Compute the crossings of the above segments to obtain the polygon offset.
What did not work was that polygon offset sometimes will give more than one output polygon, so if that is the case my approach is terribly flawed. If not it can be quite simple to implement, unfortunately I will have to refine my code to handle this problem.




0 Comments:

Post a Comment

<< Home