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

Support method to combine overlapping polygons in a Graph #26

Open
TaipanRex opened this issue Mar 13, 2018 · 2 comments
Open

Support method to combine overlapping polygons in a Graph #26

TaipanRex opened this issue Mar 13, 2018 · 2 comments

Comments

@TaipanRex
Copy link
Owner

overlaps = True
while overlaps:
overlaps = False
for each polygon n:
for each polygon m:
# https://techoverflow.net/2017/02/23/computing-bounding-box-for-a-list-of-coordinates-in-python/
# checking bounding boxes is a quick way to see if two polygons potentially overlap.
if the bounding box of n overlaps with the bounding box of m:
# combine the polygons or return both if they don't actually overlap
https://stackoverflow.com/questions/2667748/how-do-i-combine-complex-polygons
overlaps = True

Worst case this runs in O(n^3), i.e. all polygons overlap.

@deboc
Copy link
Contributor

deboc commented Apr 27, 2018

Personally, I preprocess the polygons with cascaded_union from shapely.ops.
I guess you want to avoid external dependencies. But I also guess that's the best implementation we can find.
(And shapely could also be useful for other preprocessing, as for #21)

@TaipanRex
Copy link
Owner Author

@deboc thanks for the suggestion. Yeah, I have tried to avoid dependencies. I am working on proper documentation on branch documentation. I might just reference Shapely and the specific function with an example, then let it be up to the user to do it.

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

No branches or pull requests

2 participants