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

@zarko97 · Регистрация: 11.10.2015

Author24 — интернет-сервис помощи студентам

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

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

C++

1	std::vector<std::vector<std::pair<double, double>>>

?

Добавлено через 27 минут
UP: Множеств может быть любое количество, не только два

@OlafNestandart · 12.03.2017, 00:17

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

@zarko97 · 12.03.2017, 00:24 **[ТС]**

OlafNestandart, ну я бы и до этого не додумался, спасибо)

@avgoor · 12.03.2017, 03:41

OlafNestandart, А если одна окружность находится внутри другой?

@OlafNestandart · 12.03.2017, 04:00

Сообщение от avgoor

А если одна окружность находится внутри другой?

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

Добавлено через 7 минут
И еще он не всегда будет верно работать, нужно дорабатывать

@avgoor · 12.03.2017, 04:27

OlafNestandart, Можно, например, разбить каждое множество на квадраты и перебирать только ближайшие.

@zarko97 · 12.03.2017, 13:17 **[ТС]**

avgoor, а в чем отличие от окружности?

@avgoor · 12.03.2017, 13:29

zarko97, каждое множество разбивается на подмножества. Просто взять внешние точки множества не получится. Представьте такие множества: 1) точки на окружности с радиусом 10 и центр координат 2) точки на окружности с радиусом 20 и точка (1, 1).

@zarko97 · 12.03.2017, 15:10 **[ТС]**

Сообщение от OlafNestandart

сравнивать все точки

А чем сравнение лучше перебора? Тот же перебор по факту выходит...

@avgoor · 12.03.2017, 15:20

zarko97, Перебирать не все точки, а только в минимально удаленных ячейках. Алгоритм из O(N^2) превращается в O(N*log(N)). Родственная задача. Особое внимание на раздел Calculation optimizations.

@OlafNestandart 56 / 56 / 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 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	12.03.2017, 03:41	4
	OlafNestandart, А если одна окружность находится внутри другой? 0

@OlafNestandart 56 / 56 / 31 Регистрация: 24.10.2016 Сообщений: 186
	12.03.2017, 04:00	5
	Сообщение от avgoor А если одна окружность находится внутри другой? Тогда напрашивается самый очевидный вариант - сравнивать все точки. В любом случае сложность этого алгоритма меньше чем у простого перебора и будет равна ему только в самом вырожденном случае, когда все множества пересекаются. И я ведь сразу предупредил - написал что сразу придумалось и нет никаких гарантий что не существует более оптимального алгоритма. Добавлено через 7 минут И еще он не всегда будет верно работать, нужно дорабатывать 0

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	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 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	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 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	12.03.2017, 15:20	10
	zarko97, Перебирать не все точки, а только в минимально удаленных ячейках. Алгоритм из O(N^2) превращается в O(N*log(N)). Родственная задача. Особое внимание на раздел Calculation optimizations. 1