Re: Сортировка комплексных чисел?

From

Sergey Andrianov (2:5020/1507.400)

To

Alexandr A. Redchuck

Date

2002-08-28T07:02:04Z

Area

RU.ALGORITHMS

Здравствуй, Alexandr!

Однажды 24-Aug-02  в 01:43   Alexandr A. Redchuck (via gate)
написал       Sergey Andrianov    по поводу
-=-   Re: Сортировка    комплексных    чисел?  -=-


AAR>>>>> квадрату массиве (а вот тут и перекрытия понадобились, иначе оказалось
AAR>>>>> бы, что для точки на краю квадрата "истинно" ближайшая может оказаться 
AAR> в
AAR>>>>> другом квадрате).
SA>>>>  Правильно, но после того, как нашли ближайшую точку в своем квадрате
SA>>>> (повторяю, квадраты без перекрытий), сравниваем расстояние до нее с
SA>>>> расстояниями до сторон и углов квадрата (несколько раз можно взять и
SA>>>> корень).
SA>>>> По результатам сравнения в список проверяемых может добавиться до 3-х
SA>>>> дополнительных квадратов (при условии, что в каждом квадрате имеется
AAR> [^Y]
AAR>>> Мне навскидку тяжело сказать - как лучше. Если возможен вариант,
AAR>>> что в "квадрате" точек нет совсем, то может лучше проверить при нужде
AAR>>> соседние квадраты. Если они гарантированно есть и "не одна", то лучше
AAR>>> проверить некий слой вокруг квадрата (перекртыия), чем проверять
AAR>>> весь квадрат.
AAR> Точнее, чем проверять кучу соседних квадратов.
AAR> Тут все от статистики зависит и от размера квадратов.
AAR> Если перекрытий нет и могут быть [почти] пустые квадраты, то просто
AAR> надо проверять соседние квадраты. Kстати, кто сказал, что "до 3-х"?
AAR> |     *|*     |   Если в каждом квадрате имеется, как ты говоришь,
AAR> -+-+--+-+-+--+-+  минимум одна точка, то проверить придется не три
AAR> |o     |     o|  соседних, может придется до 7 (т.е. не надо всего
AAR> |      |      |  один)
AAR> *|     x|      |   o и * - "опорные" точки.
AAR> -+-+--+-+-+--+-+   x - это сюда попала точка из "экспериментального"
AAR> *|      |      |   набора.
AAR> |      |      |     Растояния (x-o) близки к диагонали квадрата,
AAR> |o     |     o|   а расстояния (x-*) - к его ребру. Т.е.
AAR> -+-+--+-+-+--+-+   точки * окажутся _ближе_, но ты их не проверишь
AAR> по "трем соседним квадратам". А если проверять все семь, то чем это
AAR> отличается от моих "перекрытий" для предельного случая, когда
AAR> размер перекрытия равен размеру квадрата (кроме сильного роста
AAR> занимаемой памяти у меня)?

   Сейчас уже не припомню, что именно называется перекрытиями, но равномерная сетка предпочтительнее перекрытий минимум по одному из двух пунктов:
   1. Время вычисления нужной ячейки в сетке О(1), а для перекрытия, возможно, больше.
   2. Сетка потребует меньше дополнительной памяти.
   А по поводу 3 ячеек я, возможно, поспешил. Помню рассматривал похожую задачу для collision detection. Там если объект А столкнулся с объектом В, то ненужно проверять столкновение объекта В с объектом А. Здесь же, если ближайшая к А будет точка В, то может найтись точка С, которая расположена к В ближе, чем А. Так что на 3 не настаиваю. Возможно, даже их будет 8, а не 7.



                  До свидания,  в  06:50 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)