Нужна струкнура данных,

← →
Ev_grenus (2002-01-15 17:05) [0]

с подощью которой можно решить такую задачу.
На плоскости координатими заданы точки (много >100000). На каждом шаге точки перемещаются по заданому (для каждой отдельно) вектору (либо стоят на месте). Требуеться быстро определить для заданой точки:
а) ближайшую
б) точки которые находятся на расстоянии, которое меньше заданого R.

ЗЫ: Если каждый раз считать расстояния (n*n операций) то уже на 20000 начинает тормозить.

← →
Digitman (2002-01-15 18:20) [1]

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

← →
Иван Шихалев (2002-01-15 19:03) [2]

Кое-что можно сказать и по структуре:

пусть
type TPoint = record Y :integer; // или что там еще end; TLine = record X :integer; Ys : array of TPoint end; TArray = array of TLine;
Ну и, само собой, добавлять только в нужное место, а проверять методом вилки. Так будет все-таки оптимальней, чем просто отсортированный массив (по обеим координатам логарифмическое время).

← →
Фе (2002-01-15 20:01) [3]

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

← →
Ev_genus (2002-01-18 17:34) [4]

Говорите по конкретнее. Пока я остановился на такой модели.
Сортируем по Y и устанавливаем закладки (делим плоскость на полосы). Ищем нужные точки в соотведствующих полосах. Но Меня и это не устраивает. Надо что бы быстро и надёжно (и памяти по меньше гребло).
Заранее спасибо.

PS Надо что бы быстро и надёжно (и памяти по меньше гребло). А так иногда бывает.

← →
Romkin (2002-01-21 11:50) [5]

Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ.
Как раз там описан метод для поиска наименьшего расстояния между точками, кол-во действий O(n*Log2(n)).
Алгоритм, правда, рекурсивный, так что насчет памяти - как запрограммируешь, но все равно прилично.
Идея такая:
Исходные данные: два массива X & Y, содержащие координаты (x,y)(записи типа TRecord вполне). Массивы упорядочены по возрастанию координат, соотв. x & y.
1. Делим множество точек пополам вертикальной линией (находим медиану массива X) на два L & R. Точки на линии - как хочешь респределяем по половинам. Получаем соотв Xr, Yr & Xl & Yl, также упорядоченные
2. Находим минимальные расстояния между точками половин (рекурсивно, те тоже дробя их пополам и тд), Dr & Dl соотв.
Находим минимальное расстояние из этих двух: D.
3. На основе Y создаем массив Yd, содержащий точки, расстояние по х которых от линии не более D (упорядоченный по y). Проходя по этому массиву снизу вверх, вычисляем для каждой точки расстояние до 7 следующих (обоснование семи - в книге).
Соответственно, минимальное из этих расстояний - минимальное для двух половин. Если гарантируется, что точки не совпадают, имхо, можно ограничится 5 точками.
Все делается рекурсивно, первоначально массивы удобно упорядочить QuickSort (demos\threads). Потом надо делить так, чтобы постоянно получались уже упорядоченные. Впрочем, поскольку по условию задачи входной массив почти упорядочен, QuickSort подходит плохо, упорядочивать лучше другими алгоритмами.

Нужна струкнура данных, Найти похожие ветки