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

@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.

Новые блоги и статьи Все статьи Все блоги /
Агрегаты и сущности в DDD микросервисах Javaican 10.04.2025 Разработка современных программных систем часто приводит на распутье: монолит или микросервисы? Даже при выборе микросервисной архитектуры многие команды сталкиваются с проблемой правильного. . .	Многопоточность в C#: Task и параллельное программирование UnmanagedCoder 10.04.2025 Современные процессоры уже давно перестали наращивать тактовую частоту в пользу увеличения количества ядер. Это создало интересную ситуацию: разработчики, привыкшие к последовательному. . .	Линейное решение нелинейной задачи будет применено как метод обработки данных из double buffering. Формулы от LM конечно с ошибками. Hrethgir 10.04.2025 В продолжение Эта LM дала ответ похожий на нормальный. В комментриях мой комментарий - похоже она ошиблась с выведением итоговой формулы, но остальные проверю. Assistant qwen2. 5-14b-instruct . . . .	Переменные в Python py-thonny 10.04.2025 Переменная в программировании — это символическое имя, связанное с областью памяти, в которой хранится значение. Она позволяет получать доступ к данным через понятные человеку идентификаторы, а не. . .	Многопоточность в C#: Task и асинхронные операции UnmanagedCoder 10.04.2025 Многопоточность позволяет выполнять несколько операций одновременно, что важно для решения двух основных задач: повышения скорости выполнения вычислительно-сложных операций и сохранения отзывчивости. . .
Линейное решение не линейной задачи (емкость вычислений в сравнении с традиционными решениями пока не определена). Hrethgir 10.04.2025 В рамках предстоящих вычислений пришлось (да, я тоже знаю про корень числа, и про степеня, и прочие теоремы, но. . . ) найти способ нахождения отношения двух углов. . . .	Запуск контейнеров Docker на ARM64 Mr. Docker 09.04.2025 Появление таких решений, как Apple M1/ M2, AWS Graviton, Ampere Altra и Raspberry Pi, сделало использование ARM-систем обыденностью для многих разработчиков и DevOps-инженеров. При этом Docker,. . .	Vue SFC компонент на PHP с Fusion Jason-Webb 09.04.2025 PHP на сервере и JavaScript на клиенте — классическое сочетание, которое, несмотря на свою эффективность, создает определенный когнитивный диссонанс при разработке. В этом контексте появляются. . .	TypeScript vs JavaScript: Отличия и когда что использовать Reangularity 09.04.2025 JavaScript появился в 1995 году как творение Брендана Эйха и быстро стал основой интерактивности в вебе. За свою историю он прошел путь от простого языка для манипуляций с DOM до полноценной. . .	Подключение Kafka к Elasticsearch Codd 09.04.2025 Apache Kafka и Elasticsearch — две мощные технологии, которые при совместном использовании создают эффективную платформу для обработки и анализа данных в реальном времени. Kafka, выступая в роли. . .

@OlafNestandart 56 / 56 / 31 Регистрация: 24.10.2016 Сообщений: 186
	12.03.2017, 00:17
	С ходу в голову пришло Сравнивать расстояния не каждой точки одной группы с каждой точкой другой, а описать окружности вокруг каждой группы, затем провести линию, соединяющую центры окружностей, и затем искать точки, ближайшие к местам пересечения линии с окружностями. Правда не гарантирую что это самый оптимальный вариант. Миниатюры 1

@zarko97 279 / 39 / 13 Регистрация: 11.10.2015 Сообщений: 405
	12.03.2017, 00:24 [ТС]
	OlafNestandart, ну я бы и до этого не додумался, спасибо) 0

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	12.03.2017, 03:41
	OlafNestandart, А если одна окружность находится внутри другой? 0

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

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	12.03.2017, 04:27
	OlafNestandart, Можно, например, разбить каждое множество на квадраты и перебирать только ближайшие. 0

@zarko97 279 / 39 / 13 Регистрация: 11.10.2015 Сообщений: 405
	12.03.2017, 13:17 [ТС]
	avgoor, а в чем отличие от окружности? 0

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	12.03.2017, 13:29
	zarko97, каждое множество разбивается на подмножества. Просто взять внешние точки множества не получится. Представьте такие множества: 1) точки на окружности с радиусом 10 и центр координат 2) точки на окружности с радиусом 20 и точка (1, 1). 0

@zarko97 279 / 39 / 13 Регистрация: 11.10.2015 Сообщений: 405
	12.03.2017, 15:10 [ТС]
	Сообщение от OlafNestandart сравнивать все точки А чем сравнение лучше перебора? Тот же перебор по факту выходит... 0

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