Как найти наилучшее вложение выпуклого многоугольника в другой выпуклый многоугольник

Question

Я ищу алгоритм для вычисления перемещения, поворота и масштабирования, необходимых для позиционирования выпуклого многоугольника (P1) внутри другого выпуклого многоугольника (P2). Мне нужно, чтобы он возвращал "наилучшее соответствие", то есть P1 полностью содержится в P2 и имеет максимально возможную площадь.

Рассмотрим следующую диаграмму: http://i.imgur.com/ckaIIv7.png

Черный многоугольник справа (P1) должен быть оптимально размещен внутри синего многоугольника слева (P2).

Я нашел в Интернете много письменных статей об алгоритмах сдерживания многоугольников, но эти алгоритмы должны определить, могут ли многоугольники вписываться в другой многоугольник, учитывая возможность их перевода и поворота.

Алгоритм, который я ищу, должен всегда давать результат, потому что он включает в себя возможность масштабировать многоугольник P1. Я понимаю, что этот тип алгоритма может дать несколько оптимальных ответов, и это нормально.

Любая помощь?

Answer 1

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

Допустим, у вас есть P1 с p вершины и P2 с q вершины, и вы хотите соответствовать P1 внутри P2,

Вы уже нашли статьи, описывающие, как определить, может ли P1 вписаться в P2. Например, эта статья дает алгоритм в O(pq^2) время. Я не уверен, что это может быть еще быстрее, если вы знаете оба P1 а также p2 выпуклые

Итак, начнем с большого числа a такой, что a(P1) не может поместиться внутри (P2)и выполнить бинарный поиск по значению a,

Это не очень умно, но, по крайней мере, дает ответ. Если кто-то еще публикует лучший ответ, пожалуйста, игнорируйте мой...