Печать страницы - Удалить ближайших

Добрый день

Есть массив точек (int x, y), нужно удалить некоторые так чтобы расстояние между любыми двумя из оставшихся ~~не превышало~~ было НЕ МЕНЬШЕ заданного (D). Нет ли дешевого/стандартного способа это сделать (напр в STL)?

Спасибо

Edit: извиняюсь, описАлся, правильно "не меньше заданного" (т.е. прореживание)

Цитата: Racheengel от Май 31, 2012, 21:59

наверное, нету, придется эти 10 строчек вручную писать :(
а STL вообще бесполезен, когда есть Qt :)

Ну тогда может есть в Qt? И что-то у меня получается намного больше 100 строк (не говоря уже о 10) :'(

update: чуть вник.

А в чём проблема то?

Вроде (неуверен), если брать элемент, проверять все остальные на промежуток между ним. Не входящие удалять. Следующий элемент и цикл погнали.

Вопрос - а дополнительных условий нет? К примеру на количество оставшихся?

Потому что вроде самое простое - если первая точка не сходится хоть с одной точкой, значит её надо удалять(первую точку). Если хоть 1 точка с ней сходится - надо удалять остальные не входящие в радиус.

PS Тут вопрос уже, что таких массивов может быть несколько на плоскости. А так, без дополнительных условий всё просто.

Другими словами - на плоскости кругом диаметра D нужно накрыть точки, непокрытые точки удалить. Так? В общем случае решений то много, и нужны доп условия, например, максимизировать количество накрытых точек.

Примитивный вариант - чесать циклом все точки и найти максимальную плотность. А вот если имеется какая-нибудь закономерность в распределении точек по плоскости - то будет задача поиска экстремума (методы решения - от градиентного поиска до всяких там генетических алгоритмов).

Цитата: Bepec от Июнь 01, 2012, 15:01

А в чём проблема то?

Вроде (неуверен), если брать элемент, проверять все остальные на промежуток между ним. Не входящие удалять. Следующий элемент и цикл погнали.

Так а сколько времени это будет работать напр на 100k точек?

Цитата: Bepec от Июнь 01, 2012, 15:01

Вопрос - а дополнительных условий нет? К примеру на количество оставшихся?

Можно сказать что нет. Понятно что если точка не была близка с никакой доугой - то нечего ее было удалять. А так никакого "оптимального" удаления не ищется - любое разумное

Цитата: Akon от Июнь 01, 2012, 18:06

Другими словами - на плоскости кругом диаметра D нужно накрыть точки, непокрытые точки удалить. Так?

Нет, наоборот :) Это я оговорился, виноват, подправил (см первый пост)

Цитата: Igors от Июнь 01, 2012, 14:52

Ну тогда может есть в Qt? И что-то у меня получается намного больше 100 строк (не говоря уже о 10) :'(

А чего так много-то?

Код:

typedef Point;  // точка
int rho(Point x, Point y);  // расстояние между точками
const int D; // радиус прореживания

QVector<Point> Points;
QVector::iterator I = Points.begin();
while (I != Points.end()) {
    QVector::iterator J = I + 1;
    while (J != Points.end()) {
        if (rho(*I, *J) > D)
            J = Points.erase(J);
        else 
            ++J;
    }
    if (I != Points.end())
        ++I;
}

Цитата: Serr500 от Июнь 01, 2012, 21:10

А чего так много-то?

Код:

typedef Point;  // точка
int rho(Point x, Point y);  // расстояние между точками
const int D; // радиус прореживания

QVector<Point> Points;
QVector::iterator I = Points.begin();
while (I != Points.end()) {
..

Это вариант Вереса только еще хуже т.к. erase - дорогая операция. Ну и с QVector вылетит - его итератор становится невалидным после erase (хотя это неважно)

Наложить на плоскость регулярную решетку, точки, покрытые решеткой удалить, в неплотностях решетки может оказаться >1 точки, поэтому вторым проходом оставляем только одну любую точку в каждой неплотности.

Цитата: Akon от Июнь 01, 2012, 22:40

А что это за "неплотности" такие? Расскажите подробнее, лучше с псевдокодом

Цитата: Igors от Июнь 01, 2012, 21:54

Почему это он невалидный? erase() вернёт следующий валидный итератор, который мы и присвоим J. Итератор I останется валидным, поскольку все J "дальше" чем I.
По поводу дороговизны erase полностью согласен. Если нужно быстрее, то можно метить элементы для удаления каким-нибудь явно недопустимым значением, после прохода всех циклов создать пустой массив и перекопировать в него оставшиеся элементы.

Цитата: Serr500 от Июнь 02, 2012, 10:34

Почему это он невалидный? erase() вернёт следующий валидный итератор, который мы и присвоим J. Итератор I останется валидным, поскольку все J "дальше" чем I.

Вы правы

Цитата: Serr500 от Июнь 02, 2012, 10:34

По поводу дороговизны erase полностью согласен. Если нужно быстрее, то можно метить элементы для удаления каким-нибудь явно недопустимым значением, после прохода всех циклов создать пустой массив и перекопировать в него оставшиеся элементы.

Копировать необязательно, можно напр remove_if. Но это не решает главной проблемы - перебор "каждый с каждым" может работать часами

Если используется евклидова метрика на плоскости

Код:

rho((x1,y2), (x2,y2)) = sqrt((x1-x2)^2+(y1-y2)^2)

то можно вначале "проредить" массив. Выкинуть те точки, у которых

Код:

(abs(x1-x2) < D/sqrt(2)) or (abs(y1-y2) < D/sqrt(2))

То есть строим как и выше два цикла, но вместо дорогого вычисления расстояния используем более дешёвое вычитание. Потом по оставшимся точкам пробегаем также в двух циклах, но уже используем точную метрику rho.

Цитата: Serr500 от Июнь 02, 2012, 11:22

Код:

(abs(x1-x2) < D/sqrt(2)) or (abs(y1-y2) < D/sqrt(2))

Ну что же так - куча call'ов. Лучше так

Код:

qreal D2 = D * D;
...
if ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) < D2))

Но принципиально это ничего не меняет - число переборов слишком велико. Заметим что если бы вместо "точек" были "числа" (одномерный случай) - то никаких проблем бы не было.

Я могу ошибаться, но возможно подойдут вот эти ребята:
1) Spatial database (http://en.wikipedia.org/wiki/Spatial_database#Spatial_Index)
2) K-D-tree (http://en.wikipedia.org/wiki/K-d_tree)
3) M-tree (http://en.wikipedia.org/wiki/M-tree)
4) Quadtree (http://en.wikipedia.org/wiki/Quadtree)
5) R-tree (http://en.wikipedia.org/wiki/R-tree)

мб M-tree самый правильный. Вот тут java applet с примером есть: http://www.cmarschner.net/mtree.html
Я совершенно не разбираюсь в этих алгоритмах, просто однажды просили поискать.

Цитата: ck от Июнь 02, 2012, 13:22

Я могу ошибаться, но возможно подойдут вот эти ребята:

Ребята сильные, но ни один из них не выглядит ни простым ни дешевым для реализации. Плюс смущает одно обстоятельство - нужно ведь просто проредить/отфильтровать (а совсем не весь функционал), хочется обойтись без полномасштабного построения дерева.

В любом случае спасибо за подборочку

Цитата: Igors от Июнь 02, 2012, 17:24

Если просто - то перебор, если быстро, то не просто)
Но я понимаю. Эти алгоритмы не такие простые, для "простой" задачи. Я и сам бы не рвался их использовать, мб как вариант для будущих улучшений.

Цитировать

Берем круг, к нему приставляем еще круг и т.д. по плоскости. Получается решетка, между кругами есть промежутки (неплотности). Коордтнаты центров кругов известны. Алгоритм исключения точек простейший.

Цитата: Akon от Июнь 03, 2012, 16:11

Так что, если "взяли круг" - так уже мы знаем какие точки в него попадут? Или можем это быстро определить? Не вижу каким образом.

Также: если я правильно понял, центры кругов образуют регулярную решетку, и полагается что в 1 круге - не более 1 точки. Тогда 2 близкие точки могут быть в соседних кругах, и одна из них не будет удалена вторым проходом по "неплотностям"

Мб попробовать решение по аналогии с closest pair algorithm?

То есть
1) Делить множество пополам относительно некого pivot (по x-вой координате). Pivot - это то, что в русскоязычной литературе называется компаранд (по ссылке - средняя точка).
2) Рекурсивно вызывать функцию для каждой из двух половинок, где "внизу" дерева рекурсии проверяем расстояние между ними, если оно меньше - удаляем точки (тут h - величина фиксированная нами).
3) Аналогично поменять функцию объединения(split function, по ссылке это стадия объединения), то есть множество C(pi) так же для фиксированного h.

Время работы - это сумма времени работы рекурсивных вызовов + функция объединения.

http://e-maxx.ru/algo/nearest_points

Цитата: Disa от Июнь 09, 2012, 13:16

Мб попробовать решение по аналогии с closest pair algorithm?

То есть

Так я пробовал :) На сильном прореживании (когда расстояние D мало) - все очень прилично, но при бОльших D опять сваливаемся в перебор. В closest pair этой проблемы нет - ищем минимальное, ну D и уменьшается автоматычно

Russian Qt Forum

Программирование => С/C++ => Тема начата: Igors от Май 27, 2012, 13:28