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

Question

Учитывая выпуклый многоугольник P и точку A на границе P, как мне вычислить точку B также на границе P, чтобы AB разбивал P на две области заданной пропорции?

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

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

Answer 1

Разделите многоугольник на треугольники из точки А и рассчитайте их площади.Затем вы можете добавить треугольники с каждого конца к каждому многоугольнику в зависимости от их пропорций, пока не останется только один треугольник.Тогда вы знаете, что точка B находится где-то на основании этого треугольника.

Answer 2

Как часто бывает, я ответил на свой вопрос только через несколько минут после его публикации!

Мой код для определения того, между какими точками B должно идти, выглядит примерно так:

while areaSoFar + areas[i] < targetArea:
    i++
    areaSoFar += areas[i]

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

while areaSoFar + areas[i] + points[i].x * start.y - points[i].y * start.x < targetArea:
    i++
    areaSoFar += areas[i]

Обратите внимание, что приведенный выше массив областей [] содержит каждый элемент суммирования областейформула .

По духу это похоже на ответ Гуффы, но несколько эффективнее.