Как можно разделить произвольный многоугольник на равные площади?
Имеется многоугольник (ограниченная площадь), и имеется заранее строго заданное количество углов у фигур, которыми требуется разделить эту площадь на равные (по площади) участки.
Подскажите, с помощью какого алгоритма можно осуществить подобное?
Ну вот представим себе отрезки, соединённые между собой в замкнутую область. У каждого из отрезков - есть начало и конец: точки с координатами x и y.
Формат такой (массив точек): [[p1:x1,y1],[p2:x2,y2],.....[pN:xN,yN]]
И массив соединений этих точек: [[p1,p2],[p3,p4],.....[pN,p1]]
что значит сторого заданное количество уголов?
Т.е. при разделении плоскости на многоугольники, они должны содержать не более K-углов.
И массив соединений этих точек: [[p1,p2],[p3,p4],.....[pN,p1]]
А [p2, p3]?
Просто по кругу точки замкнуты, же?
Области на которые мы пилим многоугольник - они могут быть как бублики с дрыками? Иметь анклавы? Или обычные человеческие многугольники, хоть и не выпуклые?
xmoonlight, кстати, не всегда задача имеет решение.
Любой 5-угольник невозможно разделить на два треугольника,
любой 7-угольник невозможно разделить на два 4-угольника, и т.д.
xmoonlight, Очевидный критерий: разбить на n k-или-менее-угольников никогда нельзя (n*k+1)-или-больше-угольник. Потому что все изначальные углы никуда не денутся и по pigeonhole принципу какой-то из n кусков будет более чем k-угольником. Но это если нам так повезет, что мы все границы проводим исключительно хордами и получаем равные по площади куски. Скорее всего придется проводить всякие ломаные да еще и из центров сторон. Поэтому видимо n(k-3) >= количеству вершин в изначальном многоугольнике. Это не обязательное, но, похоже, достаточное условие.
xmoonlight, я прикинул, у меня получилось m<=n*(k-2)+2
т.е. делим 6-угольник (m=6) на три (n=3) треугольника (k=3), получаем облом;
делим 5-угольник на три треугольника - Ok.
xmoonlight, примерно так: выбираем (k-1) вершин очередного куска и выбираем отрезок, на котором находится последняя k-я вершина. Последняя вершина скользит по отрезку, считаем площадь, пока она не станет равна 1/n от площади целого. Стоп, отрезаем. Для оставшейся части повторяем. Т.е. не одним махом делим, а как бы отрезаем по одному куску от торта. Осталось придумать способ выбора (k-1) вершин и одного отрезка. :) Это самая муторная часть (кажется, придётся учитывать кучу частных случаев и т.д.), тут я сваливаю. :)
xmoonlight, сегодня проснулся в 6 утра и понял, что формула m<=n*(k-2)+2 неверна для невыпуклых m-угольников. Пример 6-угольника, который можно разделить на два треугольника:
Критерий, который написал Илья Николаевский работает в общем случае, в том числе и для невыпуклых.
имхо надо упрощать условия и решать какой-то конкретный случай, например разделить исходный многоугольник (с дырками или без?) на равные по площади треугольники - скажем триангуляцией с доп условиями, итеративной, придется придумывать как условия в триангуляцию вбить
"Триангуляция Делоне максимизирует минимальный угол среди всех углов всех построенных треугольников, тем самым избегаются «тонкие» треугольники." - это спец методом сделано чтоб было на выходе именно так, а как вы сделаете чтоб у вас все треугольники были одинаковой площади - при неизвестной площади же - только итеративно?
а автору надо еще разбивать на треугольники (если их выбрали, а не произвольный N) чтобы новые точки не появлялись?
тогда это не триангуляция
а перебор всех вершин
для N-угольников в составке (а не треугольников) - имхо не решаемо в общем случае за разумное время программирования (или будет брутфорс тогда время перебора неразумное)
Очень интересно, ничего не понятно.
В общем случае алгоритм таков:
1. Выбираем точность.
2. Определяем фигуру с заданным количеством углов, чья площадь сравнима с точностью.
3. Заполняем многоугольник фигурами.
Грубо говоря, мы "закрашиваем" исходный многоугольник горошинками.
