Алгоритм разбивки многоугольника с прямыми углами на прямоугольники

@Modis · Регистрация: 20.01.2011

Студворк — интернет-сервис помощи студентам

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

@Modis · 01.08.2017, 17:17 **[ТС]**

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

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

@Excalibur921 · 01.08.2017, 17:42

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

@Modis · 01.08.2017, 21:08 **[ТС]**

Сообщение от Excalibur921

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

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

@Massaraksh7 · 02.08.2017, 01:10

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

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

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

@Massaraksh7 · 02.08.2017, 01:20

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

@Massaraksh7 · 02.08.2017, 01:30

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

@Excalibur921 · 02.08.2017, 17:49

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

@Igor3D · 03.08.2017, 10:41

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

@Rolldan · 04.08.2017, 17:17

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

@Modis · 04.08.2017, 17:37 **[ТС]**

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

@Rolldan · 04.08.2017, 17:49

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

@Modis · 04.08.2017, 17:55 **[ТС]**

Сообщение от cordfield

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

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

@Massaraksh7 · 04.08.2017, 18:08

Сообщение от Modis

Да, возможно задача немного специфичная.

Это Вы дипломатично выразились. Я бы уточнил - ошибочная изначальная постановка задачи.

Сообщение от Modis

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

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

@Massaraksh7 · 04.08.2017, 18:26

---

@Shamil1 · 05.08.2017, 17:58

Сообщение от Modis

(в топике картинка с таким же условием)

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

@Modis · 07.08.2017, 15:08 **[ТС]**

Сообщение от Massaraksh7

---

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

@Massaraksh7 · 07.08.2017, 15:50

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

@Modis · 07.08.2017, 16:56 **[ТС]**

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

@Massaraksh7 · 07.08.2017, 17:09

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

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

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

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: показать затраченные материалы за определенный период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В качестве. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

@Modis 5 / 5 / 4 Регистрация: 20.01.2011 Сообщений: 350

	Алгоритм разбивки многоугольника с прямыми углами на прямоугольники 01.08.2017, 15:46. Показов 9008. Ответов 21 Метки нет (Все метки) Всем привет. Все пытаюсь нагуглить информацию по теме, но кругом одна сплошная триангуляция. Мой задача проще - имеется многоугольник, у которого все угля прямые. Нужно разбить его на прямоугольники, получив при этом все варианты. На картинке я отрисовал пример Уверен, что готовые алгоритмы есть и описаны, просто не могу найти Миниатюры 0

@Modis 5 / 5 / 4 Регистрация: 20.01.2011 Сообщений: 350
	01.08.2017, 17:17 [ТС]
	На данный момент начну прорабатывать примерно такой алгоритм: 1. Беру три точки подряд. Строю по ним прямоугольник. Пока не уверен в правильности, но идея такая: 4 точку создаю по X первой точки и Y третьей точки. 2. Проверяю полученную точку на условие попадания "внутрь" исходного многоугольника. Если попадает, то это нужная точка - строю прямоугольник. (Уточнение - можно проверять не то, что лежит "внутри", а то, что лежит на одной из граней исходного многоугольника) 3. Проверяю полученный прямоугольник на условие, что площадь меньше исходного. (данная проверка нужна в случае, который не показан на картинке в топике) 4. Если прямоугольник прошёл условие - запомнил его. В итоге имею набор прямоугольников, которые нужно разобрать на "варианты". Для этого нужно проверить на несколько условий: 1. Прямоугольники имеют не более одной общей вершины 2. Не придумал... =)) Вот такая идея. Надеюсь на комментарии по теме 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	01.08.2017, 17:42
	Гляньте “Similar Threads” внизу темы, выдает похожие темы. Видать кем-то запилен некий ИИ который ищет по ключевым словам и почти никто не юзает его… может написать админу кидать вверх этот список? Разбиение фигуры с тупыми углами на произвольным прямоугольники 0

@Massaraksh7 Айлурофил 516 / 449 / 112 Регистрация: 27.05.2017 Сообщений: 2,716 Записей в блоге: 5
	02.08.2017, 01:10
	Я бы поступил немного по-другому. 1 этап: Берутся 2 соседние точки (в цикле перебор всех вариантов), по ним строится прямая. Определяется, появились ли в результате отрезки, принадлежащие многоугольнику? Если да, то запоминаются. Продолжаем цикл. 2 этап: Получили набор отрезков. Если какие-то из них пересекаются, разбиваем их на подотрезки (оставляя и исходные). Организуем цикл по всем комбинациям отрезков, проверяя - в результате получились только прямоугольники? Далее смотрим: такой комбинации прямоугольников ещё не было? Если оба раза ответ да, то запоминаем комбинацию прямоугольников (координаты?). Продолжаем цикл. 0

@Massaraksh7 Айлурофил 516 / 449 / 112 Регистрация: 27.05.2017 Сообщений: 2,716 Записей в блоге: 5
	02.08.2017, 01:20
	Вот здесь, например, получаем 8 отрезков. И перебираем все их комбинации. Таких комбинаций будет C₈¹+C₈²+C₈³+C₈⁴+C₈⁵+C₈⁶+C₈⁷+C₈⁸=255 Да, не очень оптимально, но первое, что пришло в голову. Миниатюры 0

@Massaraksh7 Айлурофил 516 / 449 / 112 Регистрация: 27.05.2017 Сообщений: 2,716 Записей в блоге: 5
	02.08.2017, 01:30
	Ну, ещё можно оптимизировать, но это по ходу дела. 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	02.08.2017, 17:49
	А зачем надо так разбивать? Изначальная цель? Может в этой отрасли гуглить. Или подойти с противоположной стороны. Поиск в гугле зачем то по словам “rectangle packing” =) https://www.youtube.com/watch?v=B7Bfh1NgeEM 0

@Igor3D 1974 / 830 / 115 Регистрация: 01.10.2012 Сообщений: 5,018 Записей в блоге: 2
	03.08.2017, 10:41
	Думается первый проход - наложить "сетку" (в данном случае нерегулярную). Проходим по всем углам и если x и/или y не лежат на вмещающем пр-ке - добавляем их в сортированные контейнеры сеток y и/или x 0

@Rolldan 44 / 44 / 19 Регистрация: 04.05.2014 Сообщений: 190
	04.08.2017, 17:17
	1. Для каждой стороны многоугольника 1.2. взять 2 смежные стороны 1.3. если смежные стороны направлены в противоположные направления, пропустить дальнейшие этапы и перейти к следующей стороне многоугольника (п. 1) 1.3. выбрать наименьшую из 2 смежных сторон 1.4. построить из исходной и выбранной смежной стороны прямоугольник 1.5. вычесть из исходной фигуры полученный прямоугольник 1.6. если в результате получился ненулевой многоугольник, выполнить действие (п.1) для нового многоугольника 1.7. иначе записать последовательность прямоугольников, которые мы вычитали, чтобы получить в конце нулевой многоугольник 0

@Modis 5 / 5 / 4 Регистрация: 20.01.2011 Сообщений: 350
	04.08.2017, 17:37 [ТС]
	Вот вариант многоугольника в котором не будут работать все вышеописанные алгоритмы Миниатюры 0

@Rolldan 44 / 44 / 19 Регистрация: 04.05.2014 Сообщений: 190
	04.08.2017, 17:49
	Modis, определите для начала, на какие прямоугольники позволяют нарезать фигуру. Это уже будет половина решения задачи. А то ведь можно каждый прямоугольник любого решения разрезать напополам, и это тоже будет разбивкой многоугольника на прямоугольники, разве не так? В этом случае решений бесконечно много. 0

@Massaraksh7 Айлурофил 516 / 449 / 112 Регистрация: 27.05.2017 Сообщений: 2,716 Записей в блоге: 5
	04.08.2017, 18:26
	--- Миниатюры 0

@Massaraksh7 Айлурофил 516 / 449 / 112 Регистрация: 27.05.2017 Сообщений: 2,716 Записей в блоге: 5
	07.08.2017, 15:50
	Есть такой алгоритм, он более общий, но для данного частного случая сойдёт. Алгоритм поиска элементарных циклов в неориентированном графе 0

@Modis 5 / 5 / 4 Регистрация: 20.01.2011 Сообщений: 350
	07.08.2017, 16:56 [ТС]
	Я вот чувствую, что где-то уже рядом, но на самом финале застрял Я могу в изначальную фигуру добавить дополнительные отрезки. Если из этих дополнительных отрезков оставить только горизонтальные или только вертикальные, то как раз и получается нужный результат. Т.е. я его ГЛАЗАМИ вижу! Но вот как программно "вычленить" эти прямоугольники - ума не приложу. По ссылке, что выше, вообще ничего не понял - у меня нет такого обширного опыта программирования и знания теорий Миниатюры 0

@Massaraksh7 Айлурофил 516 / 449 / 112 Регистрация: 27.05.2017 Сообщений: 2,716 Записей в блоге: 5
	07.08.2017, 17:09
	Там код приведён. Для его выполнения нужно пронумеровать вершины, заполнить массив их координат, и массив связывающих их отрезков. На выходе получается массив структур с прямоугольниками (в Вашем случае). Добавлено через 6 минут xa,ya - координаты вершин (нумерация с 0), np-число вершин seg - массив отрезков, напр. seg[0,0] - номер первой вершины 1-го отрезка, seg[1,0] - номер второй 1-го отрезка и т.д. nseg - число отрезков На выходе Circles - массив прямоугольников (в Вашем случае) 0