I've been wondering how the equations/algorithms behind buffering tools actually work?
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. |
|||||
|
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. |
|||
|