Re: [boost] [geometry] area, length, centroid, behavior

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-03-05 13:49:28

Mika Heiskanen wrote:
> Simonson, Lucanus J wrote:
>> Mika Heiskanen wrote:
>>> Do you have any plans to also add a robust buffering function?
>> 
>> Do you mean polygon fill?
> 
> Sorry, my fault. The terminology comes from GIS, and I now realize is
> probably not familiar to anyone outside GIS circles, since nobody
> else probably needs the operation.
> 
> After a quick google search, this seems to sum things up pretty well:
> 
>    "Buffer operations in GIS"
>    http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf
> 
> A very simple summary would be: a buffered polygon is the polygon
> which includes all points within the given distance from the original
> polygon. 
> The definition can be extended to points (circles) and polylines
> (lines 
> with width). For more details please see for example the above link.
> 
> The operation is just as important in GIS as logical operations.
> 
> Regards,
> 
> --> Mika Heiskanen
> 
Ah, yes, we call this resizing, sizing, inflate, deflate, etc.  I have also heard the term errosion, which would be the inverse operation to what you describe.  In fact, nearly everyone needs the operation, or some variaton of it.

The answer to your original question is yes.  When resizing there is typically an option of how to handle convex corners.  The common case is to maintain the topology and move the corner.  This means that an arbitrarily acute corner would move arbitrarily far, which is often not really what the user wants.  There are commonly options such as clipping the corner off at the resizing distance or making a segmented piecewise-linear circluar-arc around the corner that joins the resized edges before and after it.  It is this ciruclar arc option that seems to be what you are describing since it approximates the set of points within a distance of a polygon.  Other options for the algorithm would relate to snapping preferences for how to handle cases where the resizing distance must be approximated due to limitations of the coordinate data type.

Resizing operations are generally lumped into "Booleans" when I use that term.  They are planned.  I have them for manhattan and 45-degree and they are robust to 45-degree non-integer events.  For arbitrary angle I plan to implement them as soon as a request for them comes in from one of my internal users or as part of eventual boost submission.  It is trivial to add rectangles to the edges to inflate them (these are sometimes called Minkowski rectangles because the approach is described in his book and often attributed to him) and then fill in the concavities around convex corners with circular-arc pie-slices then pass that geometry through an OR operation.   I could problably implement the arbitrary angle version of resizing and integrate it fully into the library API in one to two days of programming effort and perhaps another one to two days of testing and validation effort.  The algorithm is linear except for the OR operation which is loosely O(n log n) for a certain definition of n and so is considered equivalent to a Boolean operation.

As an aside, the algorithm requires three points at a time instead of two, which means when you "wrap-around" when you reach the end of the sequence of polygon points the redundant point that "closes" the polygon is just in your way because you need the last (non-redundant) point and the first two to complete the algorithm.  My code checks for and discards the redundant point that "closes" a polygon in such circumstances.

Another algorithm equivalent to booleans is connectivity extraction.  This algorithm extracts the connectivity graph between polygons that are touching or overlapping.  I have it for manhattan and 45-degree geometry and can trivially add it through my flexible arbitrary angle scanline framework when the need arises.

The key thing about providing the resizing algorithm (or any other geometry algorithm) in a boost geometry library is not that it is there, but that it provides enough options to meet the needs of the majority of people who want to use it.  For instance, there may be GIS specific requirements that I wouldn't know to implement based upon my background in unrelated application domains.  This requires that people co-operate to at least the minimum extent of sharing requirements, which is why I'm not under the illusion that I can implement a boost geometry library alone.

Regards,
Luke