Список работ

Размещение разногабаритных элементов

Содержание

Введение

Решается задача размещения без взаимного пересечения заданного числа разногабаритных элементов на прямоугольной площадке размещения (далее ПР). Язык программирования 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).

Попытка равномерного размещения элементов по оси Y

Рис. 5. После сдвига по оси Y

Попытка равномерного размещения элементов по оси X

Рис. 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, порог сглаживания ФР, порог включения элемента в массив перемещаемых элементов и коэффициент сужения сдвигаемого элемента.
Кроме того, для перехода от плотного размещения к равномерному можно взамен использованной эвристики употребить, например, генетический алгоритм.

Источники

  1. Autodesk® 3ds Max® 2009 MAXScript Reference.
  2. Абрайтис Л. Б. Автоматизация проектирования топологии цифровых интегральных микросхем. – М.: Радио и связь, 1985. – 200 с.
  3. Бартеньев О. В. Программирование модификаторов 3ds Max. Учебно-справочное пособие. – М.: Физматкнига, 2009. – 341 с.
  4. Петренко А. И., Тетельбаум А. Я. Формальное конструирование электронно-вычислительной аппаратуры. М.: Сов. радио, 1979. – 256 с.

Список работ

Рейтинг@Mail.ru