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

Question

[xmoonlight]

Имеется многоугольник (ограниченная площадь), и имеется заранее строго заданное количество углов у фигур, которыми требуется разделить эту площадь на равные (по площади) участки.

Подскажите, с помощью какого алгоритма можно осуществить подобное?

Comments

[Wataru]

Можно пример входных данных? что значит сторого заданное количество уголов?

Например, дан прямоугольник надо разделить его на 4 равные по площади: четырех-угольник, 2 треугольника и пятиугольник.

Выпоклый ли изначальный многоугольник? Части должны быть односвязные? Выпуклые?

[xmoonlight]

Илья Николаевский,

Можно пример входных данных?

Ну вот представим себе отрезки, соединённые между собой в замкнутую область. У каждого из отрезков - есть начало и конец: точки с координатами x и y.
Формат такой (массив точек): [[p1:x1,y1],[p2:x2,y2],.....[pN:xN,yN]]
И массив соединений этих точек: [[p1,p2],[p3,p4],.....[pN,p1]]

что значит сторого заданное количество уголов?

Т.е. при разделении плоскости на многоугольники, они должны содержать не более K-углов.

Выпоклый ли изначальный многоугольник?

произвольный

Части должны быть односвязные?

не особо тут понял...

Выпуклые?

произвольные

[Wataru]

xmoonlight,

И массив соединений этих точек: [[p1,p2],[p3,p4],.....[pN,p1]]

А [p2, p3]?

Просто по кругу точки замкнуты, же?

Области на которые мы пилим многоугольник - они могут быть как бублики с дрыками? Иметь анклавы? Или обычные человеческие многугольники, хоть и не выпуклые?

[xmoonlight]

Илья Николаевский,

А [p2, p3]?
Просто по кругу точки замкнуты, же?

да, я пропустил просто)

Области на которые мы пилим многоугольник - они могут быть как бублики с дрыками?

площадь должна использоваться вся.

Иметь анклавы? Или обычные человеческие многугольники, хоть и не выпуклые?

про анклавы - поясни тут...

[Wataru]

xmoonlight,

про анклавы - поясни тут...

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

Или как калининградская область - часть россии, но с ней несвязана.

Но видимо, у вас области нормальные, хоти и не выпуклые.

Вопрос - на сколько частей пилить тоже строго задано?

[xmoonlight]

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

Давай тогда в почте лучше продолжим обсуждение..
Напиши мне (на [e-mail]) и я отвечу, как нарисую.

[hint000]

xmoonlight, кстати, не всегда задача имеет решение.
Любой 5-угольник невозможно разделить на два треугольника,
любой 7-угольник невозможно разделить на два 4-угольника, и т.д.

[xmoonlight]

hint000, т.е. как-то сразу это можно проанализировать?

[Wataru]

xmoonlight, Очевидный критерий: разбить на n k-или-менее-угольников никогда нельзя (n*k+1)-или-больше-угольник. Потому что все изначальные углы никуда не денутся и по pigeonhole принципу какой-то из n кусков будет более чем k-угольником. Но это если нам так повезет, что мы все границы проводим исключительно хордами и получаем равные по площади куски. Скорее всего придется проводить всякие ломаные да еще и из центров сторон. Поэтому видимо n(k-3) >= количеству вершин в изначальном многоугольнике. Это не обязательное, но, похоже, достаточное условие.

[hint000]

xmoonlight, я прикинул, у меня получилось m<=n*(k-2)+2
т.е. делим 6-угольник (m=6) на три (n=3) треугольника (k=3), получаем облом;
делим 5-угольник на три треугольника - Ok.

[xmoonlight]

hint000, ну, вроде оно, да... Осталось понять как именно сохранить равные площади.

[hint000]

xmoonlight, примерно так: выбираем (k-1) вершин очередного куска и выбираем отрезок, на котором находится последняя k-я вершина. Последняя вершина скользит по отрезку, считаем площадь, пока она не станет равна 1/n от площади целого. Стоп, отрезаем. Для оставшейся части повторяем. Т.е. не одним махом делим, а как бы отрезаем по одному куску от торта. Осталось придумать способ выбора (k-1) вершин и одного отрезка. :) Это самая муторная часть (кажется, придётся учитывать кучу частных случаев и т.д.), тут я сваливаю. :)

[xmoonlight]

hint000, Спасибо!

тут я сваливаю. :)

Главное - вовремя!)

[hint000]

xmoonlight, сегодня проснулся в 6 утра и понял, что формула m<=n*(k-2)+2 неверна для невыпуклых m-угольников. Пример 6-угольника, который можно разделить на два треугольника:

Критерий, который написал Илья Николаевский работает в общем случае, в том числе и для невыпуклых.

[xmoonlight]

hint000, Да уж.. На вид - простое условие, а сколько проблем....

[Wataru]

hint000, Я же и написал, что это достаточное условие, но не необходимое.

[AlexHell]

имхо надо упрощать условия и решать какой-то конкретный случай, например разделить исходный многоугольник (с дырками или без?) на равные по площади треугольники - скажем триангуляцией с доп условиями, итеративной, придется придумывать как условия в триангуляцию вбить

"Триангуляция Делоне максимизирует минимальный угол среди всех углов всех построенных треугольников, тем самым избегаются «тонкие» треугольники." - это спец методом сделано чтоб было на выходе именно так, а как вы сделаете чтоб у вас все треугольники были одинаковой площади - при неизвестной площади же - только итеративно?

а автору надо еще разбивать на треугольники (если их выбрали, а не произвольный N) чтобы новые точки не появлялись?
тогда это не триангуляция
а перебор всех вершин

для N-угольников в составке (а не треугольников) - имхо не решаемо в общем случае за разумное время программирования (или будет брутфорс тогда время перебора неразумное)

Answer 1

[Griboks]

Очень интересно, ничего не понятно.
В общем случае алгоритм таков:
1. Выбираем точность.
2. Определяем фигуру с заданным количеством углов, чья площадь сравнима с точностью.
3. Заполняем многоугольник фигурами.

Грубо говоря, мы "закрашиваем" исходный многоугольник горошинками.