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

@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 минут
Можно еще поиграться с выбором вектора с наибольшим угловым коэффициентом....

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

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

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

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 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

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

Решение