GBee
Задачу поставили в таком ключе, что в рантайме надо уметь добавлять домик в произвольное свободное место (то есть если использовать сетку, то появляется ограничение, не позволяющее разместить домик на стыке) + сами домики могут быть произвольного размера, так что выбрать шаг сетки неудастся
Короч, я написал МОНСТРА, который ПОЧТИ выполняет свою задачу (пока еще отлаживаю, но хочу поделиться)
По клику добавляется новый прямоугольник (иногда неправильно рассчитываются области, выясняю почему)
Вот код
Код AS3:
package
{
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Rectangle;
[SWF(width = "800", height = "600", backgroundColor = "#FFFFFF", frameRate = "60")]
public class Slicing extends Sprite
{
private var canvas:Sprite = new Sprite();
private var rectsCanvas:Sprite = new Sprite();
private var areasCanvas:Sprite = new Sprite();
private var baseArea:Rectangle = new Rectangle(0, 0, 700, 500);
private var freeAreas:Vector.<Rectangle> = new <Rectangle>[];
private var rects:Vector.<Rectangle> = new <Rectangle>[];
public function Slicing()
{
addEventListener(Event.ADDED_TO_STAGE, onAddedToStage);
}
private function onAddedToStage(event:Event):void
{
removeEventListener(Event.ADDED_TO_STAGE, onAddedToStage);
stage.scaleMode = StageScaleMode.NO_SCALE;
stage.align = StageAlign.TOP_LEFT;
canvas.x = (stage.stageWidth - baseArea.width) >> 1;
canvas.y = (stage.stageHeight - baseArea.height) >> 1;
addChild(canvas);
canvas.addChild(rectsCanvas);
canvas.addChild(areasCanvas);
init();
}
private function init():void
{
freeAreas.push(baseArea);
drawAreas();
stage.addEventListener(MouseEvent.CLICK, onClick);
}
private function drawAreas():void
{
for (var i:int = 0, length:int = freeAreas.length; i < length; i++)
{
drawArea(freeAreas[i]);
}
}
private function drawArea(area:Rectangle):void
{
areasCanvas.graphics.lineStyle(1, Math.round(Math.random() * 0xFFFFFF));
areasCanvas.graphics.drawRect(area.x, area.y, area.width, area.height);
}
private function createRandomRect():Rectangle
{
var rect:Rectangle = new Rectangle();
rect.width = 30 + Math.round(Math.random() * 50);
rect.height = 30 + Math.round(Math.random() * 50);
return rect;
}
private function drawRect(rect:Rectangle):void
{
rectsCanvas.graphics.beginFill(0);
rectsCanvas.graphics.drawRect(rect.x, rect.y, rect.width, rect.height);
rectsCanvas.graphics.endFill();
}
private function onClick(event:MouseEvent):void
{
putRectIntoFreeArea();
recalculateFreeAreas();
drawAreas();
}
private function putRectIntoFreeArea():void
{
var rect:Rectangle = createRandomRect();
var suitableAreas:Vector.<Rectangle> = new <Rectangle>[];
for (var i:int = 0, length:int = freeAreas.length; i < length; i++)
{
var area:Rectangle = freeAreas[i];
if (area.width >= rect.width && area.height >= rect.height)
{
suitableAreas.push(area);
}
}
if (suitableAreas.length == 0)
return;
rects.push(rect);
var randomSuitableArea:Rectangle = suitableAreas[Math.floor(Math.random() * suitableAreas.length)];
rect.x = randomSuitableArea.x + Math.round(Math.random() * (randomSuitableArea.width - rect.width));
rect.y = randomSuitableArea.y + Math.round(Math.random() * (randomSuitableArea.height - rect.height));
drawRect(rect);
}
private function recalculateFreeAreas():void
{
areasCanvas.graphics.clear();
freeAreas.length = 0;
for (var i:int = 0, length:int = rects.length; i < length; i++)
{
var rect:Rectangle = rects[i];
var topArea:Rectangle = new Rectangle();
topArea.copyFrom(baseArea);
topArea.bottom = rect.top;
var bottomArea:Rectangle = new Rectangle();
bottomArea.copyFrom(baseArea);
bottomArea.top = rect.bottom;
var leftArea:Rectangle = new Rectangle();
leftArea.copyFrom(baseArea);
leftArea.right = rect.left;
var rightArea:Rectangle = new Rectangle();
rightArea.copyFrom(baseArea);
rightArea.left = rect.right;
checkForTopIntersections(rect, topArea);
checkForBottomIntersections(rect, bottomArea);
checkForLeftIntersections(rect, leftArea);
checkForRightIntersections(rect, rightArea);
if (topArea.width * topArea.height > 0)
{
freeAreas.push(topArea);
}
if (bottomArea.width * bottomArea.height > 0)
{
freeAreas.push(bottomArea);
}
if (leftArea.width * leftArea.height > 0)
{
freeAreas.push(leftArea);
}
if (rightArea.width * rightArea.height > 0)
{
freeAreas.push(rightArea);
}
}
}
private function checkForTopIntersections(targetRect:Rectangle, area:Rectangle):void
{
var sideCompareRects:Vector.<Rectangle> = new <Rectangle>[];
var i:int = 0;
var length:int = 0;
var currentRect:Rectangle = null;
for (i = 0, length = rects.length; i < length; i++)
{
currentRect = rects[i];
if (currentRect === targetRect)
continue;
if (area.intersects(currentRect))
{
sideCompareRects.push(currentRect);
}
}
var nearestLeft:Rectangle = null;
var nearestRight:Rectangle = null;
for (i = 0, length = sideCompareRects.length; i < length; i++)
{
currentRect = sideCompareRects[i]
if (currentRect.right <= targetRect.left)
{
if (nearestLeft)
{
nearestLeft = nearestLeft.right < currentRect.right ? currentRect : nearestLeft;
}
else
{
nearestLeft = currentRect;
}
}
if (currentRect.left >= targetRect.right)
{
if (nearestRight)
{
nearestRight = nearestRight.left > currentRect.left ? currentRect : nearestRight;
}
else
{
nearestRight = currentRect;
}
}
}
area.left = nearestLeft ? nearestLeft.right : area.left;
area.right = nearestRight ? nearestRight.left : area.right;
var topCompareRects:Vector.<Rectangle> = new <Rectangle>[];
for (i = 0, length = sideCompareRects.length; i < length; i++)
{
currentRect = sideCompareRects[i];
if (area.intersects(currentRect))
{
topCompareRects.push(currentRect);
}
}
var nearestTop:Rectangle = null;
for (i = 0, length = topCompareRects.length; i < length; i++)
{
currentRect = topCompareRects[i];
if (currentRect.bottom < targetRect.top)
{
if (nearestTop)
{
nearestTop = nearestTop.bottom < currentRect.bottom ? currentRect : nearestTop;
}
else
{
nearestTop = currentRect;
}
}
}
area.top = nearestTop ? nearestTop.bottom : area.top;
}
private function checkForBottomIntersections(targetRect:Rectangle, area:Rectangle):void
{
var sideCompareRects:Vector.<Rectangle> = new <Rectangle>[];
var i:int = 0;
var length:int = 0;
var currentRect:Rectangle = null;
for (i = 0, length = rects.length; i < length; i++)
{
currentRect = rects[i];
if (currentRect === targetRect)
continue;
if (area.intersects(currentRect))
{
sideCompareRects.push(currentRect);
}
}
var nearestLeft:Rectangle = null;
var nearestRight:Rectangle = null;
for (i = 0, length = sideCompareRects.length; i < length; i++)
{
currentRect = sideCompareRects[i]
if (currentRect.right <= targetRect.left)
{
if (nearestLeft)
{
nearestLeft = nearestLeft.right < currentRect.right ? currentRect : nearestLeft;
}
else
{
nearestLeft = currentRect;
}
}
if (currentRect.left >= targetRect.right)
{
if (nearestRight)
{
nearestRight = nearestRight.left > currentRect.left ? currentRect : nearestRight;
}
else
{
nearestRight = currentRect;
}
}
}
area.left = nearestLeft ? nearestLeft.right : area.left;
area.right = nearestRight ? nearestRight.left : area.right;
var bottomCompareRects:Vector.<Rectangle> = new <Rectangle>[];
for (i = 0, length = sideCompareRects.length; i < length; i++)
{
currentRect = sideCompareRects[i];
if (area.intersects(currentRect))
{
bottomCompareRects.push(currentRect);
}
}
var nearestBottom:Rectangle = null;
for (i = 0, length = bottomCompareRects.length; i < length; i++)
{
currentRect = bottomCompareRects[i];
if (currentRect.top < targetRect.bottom)
{
if (nearestBottom)
{
nearestBottom = nearestBottom.top > currentRect.top ? currentRect : nearestBottom;
}
else
{
nearestBottom = currentRect;
}
}
}
area.bottom = nearestBottom ? nearestBottom.bottom : area.bottom;
}
private function checkForLeftIntersections(targetRect:Rectangle, area:Rectangle):void
{
var verticalCompareRects:Vector.<Rectangle> = new <Rectangle>[];
var i:int = 0;
var length:int = 0;
var currentRect:Rectangle = null;
for (i = 0, length = rects.length; i < length; i++)
{
currentRect = rects[i];
if (currentRect === targetRect)
continue;
if (area.intersects(currentRect))
{
verticalCompareRects.push(currentRect);
}
}
var nearestTop:Rectangle = null;
var nearestBottom:Rectangle = null;
for (i = 0, length = verticalCompareRects.length; i < length; i++)
{
currentRect = verticalCompareRects[i]
if (currentRect.bottom <= targetRect.top)
{
if (nearestTop)
{
nearestTop = nearestTop.bottom < currentRect.bottom ? currentRect : nearestTop;
}
else
{
nearestTop = currentRect;
}
}
if (currentRect.top >= targetRect.bottom)
{
if (nearestBottom)
{
nearestBottom = nearestBottom.top > currentRect.top ? currentRect : nearestBottom;
}
else
{
nearestBottom = currentRect;
}
}
}
area.top = nearestTop ? nearestTop.bottom : area.top;
area.bottom = nearestBottom ? nearestBottom.top : area.bottom;
var leftCompareRects:Vector.<Rectangle> = new <Rectangle>[];
for (i = 0, length = verticalCompareRects.length; i < length; i++)
{
currentRect = verticalCompareRects[i];
if (area.intersects(currentRect))
{
leftCompareRects.push(currentRect);
}
}
var nearestLeft:Rectangle = null;
for (i = 0, length = leftCompareRects.length; i < length; i++)
{
currentRect = leftCompareRects[i];
if (currentRect.right < targetRect.left)
{
if (nearestLeft)
{
nearestLeft = nearestLeft.right < currentRect.right ? currentRect : nearestLeft;
}
else
{
nearestLeft = currentRect;
}
}
}
area.left = nearestLeft ? nearestLeft.right : area.left;
}
private function checkForRightIntersections(targetRect:Rectangle, area:Rectangle):void
{
var verticalCompareRects:Vector.<Rectangle> = new <Rectangle>[];
var i:int = 0;
var length:int = 0;
var currentRect:Rectangle = null;
for (i = 0, length = rects.length; i < length; i++)
{
currentRect = rects[i];
if (currentRect === targetRect)
continue;
if (area.intersects(currentRect))
{
verticalCompareRects.push(currentRect);
}
}
var nearestTop:Rectangle = null;
var nearestBottom:Rectangle = null;
for (i = 0, length = verticalCompareRects.length; i < length; i++)
{
currentRect = verticalCompareRects[i]
if (currentRect.bottom <= targetRect.top)
{
if (nearestTop)
{
nearestTop = nearestTop.bottom < currentRect.bottom ? currentRect : nearestTop;
}
else
{
nearestTop = currentRect;
}
}
if (currentRect.top >= targetRect.bottom)
{
if (nearestBottom)
{
nearestBottom = nearestBottom.top > currentRect.top ? currentRect : nearestBottom;
}
else
{
nearestBottom = currentRect;
}
}
}
area.top = nearestTop ? nearestTop.bottom : area.top;
area.bottom = nearestBottom ? nearestBottom.top : area.bottom;
var leftCompareRects:Vector.<Rectangle> = new <Rectangle>[];
for (i = 0, length = verticalCompareRects.length; i < length; i++)
{
currentRect = verticalCompareRects[i];
if (area.intersects(currentRect))
{
leftCompareRects.push(currentRect);
}
}
var nearestRight:Rectangle = null;
for (i = 0, length = leftCompareRects.length; i < length; i++)
{
currentRect = leftCompareRects[i];
if (currentRect.left > targetRect.right)
{
if (nearestRight)
{
nearestRight = nearestRight.left < currentRect.left ? currentRect : nearestRight;
}
else
{
nearestRight = currentRect;
}
}
}
area.right = nearestRight ? nearestRight.left : area.right;
}
}
}
Выглядит он совершенно люто, так что если у кого-то есть предложения по правкам - пожалуйста.
Вкратце алгоритм делает следующее (на примере верхней области):
- Берем прямоугольник всей области
- Отсекаем его низ по верхней границе вставленного прямоугольника
- Берем множество прямоугольников, которые эта область пересекает
- Находим ближайший левый (не пересекающийся проекциями на ось Х) прямоугольник (если есть) и по его правой границе отсекаем область
- Такая же история для правой стороны
- Еще раз находим множество прямоугольников, теперь уже попадающих в новую область
- Находи ближайший верхний и по его границе отсекаем область
Как-то так.
Как закончу - выложу окончательный вариант.