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

Add bounding boxes for clusters #30

Open
wbazant opened this issue Oct 5, 2024 · 2 comments
Open

Add bounding boxes for clusters #30

wbazant opened this issue Oct 5, 2024 · 2 comments

Comments

@wbazant
Copy link

wbazant commented Oct 5, 2024

Follow-up from falling-fruit/falling-fruit-web#423. Going to isolated clusters could be a nicer experience if we were able to zoom in just into their bounding box.

Implementation idea, without looking at the code: given a list of locations for a cluster and their centre, find max(lat), min(lat), max(lng), min(lng)?

The bounding boxes could be calculated optionally, maybe even with a hardcoded upper bound for a count, since they're most useful for sparsely populated places with a handful of locations.

For example: two locations in Ullapool town centre are visible as a cluster in https://beta.fallingfruit.org/map/@58.1014684,-5.5723643,8z but it takes three clicks to get to them.

@ezwelty
Copy link
Contributor

ezwelty commented Nov 6, 2024

It is easy to initially build the clusters with min, max lat, lng, and it is trivial to increment the cluster bounds when a location is added or moved, but it is not at all trivial to decrement the impacted clusters when a location is moved or deleted. In fact, I think it would require recomputing the min, max from scratch, which could be a non-negligible performance hit in areas with lots of locations.

@wbazant
Copy link
Author

wbazant commented Nov 7, 2024

Fair. Could we instead leverage the quadtree structure? We don't actually want the bounding boxes - just information about sparsity that helps the zoom.

For example, if the children of a cluster are labelled "w"/"x"/"y"/"z" , define a zoom path for a cluster to be null if the cluster has two or more children, empty string for a leaf node, and name of the only child plus the child's zoom path. Then the interface can convert e.g. "wwwyz" into the bounds of the only populated quadrant.

An idea I had on the way to that one is to define zoom level - which is the cluster's nesting level if it has 0,2,3, or 4 children, or its only child's zoom level - but that doesn't work if you need to union clusters of different types. Meanwhile, the union zoom path is the longest common substring. So if a cluster for type T1 has a zoom path "wwwyz" and a cluster for a type T2 has a zoom path "wwz", the cluster for T1+T2 has a zoom path "ww".

Not saying we have to do this at any particular time, just thinking about the problem!

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

2 participants