Se você estiver procurando por um algoritmo de aproximação, sugiro procurar um algoritmo k-means ou um cluster hierárquico, especialmente uma curva de monstro ou uma curva de preenchimento de espaço. Primeiro, você pode calcular uma árvore geradora mínima do grafo e, em seguida, remover as arestas mais longas e mais caras. Então a árvore faz muitas pequenas árvores e você pode usar o k-means para calcular o grupo de pontos, ou seja, clusters.

"O algoritmo de k-clustering de link único ... é precisamente o algoritmo de Kruskal ... equivalente a encontrar um MST e excluir as k-1 arestas mais caras." Veja por exemplo aqui:https://stats.stackexchange.com/ perguntas/1475/visualization-software-for-clustering .

Um bom exemplo de curva de monstro é a curva de Hilbert. A forma básica desta curva é uma forma de U e copiando muitas delas juntas e girando-a, a curva preenche o espaço euklidiano. Surpreendentemente, um código cinza pode ajudar a descobrir a orientação dessa forma em U. Você pode procurar a curva de hilbert quadtree do índice espacial de Nick artigo do blog sobre mais detalhes . Em vez de calcular o índice da curva, você pode montar um quadkey como nos mapas do bing. A quadkey é única para cada coordenada e pode ser usada com operações normais de string. Cada posição na chave faz parte da curva em forma de U e, portanto, você pode selecionar essa região de pontos de selecionar parcialmente da esquerda para a direita a partir da tecla quádrupla.

Nesta imagem você pode ver que o polígono verde é encontrado usando uma curva de Hilbert:



Você pode encontrar minhas aulas de php aqui:http://www.phpclasses.org/package/6202-PHP-Generate-points-of-an-Hilbert-curve.html