crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

 
Ответить в данную темуНачать новую тему
> Распределение прямоугольников в прямоугольнике
ufna
  опции профиля:
сообщение 17.7.2009, 13:39
Сообщение #1


Активный участник
***

Группа: Участник
Сообщений: 362
Регистрация: 24.5.2008
Из: Курган/СПб
Пользователь №: 182

Спасибо сказали: 29 раз(а)




Репутация:   5  


В общем, суть какая - есть прямоугольники, размеры их четко заданы. Могут быть повернуты на 90 градусов. Нужно их разместить на другом прямоугольнике, либо доказать что такого размещения нет.

Я с таким типом алгоритмов не работал, не подскажете куда копать?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
AD
  опции профиля:
сообщение 17.7.2009, 14:00
Сообщение #2


Профессионал
*****

Группа: Участник
Сообщений: 2003
Регистрация: 4.2.2008
Из: S-Petersburg
Пользователь №: 84

Спасибо сказали: 70 раз(а)




Репутация:   17  


Цитата(ufna @ 17.7.2009, 14:39) *
В общем, суть какая - есть прямоугольники, размеры их четко заданы. Могут быть повернуты на 90 градусов. Нужно их разместить на другом прямоугольнике, либо доказать что такого размещения нет.

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

Суть такая: следует проверить, входит ли один прямоугольник в другой или же нет! Такие операции есть у QRect в Qt. Или же Вам надо самому это реализовать?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ufna
  опции профиля:
сообщение 17.7.2009, 14:16
Сообщение #3


Активный участник
***

Группа: Участник
Сообщений: 362
Регистрация: 24.5.2008
Из: Курган/СПб
Пользователь №: 182

Спасибо сказали: 29 раз(а)




Репутация:   5  


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

На другом форуме подсказали что это сие есть packing problem, копаю в эту сторону.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Kagami
  опции профиля:
сообщение 17.7.2009, 15:35
Сообщение #4


Старейший участник
****

Группа: Участник
Сообщений: 601
Регистрация: 2.2.2009
Пользователь №: 523

Спасибо сказали: 101 раз(а)




Репутация:   9  


Грубую оценку можно получить сравнив сумму площадей упаковываемых прямоугольников с площадью контейнера. Можно ввести коэффициент достоверности (0,8-0,9) и умножать сумму площадей на него, что слегка повысит точность оценки.
А так задачу скорее всего придется решать полным перебором, пока не будут опробованы все варианты или не будет найдено первое подходящее решение.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Litkevich Yuriy
  опции профиля:
сообщение 17.7.2009, 16:15
Сообщение #5


разработчик РЭА
*******

Группа: Сомодератор
Сообщений: 9669
Регистрация: 9.1.2008
Из: Тюмень
Пользователь №: 64

Спасибо сказали: 807 раз(а)




Репутация:   94  


Цитата(ufna @ 17.7.2009, 17:39) *
либо доказать что такого размещения нет.
т.е. помещаются ли они в заданный?
И по условию непонятно, как помещаемые прямоугольники, собственно помещаются. Рядом, один в другой или накладываясь друг на друга.

А вообще задача должна быть решена програмным путём, или аналитически?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ufna
  опции профиля:
сообщение 17.7.2009, 17:25
Сообщение #6


Активный участник
***

Группа: Участник
Сообщений: 362
Регистрация: 24.5.2008
Из: Курган/СПб
Пользователь №: 182

Спасибо сказали: 29 раз(а)




Репутация:   5  


Да, либо нужно размещение найти, либо доказать что его нет, с достаточно малой погрешностью.

Помещаемые прямоугольники не могут пересекаться, вращение допустимо только на 90 градусов.

Решение нужно программное, т.к. это цель автозаполнителя поля.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Tonal
  опции профиля:
сообщение 21.7.2009, 7:20
Сообщение #7


Активный участник
***

Группа: Участник
Сообщений: 452
Регистрация: 6.12.2007
Из: Новосибирск
Пользователь №: 34

Спасибо сказали: 69 раз(а)




Репутация:   17  


Нужно разместить все или можно не все?
Важен только факт возможности размещения или само размешение тоже важно?
Если важно размещение и можно разместить несколькими способами какое использовать?
Если можно разместить не все, то какое из размещений будет лучшим?

Задача решается полным перебором, но можно придумать ускоряющие эвристики и использовать промежуточные результаты. :)

Сообщение отредактировал Tonal - 21.7.2009, 7:21
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Litkevich Yuriy
  опции профиля:
сообщение 21.7.2009, 11:08
Сообщение #8


разработчик РЭА
*******

Группа: Сомодератор
Сообщений: 9669
Регистрация: 9.1.2008
Из: Тюмень
Пользователь №: 64

Спасибо сказали: 807 раз(а)




Репутация:   94  


вообще было время, когда я учился на машиностроительном факультете. Имя преподователя я сейчас не вспомню, но он посвятил всю жизни изучению вопроса "об оптимальном раскрое листовых заготовок" я думаю это можно взять за ключевые слова для сёрфинга по интернету.
Насколько я помню существует аналитическое решение этой задачи для любых фигур состоящих из примитивных (непомню как они строго называются, толи какого-то рода, толи какого-то порядка)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
kwisp
  опции профиля:
сообщение 21.7.2009, 14:18
Сообщение #9


астарожна ынтжинэр
*****

Группа: Участник
Сообщений: 1404
Регистрация: 26.11.2008
Из: ТаганрогРодинаЧехова
Пользователь №: 435

Спасибо сказали: 113 раз(а)




Репутация:   23  


Цитата(Tonal @ 21.7.2009, 8:20) *
Задача решается полным перебором,

это как?
если количество n совершенно разных габаритных размеров прямоугольников да еще каждый можно повернуть на 90 градусов.
учитывая положение прямоугольника относительно других, сколько же будет вариантов для осуществления полного перебора?

задачка я вам скажу не тривиальная.
если не ошибаюсь на этом построен один из методов шифрования. нам препод, показывал как легко разрезать открытку на n фигур и как становится тяжело собрать при увеличении числа n. функции подобного рода имеют даже свое название в математике.

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

Сообщение отредактировал kwisp - 21.7.2009, 14:34
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ufna
  опции профиля:
сообщение 21.7.2009, 22:49
Сообщение #10


Активный участник
***

Группа: Участник
Сообщений: 362
Регистрация: 24.5.2008
Из: Курган/СПб
Пользователь №: 182

Спасибо сказали: 29 раз(а)




Репутация:   5  


Закопался в эту задачу, тут нужна нехилая математика. Фишку эту требовал заказчик, т.к. в программе-"идейном вдохновителе это было". Короче, про математику не буду, там разные варианты есть, в том числе и перебор. Нашел кое-что на эту тему, только на С#, если кому интересно, могу поделиться.

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

Всем спасибо, т.к. заставили много думать над идеями :)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

Быстрый ответОтветить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 27.12.2024, 16:37