Удалить ближайших

[Igors]

Добрый день

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

Спасибо

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

[Racheengel]

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

[Igors]

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

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

[Bepec]

update: чуть вник.

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

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

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

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

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

[Akon]

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

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

[Igors]

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

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

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

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

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

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

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

[Serr500]

Ну тогда может есть в 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;
}

[Igors]

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

Код:

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 (хотя это неважно)

[Akon]

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

[Igors]

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

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

[Serr500]

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

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

[Igors]

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

Вы правы

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

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

[Serr500]

Насколько я понял, точки находятся на плоскости, т.е. имеют две координаты - x,y. По какой формуле вычисляется расстояние между точками?

[Serr500]

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

Код:

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.

[Igors]

Код:

(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)) 

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