@Modis

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

Миниатюры

 

0

@Modis

На данный момент начну прорабатывать примерно такой алгоритм:
1. Беру три точки подряд. Строю по ним прямоугольник. Пока не уверен в правильности, но идея такая: 4 точку создаю по X первой точки и Y третьей точки.
2. Проверяю полученную точку на условие попадания "внутрь" исходного многоугольника. Если попадает, то это нужная точка - строю прямоугольник. (Уточнение - можно проверять не то, что лежит "внутри", а то, что лежит на одной из граней исходного многоугольника)
3. Проверяю полученный прямоугольник на условие, что площадь меньше исходного. (данная проверка нужна в случае, который не показан на картинке в топике)
4. Если прямоугольник прошёл условие - запомнил его.
В итоге имею набор прямоугольников, которые нужно разобрать на "варианты". Для этого нужно проверить на несколько условий:
1. Прямоугольники имеют не более одной общей вершины
2. Не придумал... =))

Вот такая идея. Надеюсь на комментарии по теме

0

@Excalibur921

Гляньте “Similar Threads” внизу темы, выдает похожие темы. Видать кем-то запилен некий ИИ который ищет по ключевым словам и почти никто не юзает его… может написать админу кидать вверх этот список?
Разбиение фигуры с тупыми углами на произвольным прямоугольники

0

@Modis

Я на 90% уверен, что это неподходящий вариант. Посмотрите на картинку в топике - многоугольник можно разбить на прямоугольники несколькими вариантами. А там жёстко один вариант

0

@Massaraksh7

Я бы поступил немного по-другому.

1 этап:
Берутся 2 соседние точки (в цикле перебор всех вариантов), по ним строится прямая.
Определяется, появились ли в результате отрезки, принадлежащие многоугольнику? Если да, то запоминаются.
Продолжаем цикл.

2 этап:
Получили набор отрезков. Если какие-то из них пересекаются, разбиваем их на подотрезки (оставляя и исходные).
Организуем цикл по всем комбинациям отрезков, проверяя - в результате получились только прямоугольники?
Далее смотрим: такой комбинации прямоугольников ещё не было?
Если оба раза ответ да, то запоминаем комбинацию прямоугольников (координаты?).
Продолжаем цикл.

0

@Massaraksh7

Вот здесь, например, получаем 8 отрезков. И перебираем все их комбинации.
Таких комбинаций будет
C₈¹+C₈²+C₈³+C₈⁴+C₈⁵+C₈⁶+C₈⁷+C₈⁸=255
Да, не очень оптимально, но первое, что пришло в голову.

Миниатюры

 

0

@Massaraksh7

Ну, ещё можно оптимизировать, но это по ходу дела.

0

@Excalibur921

А зачем надо так разбивать? Изначальная цель? Может в этой отрасли гуглить.
Или подойти с противоположной стороны.
Поиск в гугле зачем то по словам “rectangle packing” =)
https://www.youtube.com/watch?v=B7Bfh1NgeEM

0

@Igor3D

Думается первый проход - наложить "сетку" (в данном случае нерегулярную). Проходим по всем углам и если x и/или y не лежат на вмещающем пр-ке - добавляем их в сортированные контейнеры сеток y и/или x

0

@Rolldan

1. Для каждой стороны многоугольника
1.2. взять 2 смежные стороны
1.3. если смежные стороны направлены в противоположные направления, пропустить дальнейшие этапы и перейти к следующей стороне многоугольника (п. 1)
1.3. выбрать наименьшую из 2 смежных сторон
1.4. построить из исходной и выбранной смежной стороны прямоугольник
1.5. вычесть из исходной фигуры полученный прямоугольник
1.6. если в результате получился ненулевой многоугольник, выполнить действие (п.1) для нового многоугольника
1.7. иначе записать последовательность прямоугольников, которые мы вычитали, чтобы получить в конце нулевой многоугольник

0

@Modis

Вот вариант многоугольника в котором не будут работать все вышеописанные алгоритмы

Миниатюры

 

0

@Rolldan

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

0

@Modis

Да, возможно задача немного специфичная.
Нужно разбить многоугольник на "горизонтальные" и "вертикальные" прямоугольники. Вариантов всегда два получается. Не знаю как точнее объяснить - надеюсь по картинке будет понятно (в топике картинка с таким же условием)

Миниатюры

 

0

@Massaraksh7

Это Вы дипломатично выразились. Я бы уточнил - ошибочная изначальная постановка задачи.
Описанный мной алгоритм будет работать, но по вновь открывшимся обстоятельствам его необходимо скорректировать. И он будет сильно проще.
А именно:
Находим все вертикальные и горизонтальные отрезки отдельно.
И применяем их. Если сразу все, то варианта всегда будет только 2. Если в комбинациях, то вариантов будет больше.

1

@Massaraksh7

---

Миниатюры

 

0

@Shamil1

Непонятно, почему на правую картинку нельзя добавить один или два горизонтальных разреза (как на левой картинке).

0

@Modis

Вопрос - как правильно теперь собрать всего горизонтальные и все вертикальные линии в прямоугольники?

0

@Massaraksh7

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

0

@Modis

Я вот чувствую, что где-то уже рядом, но на самом финале застрял
Я могу в изначальную фигуру добавить дополнительные отрезки. Если из этих дополнительных отрезков оставить только горизонтальные или только вертикальные, то как раз и получается нужный результат. Т.е. я его ГЛАЗАМИ вижу! Но вот как программно "вычленить" эти прямоугольники - ума не приложу.
По ссылке, что выше, вообще ничего не понял - у меня нет такого обширного опыта программирования и знания теорий

Миниатюры

 

0

@Massaraksh7

Там код приведён. Для его выполнения нужно пронумеровать вершины, заполнить массив их координат, и массив связывающих их отрезков. На выходе получается массив структур с прямоугольниками (в Вашем случае).

Добавлено через 6 минут
xa,ya - координаты вершин (нумерация с 0), np-число вершин
seg - массив отрезков, напр. seg[0,0] - номер первой вершины 1-го отрезка, seg[1,0] - номер второй 1-го отрезка и т.д.
nseg - число отрезков

На выходе Circles - массив прямоугольников (в Вашем случае)

0