Если вы ищете алгоритм аппроксимации, я предлагаю поискать алгоритм k-средних или иерархический кластер, особенно кривую монстров или кривую заполнения пространства. Сначала вы можете вычислить минимальное остовное дерево графа, а затем удалить самые длинные и самые дорогие ребра. Затем дерево создает много маленьких деревьев, и вы можете использовать k-средства для вычисления группы точек, то есть кластеров.
«Алгоритм k-кластеризации в одной линии ... это именно алгоритм Крускала ... эквивалентный поиску MST и удалению k-1 самых дорогих ребер». Смотрите, например, здесь: https://stats.stackexchange.com/questions/1475/visualization-software-for-clustering.
Хорошим примером для кривой монстров является кривая Гильберта. Основной формой этой кривой является U-образная форма, и, скопировав многие из них вместе и вращая ее, кривая заполняет евклидово пространство. Удивительно, но серый код может помочь определить ориентацию этой U-формы. Вы можете найти в блоге пространственного индекса Ника кривую Гильберта более подробную информацию . Вместо этого, чтобы вычислить индекс кривой, вы можете собрать квадрик, как в картах Bing. Quadkey уникален для каждой координаты и может использоваться с обычными строковыми операциями. Каждая позиция в ключе является частью кривой U-образной формы, и, таким образом, вы можете выбрать эту область точек из частично выбранных слева направо от четырехугольника.
На этом изображении зеленый полигон найден с использованием кривой Гильберта:
Вы можете найти мои php классы здесь: http://www.phpclasses.org/package/6202-PHP-Generate-points-of-an-Hilbert-curve.html