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

From

Alexandr A. Redchuck ()

To

Sergey Andrianov

Date

2002-08-11T00:23:07Z

Area

RU.ALGORITHMS

From: "Alexandr A. Redchuck" <real@real.kiev.ua>

9-Aug-02 23:14 Sergey Andrianov wrote to Alexandr A. Redchuck:
SA> Здравствуй, Alexandr!

AAR>>   т.е. часть опорных точек попадет в 2 или 4 массива (обязательно
AAR>>   нужно!).
SA>        Не нужно (см. ниже)

AAR>> квадрату массиве (а вот тут и перекрытия понадобились, иначе оказалось
AAR>> бы, что для точки на краю квадрата "истинно" ближайшая может оказаться в
AAR>> другом квадрате).
SA>    Правильно, но после того, как нашли ближайшую точку в своем квадрате
SA> (повторяю, квадраты без перекрытий), сравниваем расстояние до нее с
SA> расстояниями до сторон и углов квадрата (несколько раз можно взять и
SA> корень).
SA> По результатам сравнения в список проверяемых может добавиться до 3-х
SA> дополнительных квадратов (при условии, что в каждом квадрате имеется
SA> минимум
SA> одна точка. Если это условие слишком сильное, организуем очередь из
SA> квадратов - кандидатов на рассмотрение, пока не найдем искомую точку.
 Мне навскидку тяжело сказать - как лучше. Если возможен вариант,
что в "квадрате" точек нет совсем, то может лучше проверить при нужде
соседние квадраты. Если они гарантированно есть и "не одна", то лучше
проверить некий слой вокруг квадрата (перекртыия), чем проверять
весь квадрат.
 В любом случае разбиения дадут больше порядка ускорения по сравнению
с единым массивом.

wbr,
--
/* Alexandr Redchuck, Kyiv, Ukraine */
/* real на real тчк kiev тчк ua     */

--- ifmail v.2.15dev5
 * Origin: ReAl at home (2:5020/400)