Re: [geos-devel] Buffering with obstacles
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 remaining 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. G ___ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
Re: [geos-devel] Buffering with obstacles
On Thu, Oct 12, 2023 at 4:25 AM Graham Toal wrote: > You need a variation of the shortest path algorithm; it's basically a > breadth-first flood fill, which is usually implemented by a raster > algorithm, however it *is* possible to come up with something less > expensive (but more complex to code) by using a ray-tracing algorithm (or > more specifically 'shadow casting'). I can't see an easy way to do it > using standard polygon operations though. > I've been thinking more about this problem and I think it might be possible on polygons. Some years back several of us at the MIT "Scratch" site wrote different ways of shadow casting (see https://scratch.mit.edu/projects/237786845/ for an example - click and drag the lightbulb around) not all of which were raster-based. Search the site for "pen shadow(s)" to see other examples. The missing polygon primitive needed is to construct a visibility polygon ( https://en.wikipedia.org/wiki/Visibility_polygon ), after which you would recurse down all the lines extending from the point of view with some sort of continuously varying buffering that extended the visibility by the remaining unexplored distance. One experiment I did on constructing the visibility polygon was to do a binary chop on all the obstacle polygons to determine their leftmost and rightmost extents relative to the viewpoint - try this demo to see that work: https://scratch.mit.edu/projects/115648650/ - I think it is doable in GEOS but not trivial. If GEOS is used in any programming classes I think the problem would make a good class project for kids! (The kids at MIT who worked on the shadow casting were mostly 12 - 16 yr olds) G ___ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
Re: [geos-devel] Buffering with obstacles
You need a variation of the shortest path algorithm; it's basically a breadth-first flood fill, which is usually implemented by a raster algorithm, however it *is* possible to come up with something less expensive (but more complex to code) by using a ray-tracing algorithm (or more specifically 'shadow casting'). I can't see an easy way to do it using standard polygon operations though. ___ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
