[geos-devel] Buffering with obstacles

Graham Toal gtoal at gtoal.com
Fri Oct 13 02:24:05 PDT 2023

OK, I have the solution now.

1) Starting at point X,Y draw a circle of radius B (B = buffering dist)

2) Construct the visibility polygon from X,Y limited by the circle.

3) The visibility polygon will be effectively a list of rays from
   X,Y to points on the obstacles.  Collect the list of points where
   the rays touch an obstacle at a line segment end-point - including
   where they touch tangentially and may carry on past that edge point
   to another obstacle.  I.e. one ray may generate more than one point.

4) At each of those points at a distance D from X,Y, recursively invoke
   this algorithm with the distance parameter reset to B-D, until the
   distance is zero.

The resulting polygon will consist of straight line segments (from
obstacle edges facing the source points, and projections past edges)
plus circular arcs where the circles expire due to having reached the
maximum buffering distance without having touched any object.

So the only polygon operation really needed to implement this is the
construction of the simple distance-limited visibility polygon, which is
done by finding the objects within range B from X,Y and enumerating
the end-points of the segments composing that object facing X,Y.  The
recursion takes care of the complexity of shapes and the union of
all the partial results creates the final buffered object.

I hope I managed to explain that OK. If not, let me know and I'll try to
generate some graphics to make it more clear.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20231013/e81c3126/attachment.htm>

More information about the geos-devel mailing list