Coloring close points

I have a dense set of points in the plane. I wa开发者_运维百科nt them colored so that points that are close to each other have the same color, and a different color if they're far away. For simplicity assume that there are, say, 5 different colors to choose from. Turns out I've not the slightest idea how to do that ..

I'm using Tkinter with Python, by the way

If you can use whatever color you want, you can use that fact that colors are (almost) continuous. color the points according to their x,y coordinates, so you'll get as a side effect that close points will have a somewhat similar color.

You can use something like

point.color(R,G,B) = ( point.normalized_x, 0.5, 1-point.normalized.y )

where normalized_x is (x-min_x / (max_x-min_x)), so it would give 0 for the point with minimal x value, and 1 for point with maximal x value.

If you really need to use only a small number of colors and have close point have the exact same color, then you'll have to do some clustering on your data (K-means being a simple and widely used algorithm). After clustering, you just assign each point a color according to its cluster's id. Python has some good implementations, including scipy's clustering.

I'd start with identifying the concentrations of the spots in the plane. Find the centers of those agglomerations and assign them each unique color. Then for other spots you could simply calculate the color using the linear principle. For example, if one center is red and the other is yellow, a point somewhere in the middle would become orange.

I'd probably use some exponential function instead of a linear principle. This will keep the point groups more or less of the same color only giving a noticeable color change to far away points, or, to be more exact, to far away and somewhere in between points.

One approach is to go through your points and partition them into sets with a "center". Since you have 5 colours, you'll have 5 sets. You compare the distance of the new point from each of the centers and then put it in the same group as the closest one.

Each set corresponds to a different colour so you can just plot it after this partitioning is done.

The problem domain is the well-trodden cluster analysis and the Cluster suite with PyCluster is a good start.