TaipanRex
Visibility graphs have a huge number of polygon crossings
I am trying to create a visibility graph from a shapefile, following the examples. The example programs run fine, and I am able to get a correct path. For my own shapefile, the visibility graph seem to never avoid crossing the polygons. So solution paths always cross a polygon if a polygon exists between them.
Here is my original map, plotting the polygons with matplotlitb.
For faster debugging, I made a reduced shapefile with only two polygons.
Here, I plotted all the edges in graph.visgraph.get_edges(). You can also see the solution path passing through the polygon.
Any idea what might cause this? Happy to share code if it helps. The code starts by converting a raster to polygons with fiona, saving them as a shapefile, then following example 1. Not too experienced with geospatial data, so I could have made an error here. But the polygons load fine in QGIS.
Just to add some extra details, I remade the shapefile in QGIS in case I was doing something wrong with the python libs. I got the exact same result, so I think my shapefile is fine.
Can the fact that this is a very high res, zoomed in region (compared to the globe-trotting example scripts) affect it? The coordinates are just not very different from point to point --> float errors?
Update: coordinates seem to be at play. I scaled each by 1000 and got something better: far fewer polygon intersections!
The graph:
The path:
I was able to come up with a work-around. The coastlines shapefile worked and so did my own hand-drawn test file in QGIS worked. The only one that didn't work was a raster converted to a shapefile. So I pulled up my raster->shapefile in QGIS, redrew a less "blocky" shapefile on top (still complex with lots of points).
I input this new version and it had only about 5 polygon-crossings. But after rounding and normalizing the coordinates, there were no edge crossings.
Conclusion? The blockiness of a converted raster does not play well with the VG generation. Ultimately my pipeline will be automatically converting rasters to polygons for this, but I should be apply to smooth them a bit in the code.
Yeah this is likely rounding issues when you have a large amount of vertices that are very close to each other. Reducing the number of vertices is the best fix, as well as scaling like you did.
With more data, still seeing a number of crossings. I have done numerous trials with number of rounding digits, range of new scale, etc. Note the above only shows a sample of the edges.
More polygon smoothing might help, but they are already lower resolution than I would like. Specifically dealing with nearshore USVs.
Anything else I should try?
Just for reference, here it is with much smoother polygons. Like you said, it is sensitive to shape complexity. I would like to work with higher resolution, but I can get by with this for now. Later I can look into tuning this part.
Hi Ekrell. Did you already happen to find a nice solution to this? The final image seems to have no crossing but also has a high resolution. Was it just a story of finding the right scaling factor and smoothing factor? Also, did you scale it in pyvisgraph? Thanks in advance :)
Hello SteynJanus,
Sure enough, my solution was just to apply a little bit of smoothing to the polygons.
You can see the full code here where I build the shapes (some very rough code made for a class project....): https://github.com/ekrell/conch/blob/master/planners/vgplanner_build.py
And the exact line is here (101): shape_ = shape_.simplify(0.0005, preserve_topology=False)
This resolution turned out fine for my needs. Hope this helps :)