Сгладьте выпуклую многоугольную форму, чтобы она стала как можно больше при сохранении диаметра.

Оказывается, этот вопрос уже задавали на Math Overflow, и люди пришли к выводу, что это сложная задача. Есть даже несколько основных вопросов без ответа, например, уникальна ли такая форма.

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

Задний план

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

Об одном обобщении теоремы Бляшке-Лебега для диско- многоугольники (М. Бездек, 2009 г.) описывает ряд полезных концепций. Соответствующие включают:

• диск-многоугольник - это, неформально, выпуклое множество, которое образует «толстый» многоугольник, в котором ребра заменены дугами кривизны 1.
• набор точек, которые мы можем добавить к набору точек D так, чтобы получившаяся фигура имела диаметр не более 1, называется двойным дисковым многоугольником D* из < эм>Д.
• двойственное к двойственному D** называется выпуклой оболочкой веретена D: это наименьший дисковый многоугольник, содержащий D.

Вместо работы с многоугольниками достаточно работать с многоугольниками-дисками: мы всегда можем заменить исходный многоугольник его веретенообразной выпуклой оболочкой без изменения результата.

У нас есть D ⊆ D*, когда D имеет диаметр 1 и D = D*< /em> тогда и только тогда, когда D имеет постоянную ширину 1. Решение S будет иметь постоянную ширину 1 (хотя этого, конечно, недостаточно). Следовательно, D ⊆ S тогда и только тогда, когда D ⊆ S ⊆ D*: в частности, чтобы аппроксимировать S, нам нужно только найти достаточно большое подмножество дисковых полигонов D в S. Это очень мощно, потому что, как мы увидим, утверждение о том, что некоторая точка принадлежит или не принадлежит S, преобразуется как в верхнюю границу , так и в нижнюю границу S (и, следовательно, его площадь).

Глобальный поиск.
Начните со шпиндельной выпуклой оболочки многоугольника и лениво постройте бесконечное дерево поиска из растущих дисковых многоугольников, где каждый узел разбивает набор всех постоянной ширины X. удовлетворяющие D ⊆ X ⊆ D*, в зависимости от того, является ли некоторая точка x из D* \ D принадлежит или не принадлежит X. Левая ветвь — это выпуклая оболочка веретена D ∪ {x}. Правая ветвь — это двойственный круг-многоугольник D* ∩ {y : x ∉ [y, < em>z] для всех z в D}.

Если вы не выбрали x очень неудачно (например, на границе D* \ D), каждый бесконечный путь этого дерева должен сходиться к константе - ширина кривой.

Идея состоит в том, чтобы исследовать дерево несколько вширь. Надеюсь, если x выбрать разумным образом, вы сможете отбросить все ветви, где D* имеет меньшую площадь, чем наибольшая площадь D найдено пока, так как такие ветки не могут содержать решения. Тогда у вас будет набор дисковых полигонов, которые сходятся к набору решений проблемы по мере того, как вы углубляетесь в дерево, надеюсь, не слишком быстро.

Некоторыми эвристиками для x могут быть: взять точку как можно ближе к внутренней части D* \ D, взять случайную точку и скоро. Также может быть интересно включить некоторое количество поиска в глубину, чтобы иметь более точные нижние границы области решения, что позволило бы раньше отбрасывать целые ветви дерева.

Локальный поиск:
Мы также могли работать только с дисковыми многоугольниками постоянной ширины (полигонами Рело) и смотреть на влияние небольших отклонений. Но пространство поиска довольно большое, поэтому непонятно, как это сделать.

Вычисление пересечения проще, чем кажется; все, что вам действительно нужно сделать, это определить точку, равноудаленную от двух соседних вершин; вы получите две точки, но та, которая находится ближе всего к центру фигуры, почти наверняка будет правильной; Это может быть даже гарантировано для выпуклых многоугольников, но математические доказательства не являются моей сильной стороной.

Мне кажется, что ваш нынешний алгоритм не только неэффективен, но и неверен. Возьмите прямоугольник (0,0)-(10,0)-(10,1)-(0,1), который в настоящее время имеет диаметр чуть больше 10. Пересеките круги с этим радиусом по всему углу, и вы получите довольно большую линзообразную вещь с диаметром, значительно превышающим 16. Таким образом, этот алгоритм не работает.

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

Это просто интуиция, но я сомневаюсь, что желаемый результат однозначно определяется входным полигоном и вашими требованиями. Хотя у меня еще нет примера на этот счет, я полагаю, что могут быть входные полигоны, для которых существует несколько «сглаженных» форм, все с одинаковой площадью и одинаковым диаметром, но все же не конгруэнтные друг другу. Возможно, стоит обратиться к бирже математических стеков для дальнейшего обсуждения этого экзистенциального вопроса.