ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Andrianov                     2:5020/1507.400 28 Aug 2002  07:02:04
 To : Alexandr A. Redchuck
 Subject : Re: Сортировка    комплексных    чисел?
 -------------------------------------------------------------------------------- 
 

 
 Однажды 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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Сортировка комплексных чисел?   Alexandr A. Redchuck   24 Aug 2002 01:43:03   Re: Сортировка комплексных чисел?   Sergey Andrianov   28 Aug 2002 07:02:04