Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I've been wondering how the equations/algorithms behind buffering tools actually work?

share|improve this question

2 Answers 2

up vote 8 down vote accepted

If you are interested in an implementation look at jsts a Javascript implementation of the much used Java Topology Suite library -- depending on whether you prefer reading Javascript or Java, I suppose.

A general idea of how the algorithm works.

For points, it is trivial, you simply buffer them by a given radius. If you have multiple points, you will have to find their intersections, create an outer ring, and then use a Planar graph to figure out the inner rings (if any).

For line segments, the algorithm basically takes a segment, calculates two points perpendicular to each end point (using basic trigonometry) a buffer distance away and then connects these points. Depending on the angle between this line segment and the next, these buffer end points are either connected with an arc of appropriate length (if it is greater than 180 degrees), to the next set, or the line intersection between them is calculated, in the case of a turn of less than 180 degrees. Again, a planar graph is constructed for interior points, which is then used to produce the inner rings (if any). A planar graph is constructed so as to have no intersecting line segments, so is a good data structure for calculating inner rings efficiently.

There is a decent explanation in this pdf from the Unniversity of Minnesota.

share|improve this answer
    
I knew this stuff had to be out there! Thanks so much! –  GeoGhost 9 hours ago

In my MPSuperShape product, it is possible to apply a buffer to a convex polygon. This is performed by moving the vertices outwards on the line that bisects the two edges at that vertex. The distance is chosen using trigonometry so that the edges both move out a user-specified distance.

This works well but acute vertices can extend disproportionately. Ie. the new vertex is a lot more than (specified buffer distance) from the old vertex. A more complex shape model (MPSuperShape is for MapPoint which has a basic shape model!) would added a rounded edge of constant distance from the vertex.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.