Даны 2 маршрута(к примеру, автобусных). Известны координаты каждой остановки обоих маршрутов.   Общей остановки у них нет(это важно). Как найти 2 ближайшие друг к другу остановки на этих маршрутах(оранжевые точки на рисунке)? Вариант "тупо перебором" (попарно брать координаты остановок и вычислять расстояние между ними) не подходит. Подскажите, пожалуйста, алгоритм, или хотя бы в какую сторону копать/что гуглить. Заранее спасибо.

можно попробовать деревья: http://en.wikipedia.org/wiki/Quadtree

Еще актуальна задача?

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

Поиск ближайших точек с применением сканирующей линии уменьшит вычислительную сложность с квадратичной до NlogN (вроде бы). Но значительно возрастет сложность программирования. Кроме того, как написано выше, N^2 для небольшого числа точек работает вполне быстро. Так что нужно хорошо подумать, стоит ли усложнять.
Если предполагается считать не один раз, самый простой метод - распихать предварительно точки по квадратным кластерам. Скорость увеличивается значительно, и запрограммировать несложно.

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

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

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

Если есть нужда имменно тупо искать путь, то без перебора не обойтись. Но по уму искать его надо не тупо, т.е. не по карте, а(разворачивая предидущие ответы) на заранее подготовленном графе автобусного движения. Я бы попытался примерно так:

• Отбросил остановки, заведомо расположенные на карте вне зоны возможных пересечений.
• Из остальных построил бы граф связав остановки автобусными линиями.
• Выбрал бы максимальную длину "пешеходного броска", например 10 мин. И связал бы между собой все, не всязанные напрямую остановки, находящиеся в пределах "длины броска".
• Нашел бы в графе кратчайший путь от каждой остановки к каждой.

Дальше два варианта:
1) Свести в БД найденные пути и пользоватся базой.
2) Убрать из графа все ни разу не использованные переходы и каждый раз искать путь в графе.
3) То же, что и 2, но не убирая ничего.

Вариант 1 самый разумный. Но 2 и 3 позволяют вносить быстрые изменения. Например, где-то ремонт идет и дорога перекрыта на два дня.

ЗЫ: И еще я бы делал два разных варианта поиска кратчайшего пути: самый быстрый и вклучающий минимум хотьбы (для стариков, инвалидов, и т.д.)

Это сообщение отредактировал(а) _Y_ - 18.4.2011, 22:28

 может стоит отсортировать номера остановок по осям допустим по возрастанию, в процессе сортировки будет минимум перестановок, т.к. обычно расстояние между остановками не значительное и ты знаешь в какой последовательности соединяются остановки одного маршрута. 
1). В процессе сортировки создаем Массив_Х1 в котором хранятся номера остановок первого маршрута отсортированные по оси Х и Массив_Y1 в котором хранятся номера остановок первого маршрута отсортированные по оси Y.
2).  Для второго маршрута, тоже самое только все заносим в Массив_Х2 и массив_Y2.
3). Далее цикл или два цикла в которых из элементов массивов  X1, и Y1 вытаскиваем их координаты и соответственно вычитаем координаты только первых элементов хранящихся в массивах X2[0], Y2[0] . т.к. данные отсортированы, то при грамотном задании условия "выхода из цикла" весь массив X1 и Y1 можно не пробегать. Cохраняем номер остановки хранящийся в массиве Х1(например в переменную i) и номер остановки хранящийся в массиве Y1(например в переменную k) при которых получились минимальные разницы близкие к нулю в идеале нуль.
в конечном итоге должно выглядеть примерно так.
X_1[0], X_1[1], X_1[2], X_1[3],X_1[4],...X_1[i], X_1[i+1], ...X_1[m].
                                                                  X_2[0],X_2[1],....
Y_1[0], Y_1[1], ...Y_1[k], Y_1[k+1], ...Y_1[m].
                             Y_2[0],Y_2[1],....
Соответственно получили полностью отсортированные данные и определить минимальное расстояние между остановками обычным перебором с минимумом сравнений не составит труда. 

Это сообщение отредактировал(а) миг - 18.4.2011, 20:26

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

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

Если рассматривать только движение пешком, будет просто окружность с увеличивающимся радиусом.

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

Так что тут понадобятся две вещи:
1. представление волны в виде объединения окружностей и точек и её движение
2. возможность находить остановки вблизи от волны (тут, наверное, достаточно дерева)

Пример

Neox_GeForce
Да только этот алгоритм просто найдёт пару ближайших точек, а нам надо - пару ближайших из разных путей ;)

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

Конечно, для этой задачи давно известны "серьёзные" структуры данных, но проще, чем строить диаграмму Вороного - я не знаю (да и этот-то написать в жизни не смогу  ).

По теме - http://en.wikipedia.org/wiki/Nearest_neighbor_search.

Из готового можно попробовать прикрутить мощную геометрическую библиотеку CGAL - в ней реализовано это.


P.S. Да, топик конечно старый, но всё же.

Кстати, да. Но это немного из серии "из пушки по воробьям". Кроме того, "соседние" точки не значит "ближайшие из другой линии" - строить-то придется по всем точкам всех линий.
  
Что касается реализации алгоритма построения диаграммы Вороного - наверняка сможешь, особенно после ознакомления с лекциями по компьютерной геометрии Maryland University (гуглится по коду CMSC 754). Отлично описан алгоритм Форчуна. (Собственно, это единственный источник, где он описан понятно, из того что я нашла - буквально этим летом парилась с диаграммой Вороного, больше недели потратила.)
Да и многое другое из области компьютерной геометрии - рекомендую всем, кому это надо.