QuadTree: The answer to nearest address problem
This week’s article from Fleetx tech team’s wonder box, deals with a universal use-case for all our fleet owners. It is the nearest address problem (I can see the competitive programmers salivating). Chances are, you have seen it in action, in different variations from Zomato, Uber, Happn (yeah dating too!) to even games.
For others, often, the point of interest is a user, around whom we need to find nearest addresses. But for Fleetx, there is a difference. We need to find the nearest addresses of all vehicles. So, if a fleet owner has 1000 vehicles, we need to iterate over a list of 1000 vehicles and find each vehicle’s nearest address. Not only this, we also need to know if the user is at the address.
“Vehicle is 500m from Plant A → Vehicle has reached plant A ”
Often, an account can have more than 10000+ addresses (we provide analytics and automation around addresses, so there is a lot of value here). Couple that with 1000+ vehicles and it means that we end up doing a lot of calculations (repeatedly too!) for basic use-cases. This can cause time delays and cpu issues.
Our initial solution was simple. Iterate over list of vehicles and find distance from all addresses, meanwhile maintaining a minimum distance variable. Simple, 100% accurate and honestly, if the count of vehicles and addresses is manageable, not a problem. BUT, perf matters. At medium scale (900 vehicles and 5000 addresses) our most go to function, filterRealtimeVehicle took more than 8 secs. We needed to optimise and the solution was (drumrolls) Quadtree.
After using Quadtree, time taken by filterRealtimeVehicle reduced from 8 secs to sub 1 sec
The Solution:
Quadtree data structure is a tree(of-course) in which every node has four children. Think of this as a x-y graph with four quadrants. All points are mapped to a quadrant, depending on their (x,y) position.Also, every quadrant has a capacity. If the capacity is met the quadrant breaks into four more children. This would look like this:
[Image from: https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374]
Representing latitudes and longitudes on a quad tree or how to represent all of the earth on a 2d x-y graph(a MAP!):
Latitudes range from -90 to 90 and longitudes range from -180 to 180. Which means that if we have a tree of width 180 and height 360, there is a place for every (lat,lng) on our mini rectangular earth.
We will normalise latitudes by adding 90 to latitude and 180 to longitude so that our graph starts from (0,0)[which would be (-90°, -180°) on a real map, South Pole].
Lets try to place latitudes and longitudes from 5 states of India on a quadtree.
On adding Kerala, Gujarat, West Bengal, Himachal pradesh, to our quadtreelooks like this:
It has a depth of 1 and has a total of 4 nodes.
Our Quadtree nodes have a capacity of 4. Now, when we will add the 5th state Uttar Pradesh, it will cause quadtree to split.
Our quadtree now has a depth of 3 and has a total of 12 nodes. [Note, since the points were close together, the quadtree split twice here, as the node generated after the first split still had 5 points].
So, you see this way we will be able to represent all known addresses of our client on our quadtree.
[ We can represent India on a quadtree more efficiently, if we create a quadtree keeping in mind India’s latitude and longitude range and accordingly setting width and height. Above quadtree is simplified for understanding purposes]
Finding list of nearest addresses from our quadtree.
To understand this, we need to revisit the width of our quadtree. The width of our quadtree was 180. So, x=0 was latitude -90° and x=1 was latitude -89°. Which means a width of 1, is equal to 1°, which is roughly 111kms.So, our points with width 0.01 are actually circular areas with a radius of ~1.11km (You can alter these accordingly).
Lets say, the below quadtree is all the known addresses of an account:
Now, imagine throwing a disk on the lower quadrant of our quadtree. All the addresses that the disk falls on are the nearest addresses in that range. Remember, our points were circular areas of ~ 1.11 kms and if we set width and height as 1 for our vehicle disk, it would fetch us all the addresses in that 111 km radius. These become our candidate nearest addresses. Then, we can iterate over these ‘candidate’ nearest addresses and find the one which is nearest to our vehicles lat-long.
Performance wise, finding candidate nearest addresses is a function of the depth of the Quadtree. When we checked our filterRealtimeVehicle, it went down from 8s to sub 1s.
Sources:
