Список работ

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

Содержание

Генерация элементов

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

Реализация алгоритма размещения

Приводимый ниже 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
)

Список работ

Рейтинг@Mail.ru