Ответ 1
Мотивация.. Если вы спросите, может ли диск B определенного радиуса вписаться в многоугольник P, тогда существует стандартный метод в вычислительная геометрия: проверьте, имеет ли максимальная вписанная окружность радиус не меньше; см. fooobar.com/questions/184860/...:
Вышеупомянутый алгоритм вычисления максимальной вписанной окружности довольно "прост": вычислите так называемую Обобщенную диаграмму Вороного и возьмите Voronoi node с наибольшим радиусом зазора. (Это только мотивация, просто продолжайте читать в течение минуты.)
В вашем случае ваша фигура 2 не является мячиком; ну, точнее, не эвклидовым шаром. Но на самом деле ваша фигура 2, как выпуклый многоугольник B, может определять функцию выпуклого расстояния и вычислять диаграмму Вороной в этой многогранной дистанционной функции , Но это более теоретический фон и, возможно, не то, что вы хотите реализовать для производственного кода.
Эти диаграммы Voronoi сильно связаны с вычислением кривых смещения, например, для строгания траектории инструмента при NC-механической обработке. См. Эту статью статью в блоге для обсуждения и следующий рисунок:
Шар B радиуса r вписывается в форму P тогда и только тогда, когда на расстоянии r имеется кривая смещения. (Фактически вы получаете набор всех действительных центров, а именно тех, которые находятся на кривой смещения в радиусе r.) И эти кривые смещения могут быть математически описаны как разница Минковского, как указано в статье в блоге.
Минковский-разница. Итак, теперь мы можем вернуться к вашей первоначальной проблеме. Выпускается ли выпуклый многоугольник B внутри многоугольника P? Оно выполняется тогда и только тогда, когда разность Минковского (P-B) является непустым множеством; в качестве примера можно использовать любой центр из (P-B).
Несколько деталей, основанных на приведенном выше рисунке: Обозначим через -B = {-v: v в B} форму B после точечного отражения. (Выберите источник где угодно, я обозначил его маленьким крестом с "o" для происхождения.) Теперь подумайте о -B как о форме пера (синий), и вы переместите перо (на самом деле крест) вдоль границы из P. Вы получаете серое пространство. (Это сумма Минковского границы P с -B.) Удалите серое пространство из P, и вы получите разницу Минковского P-B. Выберите любую точку внутри P-B и поместите туда копию B; он будет вписываться в P. Я поместил несколько копий (оранжевый) для вас.
Реализация. Вы можете построить серое пространство, рассматривая каждый сегмент s из P отдельно и соединяя его вдоль B. Точнее, вы помещаете копию -B на каждую конечную точку s и находите касательные двух копий -B, которые образуют границу серой области:
Возьмите решения на сегменты и вычислите объединение по всем сегментам P. Затем вычтите это объединение из P. Посмотрите Clipper для библиотеки с открытым исходным кодом, которая может сделать это для вас.
То, что вы получаете, - это не только логический ответ, если B вписывается в P, а множество всех действительных центров для B в виде множества полигонов. Возможно, это тоже интересно для вашего приложения.
Если вы также допускаете поворот B, то проблема становится значительно более сложной, я думаю. Возможно, вы можете работать с некоторой дискретизацией вращательных углов. Возможно, вы найдете какое-то решение в области планирования движения роботов и. связанный с проблемой проблемой пианино в вычислительной геометрии.