Поиск точки

← →
Дмитрий С © (2009-06-24 08:00) [0]

Есть таблица точек в mysql: `points`, в ней, помимо прочих, два поля `x` и `y`.
К примеру, в таблице порядка 100000 записей.
Задача состоит в том, чтобы максимально быстро найти координаты такой точки, которая находится не ближе чем Rmin и не дальше чем Rmax к любой любой существующей в таблице точке.
Какие будут мысли?

← →
Дмитрий С © (2009-06-24 08:05) [1]

Хочу добавить.
Разумеется таких точек будет великое множество. Нужно найти максимально случайным образом.

Конечно можно, к примеру, найти самую правую точку, и взять искомую такой (`x`+Rmin+1, `y`). Такое решение недопустимо, к сожалению.

← →
MBo © (2009-06-24 08:32) [2]

>Разумеется таких точек будет великое множество
В общем случае - не факт. Таких точек вообще не быть при узком диапазоне rmin-rmax.
Но, конечно, если диапазон соответствует набору, другое дело.

Навскидку видно квадратичное решение (O(N^2)).
Для каждой точки массива (списка) проходим в цикле по точкам с большим индексом.
Если какая-то пара точек выходит за диапазон, удаляем эту пару.
В конце концов останутся точки, удоалетворяющие условию

← →
MBo © (2009-06-24 08:37) [3]

пардон, удалять точки нельзя, нужно только помечать первую из них, как "плохую" и сразу переходить к следующей.

← →
test © (2009-06-24 08:43) [4]

Проиндексуируй оба поля в таблице.

← →
AndreyV © (2009-06-24 08:48) [5]

> [2] MBo © (24.06.09 08:32)

У него БД, не забываем. И автор не уточнил что есть R.

← →
MBo © (2009-06-24 09:42) [6]

Кстати, если набор данных статический, и многократно меняются Rmin и RMax, то есть и другое решение.

← →
Вариант (2009-06-24 10:10) [7]

Запрос? Тогда предложу следующий вариант

Пусть Rmin и Rmax соотвественно заданные ограничения (передается параметрами), а Points имя таблицы - тогда SQL запрос имеет вид

select t1.x,t1.y from Points t1
where not exists (select t2.x,t2.y from Points t2 where (t1.x <> t2.x or t1.y <> t2.y) and
((t1.x-t2.x)*(t1.x-t2.x)+ (t1.y-t2.y)*(t1.y-t2.y)) not between (:Rmin*:Rmin) and (:Rmax*:Rmax))

(Так как не знаю какие мат функции поддерживает MySQL, заменил квадрат операциями умножения ).

Где условие (t1.x <> t2.x or t1.y <> t2.y) исключает сравнение точки самой с собой( при наличии ID записи, характеризующую точку и уникальности пар x и у лучше будет использовать для этого исключение записи по ID). Оптимизировать -посмотри план запроса, может что и подскажет.

← →
palva © (2009-06-24 10:13) [8]

Надо бы попросить автора уточнить формулировку.

> не ближе чем Rmin и не дальше чем Rmax к любой любой существующей в таблице точке.

Это как понимать? К любой другой? То есть ищем пару точек не слишком близких (Rmin) и не слишком далеких (Rmax), одна из них и будет искомой?

Или просто любой? Тогда задача нерешаема при Rmin>0, поскольку расстояние от точки до себя самой всегда равно нулю. А если Rmin=0, то любая точка будет допустимой.

Или все-таки автор имел в виду "к заданной"? По-моему, все так и поняли. Но у автора явно написано нечто совсем другое. Кроме того, в таком случае становится не понятно, зачем здесь слово существующей.

← →
Вариант (2009-06-24 10:15) [9]

> Дмитрий С © (24.06.09 08:05) [1]

Про
> Нужно найти максимально случайным образом

- из выбранного набора уже выбрать случайно вполне возможнос просто с помощью генератора случайных чисел.

← →
palva © (2009-06-24 10:16) [10]

> По-моему, все так и поняли.

Извиняюсь, это я сначала так понял.

← →
Вариант (2009-06-24 11:11) [11]

Кстати [7] не учитывает возникающие повторные вычисления(правда они будут крутиться на сервере). Что бы исключить повторные вычисления,можно выбрать весь список на клиента и обработать его там, удалять точки по мере расчета удачных точек (одну точку) или если нашлась "плохая" пара -удалять сразу пару и переходить к следующей точке списка. О чем собственно писалось в [2] и в [3]

← →
Дмитрий С © (2009-06-24 11:15) [12]

> MBo © (24.06.09 08:32) [2]

Не совсем понял о чем речь.

> MBo © (24.06.09 09:42) [6]

Набор, как раз динамический. И по этому принципу в него точки и добавляются.
Rmin Rmax - постоянны, причем Rmin достаточно меньше Rmax, точку всегда можно поместить.

> Вариант (24.06.09 10:10) [7]

Дело в том, что простым селектом вряд ли эта задача решается. Координат искомой точки нет в базе. Искомую точку нужно выбрать случайно с соблюдением условий ее расположения.

> palva © (24.06.09 10:13) [8]

Уточню таким образом:
В базе находится множество *существующих* точек. Нужно найти такую точку (x0,y0) (ее нет в базе, найти ее нужно в геометрическом смысле), такую чтобы:
1 условие: она не была слишком близка к любой из *существующих* точек, т.е. для всех точек из базы должно выполняться (x - x0)^2 + (y - y0)^2 > Rmin
2 условие: она не должна быть слишком далека от какой либо *существующей точки*, т.е. должна существовать (быть в базе) хотя бы одна точка, для которой выполнится (x - x0)^2 + (y - y0)^2 < Rmax

Для наглядности я изобразил области из которой нужно случайным образом взять точку желтым цветом:
http://argi.ru/points.png
Синей окружностью обозначен радиус Rmin каждой точки, зеленой - Rmax.
На рисунке 5 точек, в базе их может быть очень много.

Строим диаграмму Вороного (задача, двойственная триангуляции Делоне)
Ее ячейки (выпуклые многоугольники и открытые многоугольники(полилинии) по периметру) окружают каждую точку, причем точки пространства внутри ячейки находятся ближе к центральной точке ячейки, чем к чужим точкам.
Для каждой из ячеек хранится ее максимальный размер (длина перпендикуляра от центральной точки до самой удаленной грани).
Очередную точку можно поставить в любую из ячеек подходящего размера на расстоянии, большем RMin. Если закрытые ячейки малы, ставим точку в открытую (по периметру облака). Перестраиваем диаграмму (для триангуляции это малозатратная операция, для Вороного, полагаю, тоже)

>большем RMin
и меньшем RMax

Поиск точки Найти похожие ветки