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

@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 - массив прямоугольников (в Вашем случае)

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

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

	Алгоритм разбивки многоугольника с прямыми углами на прямоугольники 01.08.2017, 15:46. Показов 8748. Ответов 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 Айлурофил 509 / 441 / 111 Регистрация: 27.05.2017 Сообщений: 2,647 Записей в блоге: 5
	02.08.2017, 01:10
	Я бы поступил немного по-другому. 1 этап: Берутся 2 соседние точки (в цикле перебор всех вариантов), по ним строится прямая. Определяется, появились ли в результате отрезки, принадлежащие многоугольнику? Если да, то запоминаются. Продолжаем цикл. 2 этап: Получили набор отрезков. Если какие-то из них пересекаются, разбиваем их на подотрезки (оставляя и исходные). Организуем цикл по всем комбинациям отрезков, проверяя - в результате получились только прямоугольники? Далее смотрим: такой комбинации прямоугольников ещё не было? Если оба раза ответ да, то запоминаем комбинацию прямоугольников (координаты?). Продолжаем цикл. 0

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

@Massaraksh7 Айлурофил 509 / 441 / 111 Регистрация: 27.05.2017 Сообщений: 2,647 Записей в блоге: 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 1963 / 819 / 114 Регистрация: 01.10.2012 Сообщений: 4,763 Записей в блоге: 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 Айлурофил 509 / 441 / 111 Регистрация: 27.05.2017 Сообщений: 2,647 Записей в блоге: 5
	04.08.2017, 18:26
	--- Миниатюры 0

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

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

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