Ну наконец-то дюха х комментарий был очень полезен.
Для каждой вершины в скорректированном многоугольнике вы должны найти наборывекторы, которые делают эту вершину вписанной в целевой полигон.На самом деле этот набор векторов может быть представлен на поверхности как: целевой полигон, смещенный на координаты этой вершины
Все, что вам нужно сделать дальше, - это найти пересечениеиз всех этих полигонов.Для этой цели я использовал библиотеку Clipper .Затем выберите любую точку из набора пересечений и переведите скорректированный многоугольник по его координатам.
Сложность этого алгоритма будет примерно равна: O (N M log (M)) (Предполагается, что нас не волнует количество пересечений между полигонами набора перевода)
Улучшение: Более того, вы можете использовать тот же алгоритм для встраивания многоугольника в другой многоугольник оптимально (с точки зрения проблема режущего материала ).Просто выполните итерацию по интересным углам поворота (в моем случае я использовал все возможные углы между краями многоугольников), примените алгоритм, описанный выше, ко всем повернутым фигурам и выберите из всех возможных переводов тот, который перемещает центр тяжести скорректированного многоугольника в самое отдаленное положение от места назначения.центр тяжести многоугольника.
Надеюсь, что это может кому-нибудь помочь!
Редактировать: Забыл упомянуть.Подгонка вершин не является гарантией того, что ребра не пересекаются.Итак, на втором шаге вы должны выбрать вектор перевода, который не приводит к пересечению ребер скорректированного многоугольника с краями контура назначения.
В моем решении я использовал сравнение квадрата пересечения обоих многоугольников с квадратом места назначенияконтур.Если они равны, то все равно.Еще выберите другой пункт.
Конечно, эти проверки немного портят производительность, но это не так важно при поиске лучшей позиции многоугольника.Насколько мой опыт говорит:).
Спасибо Ив Даусту за поправку.