Учитывая два выпуклых многоугольника в 2D-пространстве, как бы вы пошли на построение отрезка (ей) линии, который в любой точке линий равноудален от ближайшей точки любого выпуклого многоугольника?
Я рассчитываю на реализацию диаграмм Вороного для выпуклых многоугольников вместо точек, но я не уверен, как даже начать вычисление линии только для двух многоугольников. Так что я решила сделать один шаг за раз и начать здесь.
Редактировать Чтобы попытаться прояснить вопрос, я хочу разделить плоскость (или ее подмножество).
Предположим, у нас есть многоугольник A слева и многоугольник B справа. Будет некоторая линия деления пополам, которая делит плоскость на точки слева и точки справа. Каждая точка на линии одинаково удалена от любого многоугольника. Каждая точка слева от линии ближе к многоугольнику A, чем к многоугольнику B. Каждая точка справа от линии ближе всего к многоугольнику B.
Вот изображение, сгенерированное сценарием Matlab, которое я написал, что грубой силой является приближение:
Я полагаю, что проблема не так проста, как проверка пространства между двумя полигонами, поскольку линия должна проходить за пределы области, непосредственно между двумя фигурами. И в идеале я хотел бы найти решение, которое обобщает более двух форм, что, на мой взгляд, значительно усложняет проблему. Вот (очевидно, очень грубое) приближение того, как это может выглядеть:
