5

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

12

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.

  • I knew this stuff had to be out there! Thanks so much! – GeoGhost Oct 6 '14 at 18:05
  • Just to be smirky: jsjts is really java implemented using javascript, so it's about the same ;) – atlefren Oct 7 '14 at 13:06
  • jsts is totally and unashamedly a rewrite of JTS. Perhaps I should make that explicit. Personally, I prefer reading JS to Java, but that is just my opinion. With so much GIS work being done on the web these days (OpenLayers, Arcgis online) perhaps easier to integrate too. – John Powell Oct 7 '14 at 13:15
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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