Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Visibility graphs have a huge number of polygon crossings #48

Open
ekrell opened this issue Apr 8, 2020 · 11 comments
Open

Visibility graphs have a huge number of polygon crossings #48

ekrell opened this issue Apr 8, 2020 · 11 comments

Comments

@ekrell
Copy link

ekrell commented Apr 8, 2020

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.
sample_region

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.

sample_region_path

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.

@ekrell
Copy link
Author

ekrell commented Apr 8, 2020

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?

@ekrell
Copy link
Author

ekrell commented Apr 8, 2020

Update: coordinates seem to be at play. I scaled each by 1000 and got something better: far fewer polygon intersections!

The graph:
sample_region_graph

The path:
sample_region_path

@ekrell
Copy link
Author

ekrell commented Apr 9, 2020

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.

sample_region_graph

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.

@TaipanRex
Copy link
Owner

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.

@ekrell
Copy link
Author

ekrell commented Apr 12, 2020

sample_region_graph_mini
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?

@ekrell
Copy link
Author

ekrell commented Apr 13, 2020

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.

sample_region_graph_mini

@SteynJanus
Copy link

SteynJanus commented Jun 21, 2023

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 :)

@ekrell
Copy link
Author

ekrell commented Jun 22, 2023

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 :)

@eagerbeaver04
Copy link

Hello, may be you can help me. I installed this package today and tried to get shortest path. I already tried rounding and smoothing.

Image

@TaipanRex
Copy link
Owner

@eagerbeaver04 this is likely due to floating point representation issues as your coordiate system uses quite large numbers. take a look at this documentation and try reducing COLIN_TOLERANCE in visible_vertices.py (assuming you have cloned the repo), or just make your coordinates smaller by dividing by 1000.

@eagerbeaver04
Copy link

Thank you very much!

Image

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants