У меня имеется несколько тысяч точек на двумерной плоскости (обычная метрическая плоскость, конкретно - географическая карта). Распределение сильно неравномерное, точки плотно кучкуются, это видно глазом. Мне нужно не вываливать пользователю все точки, а представить этот набор в виде кластеров на карте с какой-то характерной длиной усреднения R. Т.е., скажем, если две точки ближе друг к другу, чем R, то они входят в один кластер. Условие это не строгое, т.е. мне подойдет любой алгоритм, который просто даст на выходе визуально приемлемую группировку.
Сейчас я просто бью плоскость грубой координатной сеткой с шагом R и кластером считаю все, что попало в одну ячейку. Это очень дешево в плане скорости, но и очень сердито в плане качества (скажем, явно выраженный кластер запросто может попасть на границу ячеек). Но проблема в том, что любой более навороченный алгоритм (из тех, что я нашел) сразу требует порядка N2 сравнений, а это для расчетов в реальном времени многовато. Карта может масштабироваться, условия выборки точек могут меняться, так что посчитать кластеры по 'долгому' алгоритму и закэшировать я не могу: ну, точнее, это будет сложно.
Может быть, существуют какие-то более дешевые решения, чем N2?
отредактировано 10.10.2006 17:31 |
» Общий форум