Ближайшая точка, типа прикладная Опции Рейтинг

[alan]

Представьте, что у вас есть множество А из M точек на плоскости (x_i,y_i). Есть информация о них - по две координаты.

Потом нам дают еще одну точку - B(b_x,b_y). Нужно найти:
а) Точку из множества А ближайшую к B.
б) N ближайших точек к B.
в) Все точки на растоянии меньше чем R от B

Задача - оптимально организовать информацию о точках А. Оптимальность определяется средней скоростью выполнения а), б) или в).

[NLIzer]

Представьте, что у вас есть множество А из M точек на плоскости (x_i,y_i). Есть информация о них - по две координаты.

Потом нам дают еще одну точку - B(b_x,b_y). Нужно найти:
а) Точку из множества А ближайшую к B.
б) N ближайших точек к B.
в) Все точки на растоянии меньше чем R от B

Задача - оптимально организовать информацию о точках А. Оптимальность определяется средней скоростью выполнения а), б) или в).

Первое что приходит на ум, это представление областей, в которых находятся точки, в виде квадрантного дерева. Для точки B определяется квадрант относительно других квадрантов в дереве и далее вычисляются квадранты ближайших точек обходом по дереву. В квадранте ближайших точек вычисляется R для каждой точки в квадранте, ну и т.д.

[alan]

Первое что приходит на ум, это представление областей, в которых находятся точки, в виде квадрантного дерева. Для точки B определяется квадрант относительно других квадрантов в дереве и далее вычисляются квадранты ближайших точек обходом по дереву. В квадранте ближайших точек вычисляется R для каждой точки в квадранте, ну и т.д.

Давай подробнее, пожалуйста А то мало что понял...
1. Что за квадратное дерево? Как его образовывать?
2. Как для В определять квадрант? Что значит определение квадранта Относительно других квадратнов?



П.С. А может еще есть и не первое приходящее на ум?

[NLIzer]

Давай подробнее, пожалуйста А то мало что понял...
1. Что за квадратное дерево? Как его образовывать?
2. Как для В определять квадрант? Что значит определение квадранта Относительно других квадратнов?
П.С. А может еще есть и не первое приходящее на ум?

Все точки А описываются одним квадратом. Этот квадрат делится на 4 равные квадратные части – квадранты, каждый из квадрантов опять делится на 4 части и т.д. Таким образом строится квадрантное дерево, все родительские узлы этого дерева – квадранты, листья дерева – точки или списки точек входящие в родительский квадрант. Для каждого узла дерева вычисляется количество точек содержащиеся в квадранте.
Ну и далее все операции выполняются сначала для квадрантов в которых есть точки, а потом для точек в них.

[alan]

Все точки А описываются одним квадратом. Этот квадрат делится на 4 равные квадратные части – квадранты, каждый из квадрантов опять делится на 4 части и т.д. Таким образом строится квадрантное дерево, все родительские узлы этого дерева – квадранты, листья дерева – точки или списки точек входящие в родительский квадрант. Для каждого узла дерева вычисляется количество точек содержащиеся в квадранте.
Ну и далее все операции выполняются сначала для квадрантов в которых есть точки, а потом для точек в них.

Ого, даже рисунок

А какой в этом смысл? Почему просто не разбить все на D^2 квадратов? Например, так что бы в каждом было или 0 или 1 точка.