Pablo Garcia

Apps for iPhone, iPad, Apple TV and Apple Watch

# Quadtree and Map Clustering - II

Feb 6, 2019

In the previous post we viewed how to build a QuadTree, now we are going to do the real magic...

## Clustering

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, i.e. distance) to each other than to those in other groups (clusters). We’ll need to find all the points which lie in different regions of the map to create groups of points.

``````

struct ClusterPoint {
let origin: CGPoint
let points: Int
}

class PGClusteringManager {

private let boxWidth = CGFloat(5.0)
private let boxHeight = CGFloat(10.0)

}

public func clusterAnnotationsWithinRectangle(rectangle: CGRect) -> [ClusterPoint] {

var clusters = [ClusterPoint]()

let boxArea = calculateBoxAreaSize(size: rectangle.size)
var xCoordinate = rectangle.origin.x
var yCoordinate = rectangle.origin.y

while yCoordinate<rectangle.size.height {
xCoordinate = rectangle.origin.x
while xCoordinate<rectangle.size.width {
let boundingBox = CGRect(x: xCoordinate, y: yCoordinate, width: boxArea.width, height: boxArea.height)
if points.count != 0 {
var totalX = CGFloat(0)
var totalY = CGFloat(0)

for point in points {
totalX += point.x
totalY += point.y
}
let totalPoints = CGFloat(points.count)
clusters.append(ClusterPoint(origin: CGPoint(x: totalX/totalPoints,
y: totalY/totalPoints),
points: points.count))
}
}
xCoordinate += boxArea.width
}
yCoordinate += boxArea.height
}

return clusters
}

private func calculateBoxAreaSize(size: CGSize) -> CGSize {

let width = size.width/boxWidth
let height = size.height/boxHeight

return CGSize(width: width, height: height)

}

}

``````

After insert all data in the QuadTree and calling the clusterAnnotationsWithinRectangle function, we'll get something like this: Awesome!! And now, we are going to check that everything is ok. In the next gift we can see all the points and cluster with their bounding box. 