Crowded Corners of the Map

A delivery company has plotted its drop-off points on a map and wants to find the crowded areas, without saying in advance how many there are. That is DBSCAN's job. It asks the same question at every point: how many other points lie within $\varepsilon$ of me?

Task: write dbscan_roles(points, eps, min_pts), where points is a list of (x, y) pairs. Return a tuple (roles, clusters):

• roles: one entry per point, in the same order as points, each "core", "border" or "noise";
• clusters: the number of clusters DBSCAN finds.

Use these rules:

• A point's neighbours are the other points at a straight-line distance of at most eps. A distance of exactly eps counts.
• A point is core if it has at least min_pts neighbours. The point itself is not one of its own neighbours.
• A point that is not core is border if at least one of its neighbours is a core point.
• Every other point is noise.
• Clusters grow from core points. Two core points that are neighbours are in the same cluster, and so is every core point reachable from them through a chain of neighbouring core points. A border point joins a cluster but never passes it on: a chain only continues through core points. Noise belongs to no cluster.

scikit-learn's min_samples counts the point itself, so it is always one more than min_pts here. Follow the rules above.