Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / [Алгоритм] Упаковка кругов разного размера в прямоугольник

[Алгоритм] Упаковка кругов разного размера в прямоугольник

Поделиться
ShitsexyПостоялецwww25 окт. 20174:19#0
Ктонибудь знает алгоритм, которым можно упаковать заполнить прямогольник(или квадрат) рандомными кружками максимально плотно.

Вот примерно как на картинке
circles | [Алгоритм] Упаковка кругов разного размера в прямоугольник

Правка: 25 окт. 2017 4:24

SuslikМодераторwww25 окт. 201710:55#1
разумеется, в общем случае аналитически точное решение ты не получишь и, вероятно, лучше сразу указать, что оно тебе и не нужно. а чтобы просто выглядело похоже, существует миллион способов. самый просто — просто на каждом шаге алгоритма ищешь самое большое пустое место, куда можно впихнуть кржочек и впихиваешь. повторяешь до тех пор, пока достаточно больших пустот больше не будет.

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

Правка: 25 окт. 2017 10:55

ShitsexyПостоялецwww25 окт. 201718:23#2
Спасибо!

У меня на самом деле как раз больше затык в определении этих пустот, это всетаки не квадраты, форма пустот нетривиальная. Есть какието распростроенные способы работы с этим? На ум приходит только разбить область на сетку, но это либо не очень точно, либо очень медленно(если мелкая сетка)

}:+()___ [Smile]Постоялецwww25 окт. 201719:09#3
Shitsexy
> У меня на самом деле как раз больше затык в определении этих пустот, это всетаки не квадраты, форма пустот нетривиальная.
Это интересная математическая задача. Мое предложение: хранить в виде аналитического distance field.

DF одного круга — это конус.
Для двух кругов конусы пересекаются по гиперболе.
Три круга образуют схождение трех гиперболических кривых в одной точке.
Соответственно, набор кругов образует криволинейную сетку, в узлах которой локальные минимумы DF, т. е. искомые пустоты.
Кстати, если круги заменить на точки, то сетка вырождается в триангуляцию Делоне, так что есть подозрение, что криволинейную сетку можно построить заметанием прямой.

t800Пользовательwww25 окт. 201721:52#4
Про алгоритмы ничего не скажу , но если нужен код упаковщика, то собственно вот:


https://www.codeproject.com/articles/42067/2d-circle-packing-algo… m-ported-to-c

Правка: 25 окт. 2017 21:58

/A\Постоялецwww25 окт. 201723:42#5
Можно попробовать диаграмы вороного, особенно если после построения диаграммы в несколько итераций подвигать точки.
+ просто_картинка
SuslikМодераторwww26 окт. 20172:09#6
}:+()___ [Smile]
> DF одного круга — это конус.
> Для двух кругов конусы пересекаются по гиперболе.
трёхмерная форма линии пересечения вообще особой роли не играет. я сомневаюсь, что кому-то нужно аналитически точное решение(если никто даже критерий оптимальности толком не определил), поэтому нет смысла искать решение точной математикой. можно просто растеризовать DF каждого следующего круга через рендеринг в текстуру, используя функцию min(). на каждом шаге искать наибольший элемент в этой текстуре и в него втыкать очередной круг. максимум в текстуре можно искать, отрендерив все её мипы, на каждом шаге выбирая максимум из усредняемых пикселей.
}:+()___ [Smile]Постоялецwww26 окт. 201717:34#7
Suslik
> поэтому нет смысла искать решение точной математикой.
Модифицированная триангуляция Делоне вполне может оказаться быстрее и точнее image-based методов.
К тому же, ее можно обновлять локально, что может помочь при итеративных добавлениях кругов.
Но, самое главное, у нее нет штрафа на большой диапазон диаметров кругов.
SuslikМодераторwww26 окт. 201718:08#8
}:+()___ [Smile]
> Но, самое главное, у нее нет штрафа на большой диапазон диаметров кругов.
круги по условию не могут пересекаться, поэтому суммарная площадь всех кругов при растеризации не будет превосходить площади исходной области.
ASModeiПользовательwww28 окт. 201723:40#9
Мда, все легко на словах, но на деле...)) Задачу нельзя решить точно, так как NP-полная. Для приближенного решения есть разные методы: использования годографа, алгоритмы имитации отжига, генетические алгоритмы, вероятностные. Вот! Отобрал из своего архива самое интересное на эту тему http://dropmefiles.com/ECWk3.
P.S. автор забыл уточнить, сама упаковка онлайн или оффлайн?

Правка: 28 окт. 2017 23:50

ShitsexyПостоялецwww29 окт. 201720:57#10
ASModei
Спасибо! Что значит онлайн\оффлайн? В реальном времени паковать не нужно
ASModeiПользовательwww29 окт. 201721:26#11
online - объекты поступают со временем, offline - система фигур для упаковки заранее известна.
FordPerfectПостоялецwww29 окт. 201723:47#12
>Задачу нельзя решить точно, так как NP-полная.
Так NP-полная или нельзя решить точно? Если NP-полная - удивительно, я думал - хуже.
MrShoorУчастникwww29 окт. 201723:55#13
FordPerfect
> Так NP-полная или нельзя решить точно? Если NP-полная - удивительно, я думал -
> хуже.
Это c-c-c-combo. NP-полная которую рельзя решить точно (ну по крайней мере пока копьютеры не научатся работать с иррациональными числами). Да и приблеженно решить задачу - тоже под вопросом.

/ Форум / Программирование игр / Общее

2001—2017 © GameDev.ru — Разработка игр