Решается задача размещения без взаимного пересечения заданного числа разногабаритных элементов на прямоугольной площадке размещения (далее ПР). Язык программирования MAXScript. Моделью элемента является прямоугольник. ПР связана с декартовой системой координат: нижний левый угол ПР находится в начале координат; X и Y оси координат направлены соответственно по нижней и левой сторонам ПР.
Подобные задачи решаются, в частности, в САПР печатных плат и интегральных схем. Критерием качества размещения может быть суммарная длина межэлементных соединений, предусмотренных электрической схемой. Для оценки длины соединения может быть использована ортогональная метрика (см. Лучевой алгоритм). В случае многослойных конструкций также полезно минимизировать и число межслойных переходов пролагаемых трасс.
Для иллюстрации процесса размещения с использованием датчика случайных чисел генерируются разногабаритные прямоугольники (рис. 1), суммарная площадь которых чуть более 60 % площади ПР.
Рис. 1. Отображение элементов, приготовленных для размещения
Генерацию элементов и их отображение обеспечивает следующий MAXScript-код:
-- Показывает элементы, подготовленные для размещения
fn shLmnts arrL lngth wdth dmn clr tH = (
local n, py, k, a
n = arrL.Count
py = -0.5 * lngth
k = 0
a = 0.1 * dmn
while k < n do (
px = -0.5 * wdth
ymx = 0
while px < 0.5 * wdth and k < n do (
k += 1
x = arrL[k][1]; y = arrL[k][2]
p = point3 (px + 0.5 * x) (py + 0.5 * y) 0
box length:(y - a) width:(x - a) height:1 lengthsegs:1 widthsegs:1 heightsegs:1 wireColor:clr pos:p
text text:(k as string) size:tH pos:[p[1], py + 0.5 * tH, 1.01] wireColor:black render_displayRenderMesh:false
px += x
ymx = amax ymx y
)
py += 1.1 * ymx
)
rectangle length:lngth width:wdth wireColor:black
max tool zoomExtents
)
delete $*
viewport.SetLayout #layout_4
viewport.ActiveViewport = 1
viewport.SetType #view_top
viewport.SetGridVisibility 1 off
viewport.SetRenderLevel #smoothhighlights
viewport.SetShowEdgeFaces on
clr = color 250 100 100
-- Размеры ПР
wdth = 200; lngth = 150
-- Границы изменения размеров генерируемых элементов
dmx = ((wdth + lngth) / 15) as integer; dmn = (0.5 * dmx) as integer
-- Коэффициент заполнения ПР элементами
pcnt = 0.6
-- Высота текста
tH = 0.7 * dmn
-- Массив arrL размещаемых элементов
-- Каждый элемент массива - это point2-элемент, хранящий размеры сгенерированного прямоугольника
arrL = #()
sT = 0
while sT < pcnt * wdth * lngth do (
pt2 = point2 (random dmx dmn) (random dmx dmn)
append arrL pt2
sT += pt2[1] * pt2[2]
)
-- Покажем ПР и размещаемые элементы
shLmnts arrL lngth wdth dmn clr tH
Прямоугольник (элемент) может быть размещен на ПР в одной из двух ориентаций (рис. 2).
Рис. 2. Ориентации размещаемого элемента
Реализуется последовательное размещение элементов, заполняющих ПР снизу вверх. Выбор ориентации осуществляется с помощью датчика случайных чисел. Также случайным образом формируется и очередной размещаемый элемент (прямоугольник).
Заметим, что в названных выше задачах САПР число возможных ориентаций элемента в 2 раза больше (по-разному ориентируются выводы элемента). Выбор очередного элемента (в случае последовательного размещения), его ориентации и позиции осуществляет таким образом, чтобы минимизировать значение критерия размещения (например, суммарную длину соединений).
Реализуемый алгоритм размещения предусматривает 2 этапа. На первом выполняется плотное размещение элементов (рис. 3), а на втором они перемещаются с целью равномерного заполнения ПР.
Рис. 3. Плотное размещение элементов
Равномерное заполнение ПР выполняется за несколько шагов. Первоначально плотное размещение перемещается в центр ПР (рис. 4).
Рис. 4. Плотное размещение элементов перемещено в центр ПР
Далее элементы раздвигаются по оси Y (рис. 5), а вслед – по оси X (рис. 6).
Рис. 5. После сдвига по оси Y
Рис. 6. После сдвига по оси X
Плотное размещение выполняется на площадке ПР2, ширина которой несколько меньше ширины исходной площадки ПР.
Размещение очередного элемента производится в выбранной ориентации в позицию фронта размещения (ФР) с наименьшей Y-координатой. Такая позиция называется позицией размещения. Если позиций, отвечающих указанному условию, несколько, то в качестве позиции размещения берется позиция с наименьшей X-координатой.
При размещении нижний левый угол элемента совмещается с выбранной позицией ФР. Если в выбранной ориентации размещение невозможно (элемент пересекает ранее размещенные элементы или выходит за правую границу ФР), то на предмет размещения исследуется вторая ориентация.
Если и эта попытка завершается неудачей, то из ФР изымается горизонтальный кусок, исходящий из позиции размещения и далее выполняется новая попытка размещения выбранного элемента в новой конфигурации ФР.
Таким образом, ФР – это ломаная линия, образованная сторонами элементов, расположенных в верхней части текущего размещения (рис. 7).
Рис. 7. Промежуточная конфигурация ФР
Первоначально ФР – это ПР2 без верхней стороны.
После размещения элемента выполняется корректировка ФР:
Если высота формируемой линии ФР равна высоте предшествующей линии ФР или если высота формируемой линии ФР несколько ниже высоты предшествующей линии ФР, то вертикаль ФР, исходящая из позиции размещения, сдвигается в положительном направлении оси X, иначе выполняется пополнение ФР горизонтальным участком, ширина которого равна ширине только что размещенного элемента.
Процесс плотного размещения прерывается, если очередной элемент выходит за пределы верхней границы ПР.
Процедуру перехода от плотного размещения к равномерному проиллюстрируем примером перемещения элементов по направлению оси Y (выполняется после переноса плотного размещения в центр ПР).
Прежде формируется массив arrTMv перемещаемых элементов. В него включаются элементы, расположенные в верхней половине ПР.
Далее, пока не выполнено перемещение всех элементов массива arrTMv, в нем берется верхний неперемещенный элемент, для него определяются верхняя граница сдвига pBdr и число nP нижележащих элементов, принадлежащих arrTMv. После этого выполняется перемещение выбранного элемента, такое, что его верхняя сторона находится ниже pBdr на величину dst = 0.5 * (pBdr – yPM) / nP, где yPM – это Y-координата верхней границы элемента до его сдвига.
Приводимый ниже MAXScript-код обеспечивает следующие действия:
-- Перемещает элементы массива arrTMv в указанном направлении (вверх, вниз, вправо или влево)
-- с целью равномерного заполнения площадки размещения
fn mvK wh arrL arrPS arrR n2 arrTMv arrNtMvd sz ksq = (
kmx = 0
cmx = if mod wh 2 == 1 then 0 else sz
k2 = if wh < 3 then 2 else 1
-- Находим верхний (нижний, левый, правый) не перемещенный элемент
for m = 1 to n2 do
if arrNtMvd[m] do (
c = arrPs[arrTMv[m]][k2]
if mod wh 2 == 1 then
if cmx < c do (cmx = c; kmx = m)
else
if cmx > c do (cmx = c; kmx = m)
)
-- Если все элементы массива arrTMv перемещены
if kmx == 0 do return false
kmx2 = arrTMv[kmx]
rctng = arrL[kmx2]
xM = rctng[1]; yM = rctng[2]
if arrR[kmx2] == 2 do (xM = yM; yM = rctng[1])
pM = arrPs[kmx2]
if wh < 3 then xM *= ksq else yM *= ksq
xLM = pM[1] - 0.5 * xM; xRM = pM[1] + 0.5 * xM
yLM = pM[2] - 0.5 * yM; yPM = pM[2] + 0.5 * yM
-- Верхняя (нижняя) граница элемента arrTMv[kmx]
pBdr = if mod wh 2 == 1 then sz else 0
for m = 1 to n2 do (
if not arrNtMvd[m] and m != kmx do (
k2 = arrTMv[m]
rctng = arrL[k2]
x = rctng[1]; y = rctng[2]
if arrR[k2] == 2 do (x = y; y = rctng[1])
if wh < 3 then x *= ksq else y *= ksq
p = arrPs[k2]
xL = p[1] - 0.5 * x; xR = p[1] + 0.5 * x
yL = p[2] - 0.5 * y; yP = p[2] + 0.5 * y
if wh < 3 then
if xL < xRM and xR > xLM do pBdr = if wh == 1 then amin pBdr yL else amax pBdr yP
else
if yL < yPM and yP > yLM do pBdr = if wh == 3 then amin pBdr xL else amax pBdr xR
)
)
-- Число элементов под (над, правее, левее) arrTMv[kmx] равно max(nP, 1)
nP = 0
for m = 1 to n2 do (
if arrNtMvd[m] and m != kmx do (
k2 = arrTMv[m]
rctng = arrL[k2]
p = arrPs[k2]
if wh < 3 then (
x = ksq * rctng[arrR[k2]]
xL = p[1] - 0.5 * x; xR = p[1] + 0.5 * x
if xL < xRM and xR > xLM do nP += 1
)
else (
y = ksq * rctng[3 - arrR[k2]]
yL = p[2] - 0.5 * y; yP = p[2] + 0.5 * y
if yL < yPM and yP > yLM do nP += 1
)
)
)
-- Перемещение
nP = amax nP 1
if wh < 3 then (
dst = 0.5 * (if wh == 1 then pBdr - yPM else yLM - pBdr) / nP
arrPs[kmx2][2] = if wh == 1 then pBdr - dst - 0.5 * yM else pBdr + dst + 0.5 * yM
)
else (
dst = 0.5 * (if wh == 3 then pBdr - xRM else xLM - pBdr) / nP
arrPs[kmx2][1] = if wh == 3 then pBdr - dst - 0.5 * xM else pBdr + dst + 0.5 * xM
)
arrNtMvd[kmx] = false
return true
)
fn cntrCP n arrL arrPs arrR wdth lngth = (
xMx = yMx = 0
for k = 1 to n do (
x = arrL[k][1]
y = arrL[k][2]
if arrR[k] == 2 do (x = y; y = arrL[k][1])
xMx = amax xMx (arrPs[k][1] + 0.5 * x)
yMx = amax yMx (arrPs[k][2] + 0.5 * y)
)
dx = 0.5 * (wdth - xMx)
dy = 0.5 * (lngth - yMx)
for k = 1 to n do arrPs[k] += [dx, dy, 0]
)
fn shftL arrF kmn = (
arrF[kmn][2] = arrF[kmn + 2][2]
return kmn +1
)
fn shftR arrF kmn = (
arrF[kmn + 1][2] = arrF[kmn - 1][2]
return kmn - 1
)
-- Размещение
fn dPlcmnt arrF kmn xmn ymn x y arrR rntn arrPs kP bSmth = (
x2 = xmn + x
y2 = ymn + y
y0 = arrF[kmn - 1][2]
kmn1 = kmn + 1
x3 = arrF[kmn1][1]
-- Выполняем размещение либо увеличивая X-координату текущей позиции,
-- либо сглаживая ФР, либо пополняя ФР
case of (
(y0 == y2 or y0 > y2 and y0 - y2 < bSmth): (arrF[kmn - 1][1] = x2; arrF[kmn][1] = x2)
(y0 > y2): (
arrF[kmn][2] = y2
insertItem (point2 x2 ymn) arrF kmn1
insertItem (point2 x2 y2) arrF kmn1
)
default: (
arrF[kmn][2] = y2
if x2 == x3 then
arrF[kmn1][2] = y2
else (
insertItem (point2 x2 y2) arrF kmn1
insertItem (point2 x2 ymn) arrF (kmn + 2)
)
)
)
append arrPs (point3 (xmn + 0.5 * x) (ymn + 0.5 * y) 0)
append arrR rntn
return kP +1
)
-- Показывает размещение и ФР (если shF = true)
fn drwF arrF arrL arrR arrPs kP clr tH shF = (
local n2, k2, p
select $Box*; delete selection
select $Text*; delete selection
select $Shape*; delete selection
if shF do (
n2 = arrF.Count
ss = splineShape render_displayRenderMesh:true render_thickness:1.0
addNewSpline ss
for k2 = 1 to n2 do addKnot ss 1 #corner #line (point3 arrF[k2][1] arrF[k2][2] 1.1)
)
for k2 = 1 to kP do (
p = arrPs[k2]
rctng = arrL[k2]
x = rctng[1]; y = rctng[2]
rntn = arrR[k2]
if rntn == 2 do (
x = y; y = rctng[1]
)
box length:y width:x height:1 lengthsegs:1 widthsegs:1 heightsegs:1 wireColor:clr pos:p
text text:(k2 as string) size:tH pos:[p[1], p[2] - 0.5 * tH, 1.01] wireColor:black render_displayRenderMesh:false
)
)
-- Показывает элементы, подготовленные для размещения
fn shLmnts arrL lngth wdth dmn clr tH = (
local n, py, k, a
n = arrL.Count
py = -0.5 * lngth
k = 0
a = 0.1 * dmn
while k < n do (
px = -0.5 * wdth
ymx = 0
while px < 0.5 * wdth and k < n do (
k += 1
x = arrL[k][1]; y = arrL[k][2]
p = point3 (px + 0.5 * x) (py + 0.5 * y) 0
box length:(y - a) width:(x - a) height:1 lengthsegs:1 widthsegs:1 heightsegs:1 wireColor:clr pos:p
text text:(k as string) size:tH pos:[p[1], py + 0.5 * tH, 1.01] wireColor:black render_displayRenderMesh:false
px += x
ymx = amax ymx y
)
py += 1.1 * ymx
)
rectangle length:lngth width:wdth wireColor:black
max tool zoomExtents
)
delete $*
viewport.SetLayout #layout_4
viewport.ActiveViewport = 1
viewport.SetType #view_top
viewport.SetGridVisibility 1 off
viewport.SetRenderLevel #smoothhighlights
viewport.SetShowEdgeFaces on
clr = color 250 100 100
-- Размеры ПР
wdth = 200.0; lngth = 150.0
-- Границы изменения размеров генерируемых элементов
dmx = ((wdth + lngth) / 15) as integer; dmn = (0.4 * dmx) as integer
-- Коэффициент заполнения ПР элементами
pcnt = 0.6
-- Высота текста
tH = 0.7 * dmn
-- Ширина ПР2
xF = 1.15 * (sqrt pcnt) * wdth
-- Порог сглаживания ФР
bSmth = 4
-- Коэффициент сужения сдвигаемого элемента
ksq = 1.15 * sqrt pcnt
-- Порог включения элемента в массив перемещаемых элементов
bMvd = lngth / 20
-- Массив arrL размещаемых элементов
-- Каждый элемент массива - это point2-элемент, хранящий размеры сгенерированного прямоугольника
arrL = #()
sT = 0
while sT < pcnt * wdth * lngth do (
pt2 = point2 (random dmx dmn) (random dmx dmn)
append arrL pt2
sT += pt2[1] * pt2[2]
)
-- Покажем ПР и размещаемые элементы
--shLmnts arrL lngth wdth dmn clr tH
-- Рисуем ПР
rectangle length:lngth width:wdth pos:[0.5 * wdth, 0.5 * lngth, 0] wireColor:black
max tool zoomExtents
-- Начальный ФР содержит одну пригодную для размещения позицию
-- Массив, хранящий ФР
arrF = #([0, lngth], [0, 0], [xF, 0], [xF, lngth])
-- Массивы позиций и ориентаций размещенных элементов
arrPs = #(); arrR = #()
n = arrL.Count
lPlcd = true -- Останется true, если удастся разместить все элементы
kP = 0
-- Цикл размещения
for k = 1 to n do (
rctngl = arrL[k]
-- Ориентация
x = rctngl[1]; y = rctngl[2]
rntn = random 1 2
if rntn == 2 do ( x = y; y = rctngl[1])
-- Размещение в позиции ФР
for m = 1 to arrF.Count do (
n2 = arrF.Count - 2
-- Поиск позиции с минимальной Y-координатой
kmn = 2
for k2 = 4 to n2 do if arrF[k2][2] < arrF[kmn][2] do kmn = k2
ymn = arrF[kmn][2]
-- Обнаружен выход за Y-границу ПР. Прерываем цикл размещения
if ymn + y > lngth do (lPlcd = false; exit)
xmn = arrF[kmn][1]
dF = arrF[kmn + 1][1] - xmn
case of (
(x <= dF): (kP = dPlcmnt arrF kmn xmn ymn x y arrR rntn arrPs kP bSmth; exit)
(x > y and y <= dF): (kP = dPlcmnt arrF kmn xmn ymn y x arrR (3 - rntn) arrPs kP bSmth; exit)
default: (
-- Изымаем из ФР узкий участок
kmn = case of (
(kmn == 2): shftL arrF kmn
(arrF[kmn + 1][1] == xF): shftR arrF kmn
default: if arrF[kmn - 1][2] < arrF[kmn + 2][2] then shftR arrF kmn else shftL arrF kmn
)
deleteItem arrF kmn
deleteItem arrF kmn
)
)
)
if not lPlcd do (
messageBox("Some items are not placed: All = " + (n as string) + "; Placed = " + (kP as string))
exit
)
)
-- Покажем плотное размещение и ФР
drwF arrF arrL arrR arrPs kP clr tH true
if lPlcd do (
-- Центрируем плотное размещение
cntrCP n arrL arrPs arrR wdth lngth
-- Покажем смещенное плотное размещение
drwF arrF arrL arrR arrPs kP clr tH false
-- Последовательное перемещение верх, вниз, влево и вправо выбранной порции элементов
for wh = 4 to 4 do (
sz = if wh < 3 then lngth else wdth
k2 = if wh < 3 then 2 else 1
if mod wh 2 == 1 then
arrTMv = for k = 1 to n where arrPs[k][k2] > 0.5 * sz + bMvd collect k
else
arrTMv = for k = 1 to n where arrPs[k][k2] < 0.5 * sz - bMvd collect k
n2 = arrTMv.Count
arrNtMvd = for k = 1 to n2 collect true
for k = 1 to n2 do
if not (mvK wh arrL arrPS arrR n2 arrTMv arrNtMvd sz ksq) do exit
)
drwF arrF arrL arrR arrPs kP clr tH false
)
Полученный результат можно улучшить интерактивно. Также улучшения можно добиться, варьируя параметры размещения, такие, как ширина ПР2, порог сглаживания ФР, порог включения элемента в массив перемещаемых элементов и коэффициент сужения сдвигаемого элемента.
Кроме того, для перехода от плотного размещения к равномерному можно взамен использованной эвристики употребить, например, генетический алгоритм.