Есть ли алгоритм для наиболее быстрого нахождения включает ли одна фигура другую? Приветствую!
Нужно наиболее быстрым способом найти включает ли полностью одна фигура другую на плоскости кроме как полным перебором.
Фигура задаётся множеством точек с координатами X, Y по часовой стрелке.
Был бы рад, если бы алгоритм был на русском.
Пока что придумал только так: по кругу обходим фигуру, берём её точку, прокладываем от неё отрезок по оси OX, и считаем пересечения этого отрезка с каждым отрезком между соседними точками другой фигуры. Если нечётно - то внутри, если чётно, то снаружи. Если хоть одна оказалась снаружи, то прекращаем, иначе считаем дальше.
Получится то получилось, но адцки медленно.

21 Авг 2019 в 06:16
173 +1
0
Ответы
1

Для нахождения включения одной фигуры в другую на плоскости существует алгоритм, называемый "алгоритмом Грэхема". Этот алгоритм основан на построении выпуклой оболочки двух фигур и проверке включения одной оболочки в другую.

Он работает следующим образом:

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

Этот алгоритм работает эффективнее, чем перебор всех точек фигуры, и может быть реализован на различных языках программирования, включая Python, Java, С++ и другие.

Надеюсь, данная информация поможет вам найти решение вашей задачи. Если у вас остались вопросы, не стесняйтесь задавать их!

20 Апр в 13:21
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Название заказа не должно быть пустым
Введите email
Бесплатные доработки
Гарантированные бесплатные доработки
Быстрое выполнение
Быстрое выполнение от 2 часов
Проверка работы
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Название заказа не должно быть пустым
Введите email
Доверьте свою работу экспертам
Разместите заказ
Наша система отправит ваш заказ на оценку 94 835 авторам
Первые отклики появятся уже в течение 10 минут
Прямой эфир