алгоритм: геометрическая фигура может содержать другую фигуру

Question

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

программа написана на python и использует ее корректно.Сначала мы проверяем области, и если площадь прямоугольника может содержаться в форме, мы просто помещаем ее в центр и проверяем.Если он не входит, мы делаем поворот на один градус (например) и продолжаем тест.после 180 градусов мы прекращаем вращение и перемещаем его с 1 сантиметра (например) в форме спирали (чтобы сделать все позиции вокруг центра тяжести геометрической формы).

Программа работает хорошо, но для некоторыхесли он относительно медленный (несколько минут расчета), я не профессионал в тригонометрии, я прошу вас помочь ускорить лечение.

У вас есть какие-либо предложения?

спасибо.

от медленного:

http://image.noelshack.com/fichiers/2018/51/5/1545390818-3dadvwcbpzmewfdbzrm7.png

http://image.noelshack.com/fichiers/2018/51/5/1545390818-htadvwcbpzmewfdbzrq7.png

http://image.noelshack.com/fichiers/2018/51/5/1545390818-ojadvwcbpzmewfdbzqg6.png

http://image.noelshack.com/fichiers/2018/51/5/1545390818-3dadvwcbpzmewfdbzrm7.png

Answer 1

Мы можем определить, подходит ли повернутый прямоугольник к выпуклому многоугольнику с приближением скользящих точек.

Поместить один угол (пусть A) прямоугольника в какую-нибудь вершину многоугольника и поместить другой угол B на ребровправо к этой вершине (или следующему ребру, если ребро прямоугольника слишком длинное).Двигайте A вправо, пока A или B не встретятся с вершиной многоугольника.Проверьте, пересекают ли траектории C и D ребра многоугольника.Эти траектории могут быть прямыми или что-то вроде циклоида (если B скользит по другому edgr, чем A).Повторите для следующего куска, пока А или В встречаются со следующей вершиной.Если не удалось, проверьте также другое размещение - ребро BC.

К сожалению, этот подход не работает для вогнутых многоугольников.