Clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters). It is a main task of exploratory data mining, and a common technique for statistical data analysis, used in many fields.
In the following example, we will reduce the number of markers on a map. This not only boosts performance (in regards to cesium’s rendering cycle) and reduces the amount of visual clutter. The higher the zoom, the bigger the detail and vice versa.
In this example I will show:
- The clustering algorithm.
- The algorithm of creating a polygon from locations – a.k.a. a convex hull.
The clustering algorithm demo:
The clustering algorithm demo receives 3 parameters as a user input:
Entity types – defines number of groups. These aren’t the actual clusters – these are groups in the sense of types of restaurants for instance.
Entities Per Type – defines the number of entities (locations) in each type/group.
Clustering Radius (px)- defines the maximum constant distance in pixels between a center of a cluster to locations that to be considered in the cluster.
In the beginning, the app creates entities, and adds them to the viewer’s entityCollection. Each entity has a property defining which group it belongs to.
In each change in camera view, the clustering algorithm is used. The algorithm clusters nearby locations from the same type, by calculating the distance between them in pixels.
Now to the algorithm. Let’s define the distance between two points on the map.
The distance:
There are 2 methods to define a location on the map.
- Location in pixels – point(x,y).
- Location in degrees – converted into Cesium.Cartesian3(longitude, latitude).
Cesium’s API allows us to calculate the distance between two points in kilometers (km):
var distanceInKilometers = Cesium.Cartesian3.distance(point1, point2);
In order to convert km to pixels, we can convert points in pixels to Cartesian locations (using the pickEllipsoid method of the camera), and then get the km-pixels ratio (since we know both distances).
Now we can easily calculate the pixels distance between 2 points on the map.
The algorithm
- Divide entities to groups.
- For each group do:
- For each entity do:
- If fits to an existing cluster (falls within the minimal distance):
- Insert the entity’s location to the cluster
- else
- Create a new cluster with the entity’s location as its center and add the entity into this new cluster.
- Set original entity’s “show” attribute to “false”
- If fits to an existing cluster (falls within the minimal distance):
- For each entity do:
After all the clusters are complete, we set each cluster’s position as the center of all the points in it.
Each group gets a random color in this demo.
This step is done with each camera “moveEnd” event, hence changing our clutters according to what is seen in the current viewing rectangle.
Creating the convex hull
When hovering over a cluster, a polygon appears. This polygon shows the borders of the cluster, and is made of the positions that are farther away from the center.
Drawing the polygon calculated by the convex hull algorithm.
Live sample here: http://biksapps.com/racheli/cesium_cluster/dist/#/
The code is also available here with a few changes and improvements:
- No convex hull (yet)
- Fully tested (jasmin+karma)
- Still in development
- Built as an angular module