[geos-devel] Buffering with obstacles

[Graham Toal]

On Thu, Oct 12, 2023 at 4:25 AM Graham Toal <gtoal at gtoal.com> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20231013/76312ca5/attachment.htm>