Parentheticals & Excursions

As I posted yesterday, I needed an algorithm that could paint clusters so as to make them distinguishable from each other. Today, I implemented a simple, “good enough” algorithm.

Inputs and Outputs

The algorithm is fairly general, only requiring that each cluster has:

• has a size — the number of points it contains
• has a radius — gives a general indication of the cluster’s spatial extent
• has a centre — some point indicating the position of the entire cluster

It takes as parameters, a collection of clusters and a list of “paints” and returns a map that assigns every cluster a paint.

Coloring Algorithm

• Order the clusters by the number of points they contain (most populous first)
• For each cluster:
  • compute it’s distance from every other cluster (subtracting their combined radii from the distance between their centres)
• Order these radius-adjusted distances (nearest first)
• Iterate over all the clusters again, for each one:
  • if there is a paint that is not used by any of the other clusters, assign that to the cluster
  • Otherwise assign the most distant paint ie. the last paint used by any other cluster (distance order as above)

Early Results

Here are progressive results over a small dataset using 5 colours.

Even with 200 clusters, this algorithm does a fairly good job at making all the clusters distinguishable using just 5 colours.