Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Сортировка географических координат по близости друг к другу - Мир MS Excel

Старая форма входа
  • Страница 1 из 2
  • 1
  • 2
  • »
Модератор форума: китин, _Boroda_  
Мир MS Excel » Вопросы и решения » Вопросы по Excel » Сортировка географических координат по близости друг к другу (Формулы/Formulas)
Сортировка географических координат по близости друг к другу
totkapf Дата: Среда, 09.07.2014, 15:38 | Сообщение № 1
Группа: Пользователи
Ранг: Прохожий
Сообщений: 6
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
Добрый день, прошу помочь с сортировкой географических координат их гугловских карт. К примеру, если звять первую строку и считать её отправной точкой, то после сортировки за ней должна идти ближайшая к первой, затем ближайшая ко второй и так далее.

Спасибо за помощь.
К сообщению приложен файл: 2181574.xlsx (9.3 Kb)


Сообщение отредактировал totkapf - Среда, 09.07.2014, 15:39
 
Ответить
СообщениеДобрый день, прошу помочь с сортировкой географических координат их гугловских карт. К примеру, если звять первую строку и считать её отправной точкой, то после сортировки за ней должна идти ближайшая к первой, затем ближайшая ко второй и так далее.

Спасибо за помощь.

Автор - totkapf
Дата добавления - 09.07.2014 в 15:38
AlexM Дата: Среда, 09.07.2014, 16:21 | Сообщение № 2
Группа: Друзья
Ранг: Участник клуба
Сообщений: 4480
Репутация: 1114 ±
Замечаний: 0% ±

Excel 2003
Разделить широту и долготу формулами
Код
=ПОДСТАВИТЬ(ЛЕВБ(A2;9);".";",")
и
Код
=ПОДСТАВИТЬ(ПРАВБ(A2;9);".";",")
посчитать расстояние формулой
Код
=ACOS(SIN(B$2*ПИ()/180)*SIN(B2*ПИ()/180)+COS(B$2*ПИ()/180)*COS(B2*ПИ()/180)*COS((C$2-C2)*ПИ()/180))*6371,21
где 6371,21 - радиус земли. Для сортировки на радиус земли можно не умножать.
Далее сортируем
Выделить A2:D10. Данные - Сортировка
По столбцу расстояние, по возрастанию, Ок
К сообщению приложен файл: 2181574_new.xls (26.0 Kb)



Номер мобильного модема (без голосовой связи)
9269171249 МегаФон, Московский регион.
 
Ответить
СообщениеРазделить широту и долготу формулами
Код
=ПОДСТАВИТЬ(ЛЕВБ(A2;9);".";",")
и
Код
=ПОДСТАВИТЬ(ПРАВБ(A2;9);".";",")
посчитать расстояние формулой
Код
=ACOS(SIN(B$2*ПИ()/180)*SIN(B2*ПИ()/180)+COS(B$2*ПИ()/180)*COS(B2*ПИ()/180)*COS((C$2-C2)*ПИ()/180))*6371,21
где 6371,21 - радиус земли. Для сортировки на радиус земли можно не умножать.
Далее сортируем
Выделить A2:D10. Данные - Сортировка
По столбцу расстояние, по возрастанию, Ок

Автор - AlexM
Дата добавления - 09.07.2014 в 16:21
totkapf Дата: Среда, 09.07.2014, 16:42 | Сообщение № 3
Группа: Пользователи
Ранг: Прохожий
Сообщений: 6
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
Круто, очень...

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

Вообще задача такая, что надо объехать много-много точек на карте и необходимо спланировать порядок объезда так, чтобы не ездить через весь город, в день планируется посещение порядка трёх точек. Можно в Вашем варианте править формулу в каждой четвёртой строке и сортировать заново все ниже лежащие, но это долго (точек порядка 100) и боюсь заупутаться. Можно это как-то автоматизировать?
 
Ответить
СообщениеКруто, очень...

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

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

Автор - totkapf
Дата добавления - 09.07.2014 в 16:42
Gustav Дата: Среда, 09.07.2014, 17:46 | Сообщение № 4
Группа: Друзья
Ранг: Участник клуба
Сообщений: 2731
Репутация: 1132 ±
Замечаний: 0% ±

начинал с Excel 4.0, видел 2.1
Попробовал. В принципе что-то получается. С обильным использованием функции РАНГ и огромной решательной полуматрицей. Для уникальной однозначности РАНГ добавил в формулу номер строки (в 6-й разряд после запятой). Решение не окончательное, но показывающее направление. Надо еще будет собрать отсортированные координаты из первой строки матрицы. Если будет 100 пар координат, то по ширине листа в Excel 2003 не влезет, как минимум 2007.
К сообщению приложен файл: 2181574_geo.xlsx (16.2 Kb)


МОИ: Ник, Tip box: 41001663842605
 
Ответить
СообщениеПопробовал. В принципе что-то получается. С обильным использованием функции РАНГ и огромной решательной полуматрицей. Для уникальной однозначности РАНГ добавил в формулу номер строки (в 6-й разряд после запятой). Решение не окончательное, но показывающее направление. Надо еще будет собрать отсортированные координаты из первой строки матрицы. Если будет 100 пар координат, то по ширине листа в Excel 2003 не влезет, как минимум 2007.

Автор - Gustav
Дата добавления - 09.07.2014 в 17:46
MCH Дата: Среда, 09.07.2014, 17:59 | Сообщение № 5
Группа: Админы
Ранг: Старожил
Сообщений: 2003
Репутация: 751 ±
Замечаний: ±

На вид классическая задача коммивояжера.
Нужно ли возвращатся в первоначальную точку?
Нужно ли обязательно объезжать все точки?

Если точек не более 10-12, то оптимальный маршрут можно найти перебором всех возможных вариантов, если более 15, то перебор уже не подойдет.
То что Вы описали по решению напоминает жадный алгоритм. Он подойдет если нет необходимости возвращатся в первоначальную точку.
Если маршрут должен быть замкнутым, то можно еще попытатся решить методом ветвей и границ (методом Литтла) - но алгоритм достаточно сложный и его реализации на VBA у меня нет (но думал реализовать)
 
Ответить
СообщениеНа вид классическая задача коммивояжера.
Нужно ли возвращатся в первоначальную точку?
Нужно ли обязательно объезжать все точки?

Если точек не более 10-12, то оптимальный маршрут можно найти перебором всех возможных вариантов, если более 15, то перебор уже не подойдет.
То что Вы описали по решению напоминает жадный алгоритм. Он подойдет если нет необходимости возвращатся в первоначальную точку.
Если маршрут должен быть замкнутым, то можно еще попытатся решить методом ветвей и границ (методом Литтла) - но алгоритм достаточно сложный и его реализации на VBA у меня нет (но думал реализовать)

Автор - MCH
Дата добавления - 09.07.2014 в 17:59
MCH Дата: Среда, 09.07.2014, 18:33 | Сообщение № 6
Группа: Админы
Ранг: Старожил
Сообщений: 2003
Репутация: 751 ±
Замечаний: ±

Пробовал решать случайной расстановкой.
Для небольшого количества точек подходит
К сообщению приложен файл: 8456417.xlsb (22.9 Kb)
 
Ответить
СообщениеПробовал решать случайной расстановкой.
Для небольшого количества точек подходит

Автор - MCH
Дата добавления - 09.07.2014 в 18:33
totkapf Дата: Четверг, 10.07.2014, 09:37 | Сообщение № 7
Группа: Пользователи
Ранг: Прохожий
Сообщений: 6
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
Gustav, спасибо вариант очень интересный, осталось только разобраться как вытаскивать собственно нумерацию, пока, как я понял, это только врчную работает, надо попробовать на всей матрице.

Ещё раз спасибо за ответ.
 
Ответить
СообщениеGustav, спасибо вариант очень интересный, осталось только разобраться как вытаскивать собственно нумерацию, пока, как я понял, это только врчную работает, надо попробовать на всей матрице.

Ещё раз спасибо за ответ.

Автор - totkapf
Дата добавления - 10.07.2014 в 09:37
totkapf Дата: Четверг, 10.07.2014, 09:39 | Сообщение № 8
Группа: Пользователи
Ранг: Прохожий
Сообщений: 6
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
MCH, очень интересно, только не могу понять, почему, когда я добавлюя новые строки, даже поправив в формулах конечную строку, у меня всё слетает? Что я делаю не так?
 
Ответить
СообщениеMCH, очень интересно, только не могу понять, почему, когда я добавлюя новые строки, даже поправив в формулах конечную строку, у меня всё слетает? Что я делаю не так?

Автор - totkapf
Дата добавления - 10.07.2014 в 09:39
HoBU4OK Дата: Четверг, 10.07.2014, 12:29 | Сообщение № 9
Группа: Проверенные
Ранг: Обитатель
Сообщений: 309
Репутация: 14 ±
Замечаний: 0% ±

Excel 2010
У меня так получается

Требуется доводка
К сообщению приложен файл: 2181574_geo_1.xls (30.5 Kb)


Я думал, ты остроглазый лев, а ты слепая собака :-)
 
Ответить
СообщениеУ меня так получается

Требуется доводка

Автор - HoBU4OK
Дата добавления - 10.07.2014 в 12:29
MCH Дата: Четверг, 10.07.2014, 14:12 | Сообщение № 10
Группа: Админы
Ранг: Старожил
Сообщений: 2003
Репутация: 751 ±
Замечаний: ±

Что я делаю не так?

Без Вашего файла трудно сказать что не так, но нужно учитывать, что макрос ссылается на определенные ячейки, формулы и график тоже ссылаются на определенные диапазоны и т.д.
Если не получается вставить данные самому, то приложите обновленный файл - поправим


Сообщение отредактировал MCH - Четверг, 10.07.2014, 14:54
 
Ответить
Сообщение
Что я делаю не так?

Без Вашего файла трудно сказать что не так, но нужно учитывать, что макрос ссылается на определенные ячейки, формулы и график тоже ссылаются на определенные диапазоны и т.д.
Если не получается вставить данные самому, то приложите обновленный файл - поправим

Автор - MCH
Дата добавления - 10.07.2014 в 14:12
Gustav Дата: Четверг, 10.07.2014, 15:34 | Сообщение № 11
Группа: Друзья
Ранг: Участник клуба
Сообщений: 2731
Репутация: 1132 ±
Замечаний: 0% ±

начинал с Excel 4.0, видел 2.1
Реализовал свой алгоритм сортировки в процедурном виде с использованием рекордсетов ADO в качестве массивов (их можно удобно фильтровать и сортировать в памяти). Стало всё намного компактнее и прозрачнее.

В качестве параметров процедуре надо передать исходный диапазон листа (2 колонки), содержащий координаты точек, а также указать диапазон вывода порядковых номеров сортировки (также вертикальный, 1 колонка). Удобно вывести порядковые номера в ближайший столбец, соседний с координатами, чтобы потом стандартно отсортироваться по этому столбцу. Первой строкой исходного диапазона должна быть выбранная точка отсчета (поэтому порядковый номер для первой строки всегда будет 1).

К сообщению приложен файл: 2181574_geo2.xlsm (36.6 Kb)


МОИ: Ник, Tip box: 41001663842605
 
Ответить
СообщениеРеализовал свой алгоритм сортировки в процедурном виде с использованием рекордсетов ADO в качестве массивов (их можно удобно фильтровать и сортировать в памяти). Стало всё намного компактнее и прозрачнее.

В качестве параметров процедуре надо передать исходный диапазон листа (2 колонки), содержащий координаты точек, а также указать диапазон вывода порядковых номеров сортировки (также вертикальный, 1 колонка). Удобно вывести порядковые номера в ближайший столбец, соседний с координатами, чтобы потом стандартно отсортироваться по этому столбцу. Первой строкой исходного диапазона должна быть выбранная точка отсчета (поэтому порядковый номер для первой строки всегда будет 1).


Автор - Gustav
Дата добавления - 10.07.2014 в 15:34
totkapf Дата: Четверг, 10.07.2014, 16:06 | Сообщение № 12
Группа: Пользователи
Ранг: Прохожий
Сообщений: 6
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
MCH, я добалил в файл новую строку "Новая запись", в Исходные данные, ввёл в неё реальные координаты. Потом добавил с таблицу рядом, поправил ссылки и диапазоны, но по кнопке Случайно программа возвращает ошибку. Вроде всё проверил, все ссылки, но что-то не так
К сообщению приложен файл: 0825418.xlsb (23.6 Kb)
 
Ответить
СообщениеMCH, я добалил в файл новую строку "Новая запись", в Исходные данные, ввёл в неё реальные координаты. Потом добавил с таблицу рядом, поправил ссылки и диапазоны, но по кнопке Случайно программа возвращает ошибку. Вроде всё проверил, все ссылки, но что-то не так

Автор - totkapf
Дата добавления - 10.07.2014 в 16:06
MCH Дата: Четверг, 10.07.2014, 16:26 | Сообщение № 13
Группа: Админы
Ранг: Старожил
Сообщений: 2003
Репутация: 751 ±
Замечаний: ±

Поправил
К сообщению приложен файл: 6298444.xlsb (37.9 Kb)
 
Ответить
СообщениеПоправил

Автор - MCH
Дата добавления - 10.07.2014 в 16:26
totkapf Дата: Пятница, 11.07.2014, 09:33 | Сообщение № 14
Группа: Пользователи
Ранг: Прохожий
Сообщений: 6
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
Попробовал, работает, спасибо большое.

Всем остальным тоже спабо, Gustav, вариант хороший, но добавление новых точек отнимает слишком много времени.
 
Ответить
СообщениеПопробовал, работает, спасибо большое.

Всем остальным тоже спабо, Gustav, вариант хороший, но добавление новых точек отнимает слишком много времени.

Автор - totkapf
Дата добавления - 11.07.2014 в 09:33
AlexM Дата: Пятница, 11.07.2014, 10:57 | Сообщение № 15
Группа: Друзья
Ранг: Участник клуба
Сообщений: 4480
Репутация: 1114 ±
Замечаний: 0% ±

Excel 2003
MCH, Очень бы хотелось посмотреть на решение задачи.



Номер мобильного модема (без голосовой связи)
9269171249 МегаФон, Московский регион.
 
Ответить
СообщениеMCH, Очень бы хотелось посмотреть на решение задачи.

Автор - AlexM
Дата добавления - 11.07.2014 в 10:57
MCH Дата: Пятница, 11.07.2014, 17:36 | Сообщение № 16
Группа: Админы
Ранг: Старожил
Сообщений: 2003
Репутация: 751 ±
Замечаний: ±

.
К сообщению приложен файл: 10.xls (90.5 Kb)
 
Ответить
Сообщение.

Автор - MCH
Дата добавления - 11.07.2014 в 17:36
HoBU4OK Дата: Пятница, 11.07.2014, 18:28 | Сообщение № 17
Группа: Проверенные
Ранг: Обитатель
Сообщений: 309
Репутация: 14 ±
Замечаний: 0% ±

Excel 2010
Классно получилось, у меня МИН расстояние 3692 выскачило


Я думал, ты остроглазый лев, а ты слепая собака :-)
 
Ответить
СообщениеКлассно получилось, у меня МИН расстояние 3692 выскачило

Автор - HoBU4OK
Дата добавления - 11.07.2014 в 18:28
MCH Дата: Суббота, 12.07.2014, 10:03 | Сообщение № 18
Группа: Админы
Ранг: Старожил
Сообщений: 2003
Репутация: 751 ±
Замечаний: ±

Попытка найти решение случайным образом уже для 20 точек не получается, сделал решение графическим способом.
Решение не всегда может быть оптимальным, но близкое к таковому, при этом скорость решения очень большая
К сообщению приложен файл: Travelling_sale.rar (50.1 Kb)


Сообщение отредактировал MCH - Суббота, 12.07.2014, 10:50
 
Ответить
СообщениеПопытка найти решение случайным образом уже для 20 точек не получается, сделал решение графическим способом.
Решение не всегда может быть оптимальным, но близкое к таковому, при этом скорость решения очень большая

Автор - MCH
Дата добавления - 12.07.2014 в 10:03
MCH Дата: Суббота, 12.07.2014, 11:11 | Сообщение № 19
Группа: Админы
Ранг: Старожил
Сообщений: 2003
Репутация: 751 ±
Замечаний: ±

Сделал для 100 точек, тоже все очень быстро считает
К сообщению приложен файл: 6494697.rar (66.4 Kb)


Сообщение отредактировал MCH - Суббота, 12.07.2014, 12:25
 
Ответить
СообщениеСделал для 100 точек, тоже все очень быстро считает

Автор - MCH
Дата добавления - 12.07.2014 в 11:11
SLAVICK Дата: Вторник, 12.08.2014, 14:36 | Сообщение № 20
Группа: Модераторы
Ранг: Старожил
Сообщений: 2290
Репутация: 766 ±
Замечаний: 0% ±

2019
Шикарное решение MCH hands
На сколько я понял алгоритм - расчет идет по расположению... т.е. нахождение точек внутри многоугольника.
Похожее решение видел на немецком форуме(файл внутри)... там тоже расчет связан с графиком.
У этого подхода есть один недостаток - он производит расчет по прямой... а натуральное расстояние может в разы отличатся(например точки А и Б находятся на разных берегах, и чтобы доехать из А в Б - можно по пути проехать несколько точек (В,Г,Д) - тогда будет не АБВГД а АВГДБ).
Мы с Вами уже обсуждали тему здесь, но в этой теме она обсуждается активней :)
Может можно как-то связать то что Вы сделали с матрицей реальных расстояний? Чтобы показывало действительно наилучший и реальный результат.
Думаю может какую-то перепроверку по прилегающим квадратам или точкам, чтобы не перебирать все точки?
К сообщению приложен файл: Forum26012009-1.xls (53.0 Kb)


Иногда все проще чем кажется с первого взгляда.
 
Ответить
СообщениеШикарное решение MCH hands
На сколько я понял алгоритм - расчет идет по расположению... т.е. нахождение точек внутри многоугольника.
Похожее решение видел на немецком форуме(файл внутри)... там тоже расчет связан с графиком.
У этого подхода есть один недостаток - он производит расчет по прямой... а натуральное расстояние может в разы отличатся(например точки А и Б находятся на разных берегах, и чтобы доехать из А в Б - можно по пути проехать несколько точек (В,Г,Д) - тогда будет не АБВГД а АВГДБ).
Мы с Вами уже обсуждали тему здесь, но в этой теме она обсуждается активней :)
Может можно как-то связать то что Вы сделали с матрицей реальных расстояний? Чтобы показывало действительно наилучший и реальный результат.
Думаю может какую-то перепроверку по прилегающим квадратам или точкам, чтобы не перебирать все точки?

Автор - SLAVICK
Дата добавления - 12.08.2014 в 14:36
Мир MS Excel » Вопросы и решения » Вопросы по Excel » Сортировка географических координат по близости друг к другу (Формулы/Formulas)
  • Страница 1 из 2
  • 1
  • 2
  • »
Поиск:

Яндекс.Метрика Яндекс цитирования
© 2010-2024 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!