| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Группировка точек на пл-ти по близости друг другу |
| Автор: Liner 26.3.2006, 20:15 |
| Есть точки на плоскости и число R, задавемое пользователем. Нужно объединить точки, которые ближе друг к другу, чем R, в группы. Проще по рисунку: (если он не работает, то ссылка http://mike234.narod.ru/index3.html)  Напрямую ясно как*, но очень медленно. Есть ли хитрые быстрые способы? Спасибо. *Я делаю примерно так: 1. сначала столько же групп, сколько точек, в каждой по одной точке; 2. взять очередную группу, проверить "пересекается" ли она с какой-нибудь другой, если да, объеденить их; 3. повторять 2. до последней группы. |
| Автор: Akina 27.3.2006, 08:33 |
| Влоб - построить матрицу расстояний (читай - связности) и разделить ее на подгруппы. Ведь если задано R, то расстояние <2R. O(N^2). |
| Автор: Liner 27.3.2006, 15:26 |
Т.е. быстрее N^2 нельзя? На десятках тысяч точек притормаживает  |
| Автор: Earnest 28.3.2006, 19:10 |
| Можно попробовать построить алгоритм на основе сканирующей линии: начало как у тебя (каждая точка = кластер), отсортировать точки по x. Потом заводим сканирующую линию = вертикальная полоса: левая граница проходит через самую левую точку, правая - на расстоянии R. Активными считаются кластеры, пересекающие полосу. На каждом шаге проверяем (сравниваем, объединяем) только активные кластеры. Потом переносим линию на следующую точку, обновляем список активных кластеров и снова проверяем. Если R по сравнению с размером области невелико, ИМХО должно помочь. Операция проверки кластеров на "близость" все же вызывает сомнения. Можно попробовать сначала построить граф из точек, где дуга создается, если точки ближе, чем R. Это тоже сканирующей линией. А потом - найти связные компоненты. Естественно, граф строить реально не надо, нам ведь нужны только пары близких точек, которые сразу после обнаружения можно подавать на вход алгоритма поиска связности. Задача связности шикарно описана у Седжвика (Фундаментальные алгоритмы) в первой главе. |