What is Clustering?

Have you noticed in a World map, where, markers are used to represent something? The markers when seen at the beginning appear close between two locations and when zoomed in, appears far away. If the cities are too close it can even overlap each other. It will look ugly isn't it?

Clustering is nothing but grouping together two or more nearby markers and show them as one, probably in the middle of the two locations. And when zoomed in, it can be separated and shown as different markers in their respective places.

Sounds simple right! But is it easy to implement? Is there any method to do it in a simple way?

Quadtree and how does it help?

Quadtree is a tree data structure, where each node is divided into four children. It can be visualised using a square cut into four parts. The main square forms the parent and the sub squares form the children.

The Quadtree approach can be used to search for geometric points in a plane accurately and instantly. This comes in handy when we are plotting locations in a map using SVG.

I have added a code pen project to explain how the points are converted to a tree structure in quadtree. Plot the points and notice the tree structure getting updated. When you hover over a point it is highlighted in the tree to understand how the squares are formed.

Implement Clustering

D3 offers an API called Quadtree, which can help to group the markers.

The SVG layout is like a plane in geometry, where the locations are sketched based on x and y values. Now, using quadtree we can determine the locations that fall under the same square. So, the locations that are in the same square can be grouped to show as one. Once we zoom in/out, we can decrease/increase the area of the square to group or un group the locations.

Benefits of using Quadtree in Clustering

• Quadtrees are a way of partitioning space, and hence it is easy to traverse and search.

• Quadtree uses x and y points as in a geometry, that helps achieve clustering in SVG.

• Clustering is offered by many Maps API and Libraries, but we might not get the customisation that we can do using just D3.

We have reached the end of the article. I have attached a blog from where I took my inspiration to go ahead with Quadtree to implement clustering instead of choosing an external library like leafletJS, OpenLayers, MapBox, etc,.

I hope you find this article helpful and informative. If you like this article, give me a thumbs up 👍 Don't forget to bookmark it for future reference 🔖

Thanks for reading 🤓