Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
zarko97
279 / 39 / 13
Регистрация: 11.10.2015
Сообщений: 405
1

Расстояние между двумя заданными множествами точек на плоскости

11.03.2017, 22:12. Просмотров 572. Ответов 9
Метки нет (Все метки)

Расстояние между двумя множествами точек - это расстояние между наиболее близко расположенными точками этих множеств. Найти расстояние между двумя заданными множествами точек на плоскости.

Не могу найти оптимальный вариант решения сей задачи, кроме как перебором...а что если задано овер 100 множеств и эти точки предпоследняя и последняя точки крайнего множества? И целесообразно представить множества так:
C++
1
std::vector<std::vector<std::pair<double, double>>>
?

Добавлено через 27 минут
UP: Множеств может быть любое количество, не только два
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2017, 22:12
Ответы с готовыми решениями:

Расстояние между двумя множествами точек - это расстояние между наиболее близко расположенными точками этих
1. Расстояние между двумя множествами точек - это расстояние между наиболее...

Расстояние между двумя произвольно заданными на плоскости отрезками
Ребят, подскажите как найти расстояние между двумя произвольно заданными на...

Вычислить расстояние между двумя точками с заданными координатами
Вычислить расстояние между двумя точками с заданными координатами:A(a,d),B(u,m).

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

Найти расстояние между двумя точками на плоскости
Даны четыре действительных числа: x1, y1, x2, y2. Напишите функцию distance(x1,...

9
OlafNestandart
54 / 54 / 31
Регистрация: 24.10.2016
Сообщений: 186
12.03.2017, 00:17 2
С ходу в голову пришло
Сравнивать расстояния не каждой точки одной группы с каждой точкой другой, а описать окружности вокруг каждой группы, затем провести линию, соединяющую центры окружностей, и затем искать точки, ближайшие к местам пересечения линии с окружностями. Правда не гарантирую что это самый оптимальный вариант.
1
Миниатюры
Расстояние между двумя заданными множествами точек на плоскости  
zarko97
279 / 39 / 13
Регистрация: 11.10.2015
Сообщений: 405
12.03.2017, 00:24  [ТС] 3
OlafNestandart, ну я бы и до этого не додумался, спасибо)
0
avgoor
1041 / 609 / 157
Регистрация: 05.12.2015
Сообщений: 1,732
12.03.2017, 03:41 4
OlafNestandart, А если одна окружность находится внутри другой?
0
OlafNestandart
54 / 54 / 31
Регистрация: 24.10.2016
Сообщений: 186
12.03.2017, 04:00 5
Цитата Сообщение от avgoor Посмотреть сообщение
А если одна окружность находится внутри другой?
Тогда напрашивается самый очевидный вариант - сравнивать все точки. В любом случае сложность этого алгоритма меньше чем у простого перебора и будет равна ему только в самом вырожденном случае, когда все множества пересекаются. И я ведь сразу предупредил - написал что сразу придумалось и нет никаких гарантий что не существует более оптимального алгоритма.

Добавлено через 7 минут
И еще он не всегда будет верно работать, нужно дорабатывать
0
avgoor
1041 / 609 / 157
Регистрация: 05.12.2015
Сообщений: 1,732
12.03.2017, 04:27 6
OlafNestandart, Можно, например, разбить каждое множество на квадраты и перебирать только ближайшие.
0
zarko97
279 / 39 / 13
Регистрация: 11.10.2015
Сообщений: 405
12.03.2017, 13:17  [ТС] 7
avgoor, а в чем отличие от окружности?
0
avgoor
1041 / 609 / 157
Регистрация: 05.12.2015
Сообщений: 1,732
12.03.2017, 13:29 8
zarko97, каждое множество разбивается на подмножества. Просто взять внешние точки множества не получится. Представьте такие множества: 1) точки на окружности с радиусом 10 и центр координат 2) точки на окружности с радиусом 20 и точка (1, 1).
0
zarko97
279 / 39 / 13
Регистрация: 11.10.2015
Сообщений: 405
12.03.2017, 15:10  [ТС] 9
Цитата Сообщение от OlafNestandart Посмотреть сообщение
сравнивать все точки
А чем сравнение лучше перебора? Тот же перебор по факту выходит...
0
avgoor
1041 / 609 / 157
Регистрация: 05.12.2015
Сообщений: 1,732
12.03.2017, 15:20 10
zarko97, Перебирать не все точки, а только в минимально удаленных ячейках. Алгоритм из O(N^2) превращается в O(N*log(N)). Родственная задача. Особое внимание на раздел Calculation optimizations.
1
12.03.2017, 15:20
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.03.2017, 15:20

Вычислить расстояние между двумя точками на плоскости
1. Известны координаты на плоскости двух точек. Составить программу вычисления...

Вычислить расстояние между двумя точками на плоскости
Вычислить расстояние между двумя точками на плоскости, заданных своими...

Вычисление расстояния между двумя точками, заданными на плоскости их координатами
Составить программу вычисления расстояния между двумя точками, заданными на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru