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

Приемы и технологии программирования

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Программирование на Visual Basic/Visual Studio и ASP/ASP.NET" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Декабрь 2005   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Mr. Black

Статистика

1.464 подписчиков
0 за неделю
←   Все выпуски   →

Приемы и технологии программирования Многомерный поиск (продолжение)


Информационный Канал Subscribe.Ru
http://www.mrblack.pp.ru
Приемы и технологии программирования #12

Многомерный поиск (продолжение)

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

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

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

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

Виртуальные тухлые помидоры

Ilya Y Golberg прислал довольно длинное письмо, смысл которого сводится к тому, что ничего в моей статье не понятно. Приведу некоторые фрагменты этого письма, и буду отвечать по ходу дела.

Извиняй меня убогого, но, по-моему, твоя статья
"Многомерный поиск" http://www.mrblack.pp.ru/index.php/articles/13
нуждается в некоторых пояснениях.

0. Нет четкой постановки задачи(возможны варианты толкования).
Итак, насколько я понял, решается след. задача:
"Для заданного множества точек плоскости {A(i)=(Х(i),Y(i));i=1..N},
и точки O=(X(0),Y(0)) найти i, такое, что расстояние OA(i) - минимальное"

Если я понял неправильно, то дальше модешь не читать, просто
сформулируй, что именно имелось в виду.

Это ты понял абсолютно правильно. А какие еще варианты толкования здесь возможны?

1. "Пусть все точки множества имеют координаты от 0 до 1. Умножим их на
2^N".
Сто точек. Ну и как прикажешь умножать на 2^100? Какой тип
данных пользовать? Понятие "невязка" знакомо?
Главное: почему N умножений не учитываецо в количестве операций? За
2*N умножений и 3*N сложений задача решаеца перебором. Те же O(N)
Откуда береццо число 64???

N здесь - это не количество точек, а произвольное число. Умножение нужно просто для того, чтобы из float сделать int. Если в 32 бита мы хотим впихнуть 2 числа, то на каждое по 16 битов, тогда N = 16. Число 64 просто для примера. Не рисовать же в статье таблицу размером 65536х65536? По поводу O(N), соответствующего полному перебору, то тут я вроде достаточно ясно написал, что мой метод дает статистическое ускорение, т. е. никто не гарантирует, что поиск будет короче полного перебора, но в большинстве случаев он всё же существенно короче.

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

P.S. Извиняй за резкость и сумбурность, ничего личного. Искренне
надеюсь получить ответы. Задачка на самом деле интересна и
нетривиальна. Я бы наверно ковырял ее в сторону замены {X(i),Y(i)} на
m(i)= max{Abs(x(i)-x(0));Abs(y(i)-y(0))}. Т.е. сводил бы к одномерному
случаю при помощи O(N) аддитивных операций. Возможно, далее, поиск минимума в
получившейся последовательности. Далее перебор всех i, таких, что
m(i)<=sqr(2)*min(m(i)).

А я именно с этого и начал, но пока у меня не получается при любых x(0) и y(0) находить такой квадрат.

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

А вот письмо Алексея Вахтина.

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

Это, конечно, другая задача, но по теме, так что приведу важный для нас отрывок этой статьи. Полный текст лежит на сайте автора по адресу http://www.cs.vsu.ru/sbem-contact/papers.php?Id=13

Алгоритм определения пространственного положения узлов основан на методе трассировки лучей [5]. Пусть задана некоторая точка M(Xm,Ym,Zm), для которой необходимо определить пространственное положение относительно поверхности Omega. Пусть n – число пересечений поверхности Omega с выпущенным из M(Xm,Ym,Zm) лучом

l={X=Xm;Y=Ym;Z>=Zm}

Если n четно, то M находится вне области, ограниченной рассматриваемой гранично-элементной сеткой, иначе – внутри.

[ Пропускаю некоторые замечания о реализации алгоритма ]

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

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

Утверждение 2. Если для вершин плоского многоугольника выполняются неравенства

neravenstva

то они выполняются для всех точек данного многоугольника.

[ Пропускаю доказательство ]

Из данного утверждения следует:

Для того, чтобы луч пересекал граничный элемент, необходимо, чтобы для координат точки, из которой выпущен заданный луч выполнялись следующие неравенства:

neravenstva

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

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

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

Таким образом, можно найти такие минимальные и максимальные значения координат, чтобы гранично-элементная сетка была заключена в параллелепипед, представленный в виде неравенств. Полученный параллелепипед можно разделить на Nx Ny Nz равных частей (рис. 6):

Puc. 6a

Puc. 6b

Pис. 6. Разбиение прямоугольного параллелепипеда, охватывающего гранично-элементную сетку, на Nx Ny Nz равных частей.

Каждому множеству узлов, заданных неравенствами можно задать индекс:

indices,

, , , [.] – округление до целого.

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

Используя неравенства и функцию, можно получить индексы множеств точек, для которых существует вероятность пересечения луча с граничным элементом сетки:

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

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

_

2005-12-05

mr. Black <mrblack@pochta.ws>
Аська: 179497623
Сайт: http://www.mrblack.pp.ru/ 		Программа "Simple RAS Dialer"
Статьи о технологиях программирования
Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора 		Подписан адрес:
Код этой рассылки: comp.soft.prog.techn
Архив рассылки 		Отписаться
Вспомнить пароль
В избранное