Отправляет email-рассылки с помощью сервиса Sendsay
  Все выпуски  

Постановка задачи. Есть множество точек в 2-, 3- и тд.-мерном


Информационный Канал Subscribe.Ru

http://www.mrblack.pp.ru
Приемы и технологии программирования #10

Многомерный поиск

Прошу прощения за долгий перерыв в выпусках рассылки. Сегодня мне хотелось бы рассмотреть интересную, на мой взгляд, проблему поиска объекта в многомерном пространстве.

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

  1. точку из данного множества, ближайшую к заданной
  2. все точки пересечения данного множества и некоторой области

Где это может использоваться.

  1. В играх для рассчета столкновения объекта с чем-либо, прежде всего, следует отыскать поверхность, с которой объект столкнется раньше всего
  2. Для реализации выделения мыщью объектов на карте
  3. В задачах компьютерного моделирования систем, состоящих из большого количства частиц, можно значительно ускорить вычисления, учитываю не все взаимодействия, а только взаимодействия частицы с N ближайщими соседями

До сих пор я не находил в интернете ни одного решения описанной выше задачи. Существование игр с реализацией столкновений многих объектов друг с другом доказывает, что их разработчики эту задачу решили, однако в свободном доступе я пока не видел ни одного готового решения в исходниках или хотя бы описания алгоритма. Так что я занялся разработкой своих решений.

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

Описание алгоритма

Пусть все точки множества имеют координаты от 0 до 1. Умножим их на 2^N и запишем целые части этих чисел в двоичном виде:

 X = {x(N),x(N-1)...x(1),x(0)}
 y = {y(N),y(N-1)...y(1),y(0)}

(Здесь и далее будем рассматривать двумерный случай)

Теперь составим из этив битов такую последовательность:

 i = {x(N),y(N),x(N-1),y(N-1)...x(1),y(1),x(0),y(0)}

Упорядочим точки по этому значению. Вот как будет выгладеть расстановка значений i на проскости:

014516172021
236718192223
89121324252829
1011141526273031
3233363748495253
3435383950515455
4041444556576061
4243464758596263

Отсюда видно, что исходный квадрат разделен на 4 части, и по номерам сначала идут точки одного квадрата, затем другого и тд. Каждый из этих квадратов, в свою очередь, разделен аналогичным образом. Такая вот иерархическая структура. Для любого квадрата любого уровня можно за логарифмическое время найти указатели на первую и последнюю точки квадрата путем обыкновенного одномерного поиска делением пополам. Теперь мы можем попытаться указать такой квадрат, в котором наверняка находится искомая точка, а затем перебрать все точки этого квадрата. Понятно, что время поиска зависит только от количества этих точек, тоесть от размера квадрата.

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

Вся фишка в том, что кавдрат этот не всегда будет иметь размер порядка расстояния OA. Если точка O имеет координаты (4.99;4.99), а А(5.01;5.01), то придется перебирать абсолютно все точки, и ничего ускорить не получится. Однако, можно показать, что при равномерном распределении точек из множества, в котором осуществляется поиск, по области допустимых значений и равномерном распределении целевых точек большие размеры квадратов будут менее вероятны, чем малые.

Итого, время поиска выражается так:

 t = O(log(N)) + O(M),

Где M - переменная величина со следующим распределением вероятности:

 p(M) = 2^(-M)

Во вложении программа-пример. Программа случайно генерирует некоторое количество точек. По щелчку мыши программа находит точку, ближайшую к указанной и помечает ее, а также выводит количество точек, перебранных в процессе поиска. Я впервые использую функцию вложения файлов в рассылку, так что не судите строго, если вложение не получится открыть. В этом случае качайте файл с веба: http://mrblack.pp.ru/attach/multidim_search.rar

Если вы знаете другие решения этой задачи, прошу вас написать о них или хотя бы ссылку прислать. Если вы сталкивались подобной проблемой, мне и читателям будет интересно узнать и вашей работе. Если вы просто интересуетесь информационными технологиями, хотелось бы прочитать ваше мнение. Мой адрес mrblack@pochta.ws

В следующем выпуске я обязательно рассмотрю вторую часть задачи и опубликую ваши письма.

_

2005-11-24

mr. Black <mrblack@pochta.ws>
Аська: 179497623
Сайт: http://www.mrblack.pp.ru/
Программа "Simple RAS Dialer"
Статьи о технологиях программирования

Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора
Подписан адрес:
Код этой рассылки: comp.soft.prog.techn
Архив рассылки
Отписаться
Вспомнить пароль

В избранное