Найти выпуклый многоугольник, который охватывает все точки множества

@Dmitriy3211 · Регистрация: 07.05.2018

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

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

@Kuzia domovenok · 07.05.2018, 10:57

convex hull

Байт · 07.05.2018, 11:05

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

нет никаких идей.

Может быть вам поможет такой любопытный факт из аналитической геометрии. Если прямая задана общим уравнением Ax+By+C=0, то при подстановке точек из одной полуплоскости получается один знак, для другой полуплоскости - знак противоположный.

@Dmitriy3211 · 08.05.2018, 12:11 **[ТС]**

Можно поподробнее об convex hull? Никакой полезной информации на русском не нашёл

Добавлено через 23 часа 41 минуту
Up.

@AlexVRud · 08.05.2018, 13:25

https://ru.wikipedia.org/wiki/... 0%BA%D0%B0

@Kuzia domovenok · 08.05.2018, 13:34

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

Никакой полезной информации на русском не нашёл

тяжела и неказиста жизнь... эээмм безязыкового программиста

Не по теме:

как рифму-то подобрать, а?

Байт · 08.05.2018, 23:21

Dmitriy3211, Вот один грубый, но действенный алгоритм, основанный на факте из аналитической геометрии, изложенном в посте 3.
Выбираем точку A0 с наименьшей координатой X. Проводим (определяем общее уравнение) всех прямых A₀M.Две из них будут обязательно будут лежать по одну сторону от множества (проверка по знаку). Этим прямым соответствуют точки A₁, A_k. Точки A₀, A₁ Исключаются из дальнейшего перебора.
Теперь берем A₁ и анализируем все прямые A₁M. Одна из них будет обязательно содержать все множество точек с одной стороны. Соответствующая точка - A₂. И так далее, пока не упремся в точку A_n-k
На этом пути возможны коллизии, когда соответствующих прямых будет несколько (или есть несколько точек с наименьшей координатой X). Но это значит всего-лишь. что точки лежат на одной прямой. Выбирать в качестве следующей следует самую дальнюю. Как это сделать, легко понять если опять вспомнить аналитическую геометрию.
ЗЫ. Алгоритм не претендует на эффективность. Навярняка есть и более сильные. По ссылке уважаемого AlexVRud там их целая куча. Но этот - то, что приходит в голову первым.

Добавлено через 7 минут
Небольшое замечание. Нетрудно понять, что для любой вершины выпуклой оболочки существует такая система координат, что эта точка будет иметь иметь в ней "крайние" координаты (наибольший X, или наименьший) А для внутренних точек такой системы координат не существует. Может быть можно построить хороший алгоритм на этом факте...

Добавлено через 6 часов 30 минут
Можно еще поиграться с выбором вектора с наибольшим угловым коэффициентом....

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Dmitriy3211 0 / 0 / 0 Регистрация: 07.05.2018 Сообщений: 15

	Найти выпуклый многоугольник, который охватывает все точки множества 07.05.2018, 10:39. Показов 3798. Ответов 6 Метки нет (Все метки) Здравствуйте, возникли трудности с выполнением данного задания. Вообще нет никаких идей.. Надеюсь на помощь. Задано множество точек на плоскости (10 точек). Найти выпуклую оболочку этого множества, то есть выпуклый многоугольник с вершинами в некоторых точках этого множества, который охватывает все его точки. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	07.05.2018, 10:57
	convex hull 0

@Dmitriy3211 0 / 0 / 0 Регистрация: 07.05.2018 Сообщений: 15
	08.05.2018, 12:11 [ТС]
	Можно поподробнее об convex hull? Никакой полезной информации на русском не нашёл Добавлено через 23 часа 41 минуту Up. 0

@AlexVRud 694 / 304 / 99 Регистрация: 04.07.2014 Сообщений: 851
	08.05.2018, 13:25
	https://ru.wikipedia.org/wiki/... 0%BA%D0%B0 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	08.05.2018, 23:21
	Сообщение было отмечено Dmitriy3211 как решение Решение Dmitriy3211, Вот один грубый, но действенный алгоритм, основанный на факте из аналитической геометрии, изложенном в посте 3. Выбираем точку A0 с наименьшей координатой X. Проводим (определяем общее уравнение) всех прямых A₀M.Две из них будут обязательно будут лежать по одну сторону от множества (проверка по знаку). Этим прямым соответствуют точки A₁, A_k. Точки A₀, A₁ Исключаются из дальнейшего перебора. Теперь берем A₁ и анализируем все прямые A₁M. Одна из них будет обязательно содержать все множество точек с одной стороны. Соответствующая точка - A₂. И так далее, пока не упремся в точку A_n-k На этом пути возможны коллизии, когда соответствующих прямых будет несколько (или есть несколько точек с наименьшей координатой X). Но это значит всего-лишь. что точки лежат на одной прямой. Выбирать в качестве следующей следует самую дальнюю. Как это сделать, легко понять если опять вспомнить аналитическую геометрию. ЗЫ. Алгоритм не претендует на эффективность. Навярняка есть и более сильные. По ссылке уважаемого AlexVRud там их целая куча. Но этот - то, что приходит в голову первым. Добавлено через 7 минут Небольшое замечание. Нетрудно понять, что для любой вершины выпуклой оболочки существует такая система координат, что эта точка будет иметь иметь в ней "крайние" координаты (наибольший X, или наименьший) А для внутренних точек такой системы координат не существует. Может быть можно построить хороший алгоритм на этом факте... Добавлено через 6 часов 30 минут Можно еще поиграться с выбором вектора с наибольшим угловым коэффициентом.... 0

Найти выпуклый многоугольник, который охватывает все точки множества

Решение