Проредить точки на плоскости, в соответствии с заданным максимальным расстоянием

Здравствуйте! Не могу додуматься, как наиболее оптимально решить задачу: задано множество точек на плоскости, точки распределены неравномерно (густота точек в различных частях плоскости разная). Требуется наиболее оптимальным способом найти подмножество этих точек, такое, чтобы минимальное расстояние между любыми двумя соседними точками было не меньше заданного. Такое подмножество не единственно, нужно найти только одно, любое. Мне приходят в голову очень не оптимальные решения. Точек может быть больше миллиона, поэтому и требуется скорость. Не плохо бы, если можно было бы находить такое множество за время меньше секунды, если это реально.

0

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

Я полагаю, что вам все таки нужно сохранить какие-то (условно максимальное) количество точек. Итак, если нужно найти любое решение, "разумно" удовлетворяющее условию, то стратегия тут очевидна: берем первую (любую) точку, и уничтожаем все другие точки, попавшие внутрь заданного радиуса от исходной. Берем следующую точку (любую из оставшихся) и повторяем процесс. И т.д.

Тут, конечно, возникает задача поиска точек, попавших в круг. Чтобы решить ее максимально эффективно, необходимо строить довольно хитрые структуры данных (k-d деревья, quad деревья и т.п.), помогающие делать эффективный поиск точек в ограниченном радиусе. Но я не знаю, нужны ли это вам все эти сложности. Скорее всего нет.

Вы можете просто предварительно разбить плоскость на прямоугольные ячейки с шагом в ваш радиус (как клетчатая бумага), или лучше даже с меньшим шагом, и предварительно разбросать ваши точки по этим ячейкам. Зная, какие точки принадлежат каждой ячейке можно довольно эффективно ограничивать поиск, т.е. мгновенно распознавать и удалять точки, заведомо лежащие внутри радиуса, и мгновенно исключать из рассмотрения те точки, которые заведомо лежат за пределами радиуса.

2

Да, вы правы, поставил задачу не так, как нужно, но вы правильно поняли, что я хочу. Идея, насчет удаления точек, попадающих в окружность с центром в каждой точке и размером с нужный радиус приходила, но моего опыта не хватает, чтобы быть уверенным, что это будет работать за время не большее секунды. Тут же, мне видится, массивами обойтись трудно, придется искать контейнеры, с возможностью удаления произвольного элемента, а контейнеры относительно медленные. Кстати, а можно поподробнее насчет сетки? Допустим, задали сетку, разве прорежение будет эффективнее, чем без нее?
P.S. А неоднозначность, которая имелась ввиду, заключалась в том, что, если мы применим описанный Вами алгоритм, начиная с различных точек, то результат будет различен, и мне не важно, какой именно, главное, чтобы быстро.

Добавлено через 19 минут
Правильно ли я понимаю, что для хранения точек лучше использовать массив массивов, причем каждый массив в данном массиве - точка и состоит из двух элементов (x,y). А чтобы не использовать контейнеры, создать еще массив типа bool, в котором будет описываться принадлежность точек с данным порядковым номером к новому, прореженному множеству?

0

Сетка поможет в том плане что при анализе вы сможете перебирать не все точки а только точки из одной или смежных ячеек

0

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

0

Павлушечка, Пусть N число точек. Выберем число ячеек M, например M пропорционально N.
Тогда разбиение массива точек на M массивов - сложность линейная.
Определение ближайших - сложность O(N*N/M)=(т.к. N/M=const)=O(N) - линейная.
А если не разбивать - каждую точку сравниваем с каждой - сложность квадратичная.

1

Сообщение от Павлушечка Ведь придется рассчитывать дополнительно, какие точки принадлежат данной ячейке.

А без этого вы никак не обойдетесь.

Базовый факт тут таков: чтобы решить эту задачу эффективно, вам придется выполнить препроцессинг ваших данных. То есть еще до того, как вы займетесь собственно обработкой точек, вам надо будет организовать эти точки в некую эффективную структуру данных, которая поможет вам выполнить удаление. На эту организацию точек придется потратить время, именно до начала собственно решения задачи.

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

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

И еще раз: без препроцессинга точек решить эту задачу эффективно никаких шансов нет.

(Другое дело, если ваши точки с самого начала приходят к вам не свалкой, а уже организованными в некую эффективную структуру данных. Но вы нам ничего такого не говорили, а телепатов тут нет.)

1

Если сетка 100 на 100 а точек 1 млн то в одной ячейке 100 точек - пробежать по ним легче чем по всему млн

1

Сообщение от avgoor Павлушечка, Пусть N число точек. Выберем число ячеек M, например M пропорционально N. Тогда разбиение массива точек на M массивов - сложность линейная. Определение ближайших - сложность O(N*N/M)=(т.к. N/M=const)=O(N) - линейная. А если не разбивать - каждую точку сравниваем с каждой - сложность квадратичная.

О, спасибо, теперь ясно.

Сообщение от TheCalligrapher (Другое дело, если ваши точки с самого начала приходят к вам не свалкой, а уже организованными в некую эффективную структуру данных. Но вы нам ничего такого не говорили, а телепатов тут нет.)

Точки приходят свалкой (изредка - нет).

Сообщение от TheCalligrapher И еще раз: без препроцессинга точек решить эту задачу эффективно никаких шансов нет.

Хорошо, спасибо, сделаю, как сказали.

0