Как минимизировать максимальное соотношение сторон двух субполигонов?

Question

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

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

Соотношение сторон многоугольника A определяется как:

asp(A) := diam(A)^2 / area(A)

Answer 1

Метод, над которым я работал, очень похож на Велизария, поэтому я поделюсь лишь несколькими заметками о своем мышлении (я использую Mathematica).

• Количество пар ребер, в которых может быть размещен разрез, квадратично равно числу вершин (1/2 n (n-1)): (линии обозначают пары ребер, соединяя начальныевершины каждой пары)

Желтые области обозначают область, в которой можно найти разрез:

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

- Как сказал Велисарий, вы можете найти диапазон соотношений площадей для каждой из вышеперечисленных ситуаций, но просто взять Min и Max неверно.Два диапазона, которые вы получаете, когда вы изменяете две области в вашем соотношении площадей, могут быть разделены.Я использую арифметику Mathematica Interval, чтобы справиться с этим для меня:

Проверка того, обрабатывается ли заданное соотношение площадей с удобной функцией Interval:

containsRatioQ[area1_, area2_, areaBetween_, ratio_] := 
 IntervalMemberQ[areaRatioInterval[area1, area2, areaBetween], ratio]

• Значение параметра labma labda, определяющего местоположение разреза через первый край, в зависимости от mu (параметр, определяющий положение второго края)

  \[Lambda] -> (2*aL + givenAreaRatio*(-2* aR + (p1y - p3y)*(p2x - p4x) - (p1x - p3x)*(p2y - p4y)) + (1 + givenAreaRatio)*(p1x*p3y - p3y*p4x + p1y*(-p3x + p4x) - p1x*p4y + p3x*p4y)*\[Mu])/ ((1 + givenAreaRatio)*((-p2x)*p4y + p1x*(-p2y + p4y) + (p1x - p2x)*(p3y - p4y)*\[Mu] + p1y*(p2x + p4x*(-1 + \[Mu]) - p3x*\[Mu]) + p2y*(p4x + p3x*\[Mu] - p4x*\[Mu])))

или мю как функция от labda:

\[Mu] -> (-2*aL + givenAreaRatio*(2*
       aR - (p1y - p3y)*(p2x - p4x) + (p1x - p3x)*(p2y - p4y)) + (1 + 
      givenAreaRatio)*((-p1x)*p2y + p1y*(p2x - p4x) + p2y*p4x + 
      p1x*p4y - p2x*p4y)*\[Lambda])/
   ((1 + givenAreaRatio)*((-p3y)*p4x + p3x*p4y + 
     p1y*(p3x - p4x)*(-1 + \[Lambda]) - 
     p1x*(p3y - p4y)*(-1 + \[Lambda]) + ((-p2y)*p3x + p2x*p3y + 
        p2y*p4x - p2x*p4y)*\[Lambda]))

с p1, p2, p3, p4 координатами области, охватывающей разрез, и всей области«зеленого» многоугольника и область «красного» многоугольника (см. рисунок внизу этого поста).

• Не каждая точка на одном ребре всегда дает решение длядругой край и наоборот.Я проверяю уравнение для лямбды, чтобы найти значения mu, которые устанавливают лямбду в 0 или 1, и наоборот.

• В качестве последнего шага я минимизирую максимальное значение функций соотношения сторон:две области.На языке Mathematica:

  NMinimize[{Max[aspectRatio[area1tot], aspectRatio[area2tot]], \[Mu]range[[1]] <= \[Mu] <= \[Mu]range[[2]]}, \[Mu]]

, где are1tot и area2tot - это общие площади для обеих половин, параметризованных mu и lambda, и где лямбда заменяется приведенным выше уравнениемдля лямбда с точки зрения му.Теперь у нас остался только один параметр

• Вот результат процедуры минимизации для соотношения площадей 1. Зеленая кривая - это соотношение сторон для зеленого многоугольника (+ добавленная площадь в зависимости от мю)а красная кривая - это соотношение сторон для красного многоугольника (+ добавленная область в зависимости от му).

• И вот, наконец, вашсамый приятный 'полигональный разрез:

У меня есть блокнот Mathematica, который я отправлю по запросу.Просто пришлите мне электронное письмо.

Answer 2

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

Проблема состоит из двух частей:

• Найдите многоугольные перегородки, которые дают желаемое соотношение площади
• Выберите из них тот, который минимизирует соотношение сторон

Давайте сначала посмотрим на первую проблему. Вы можете сделать что-то вроде:

Рассмотрим каждую пару сторон, как показано на следующем рисунке

И для каждой пары рассмотрим три следующие области:

Таким образом, максимальные и минимальные отношения, которые вы можете получить для разбиения многоугольника с линией, пересекающей эти две стороны, составляют Min() и Max[] из следующего набора:

 { (S1+S2)/S3, S3/(S1+S2), (S2+S3)/S1, S1/(S2+S3) }

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

Примечание: Для расчета площадей вы можете использовать эту формулу

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

Если вы параметризовали обе стороны уравнением, подобным

{x, y} = {A} + t {B- A} 

вы сможете получить что-то вроде этого:

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

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

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

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

здесь вы можете увидеть результаты для соотношения сторон для шестиугольника, взяв одну вершину в качестве точки разделения следующим образом:

А график соотношения сторон для каждой области:

Где каждая единица на оси x соответствует одной стороне.

Дайте мне знать, если вы хотите больше подробностей ...