search

falling-fruit / falling-fruit-api

API (v0.3) for Falling Fruit
https://fallingfruit.org/api/0.3
GNU General Public License v3.0
7 stars 2 forks source link

Add bounding boxes for clusters #30

Open wbazant opened 1 month ago

wbazant commented 1 month ago

Follow-up from https://github.com/falling-fruit/falling-fruit-web/issues/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 commented 2 weeks ago

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 commented 2 weeks ago

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!