I am trying to create a schematic diagram from a geographical map such that I can somehow avoid dense areas while still trying to maintain the rough "shape" of the pointset. Below is an exemplary pointset (where the GPS coordinates are mapped directly to the position in the diagram) - the coloring is the resut of running the KMeans clustering algorithm: Pointset (coloring due to KMeans). Now my idea is the following:
Compute the voronoi diagram of the centers obtained from the clustering and bound it to a rectangle (e.g., to the boundary of the diagram): Voronoi Diagram of Cluster Centers
Update the cells such that their size is proportional to the number of points of their respective clusters, but the adjacency to other cells is maintained. I got an "average" result by applying a force-directed algorithm on the clustercenters where the repulsion force for every point is proportional to the number of points contained in their cluster.
Finally, once we obtain the final shape of the cell, respace the points inside the cells while somehow maintaing their shape: Respace points inside cell
Again I tried a force-directed approach but did not succeed here.
Any advice for steps 2 & 3 (or other ways to solve this problem) would be appreciated.
Best regards,
MrLemming
Apparently I can not display the images inline since I do not have enough reputation, sorry for the circumstances.
I also tried the fisheye technique to enlarge dense areas but could not really make it work for multiple ones simultaneously.