Вообщем, что то такое я набросал, вариант правда далёк от завершения.
искать свободную площадь. В примере ищется площадь для верхней стороны квадратов.
Код AS3:
package
{
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Rectangle;
/**
* Тест.
* @author Tails
*/
public class Main extends Sprite {
// Приват
private var _quadsTotal:uint; // Количество квадратов.
private var _space:Rectangle; // Размер мира.
private var _sprite:Sprite; // Рисунок результата.
private var _quads:Vector.<Rectangle>; // Рассекающие квадраты.
private var _result:Vector.<Rectangle>; // Полученные области.
public function Main() {
if (stage === null)
addEventListener(Event.ADDED_TO_STAGE, init);
else
init();
}
private function init(e:Event = null):void {
removeEventListener(Event.ADDED_TO_STAGE, init);
_sprite = new Sprite;
addChild(_sprite);
stage.addEventListener(MouseEvent.MOUSE_DOWN, onMouseDown);
onMouseDown();
}
private function onMouseDown(e:MouseEvent = null):void {
var i:uint;
var quad:Rectangle;
// ГЕНЕРАЦИЯ МИРА
// Общие параметры и свойства:
_quadsTotal = 5;
_space = new Rectangle(100, 100, 400, 300);
_quads = new Vector.<Rectangle>;
_result = new Vector.<Rectangle>;
// Создаём рассекающие квадраты:
i = 0;
while (i < _quadsTotal) {
_quads[i] = createRandomQuad();
i ++;
}
//_quads.push(new Rectangle(200, 10, 10, 200));
//_quads.push(new Rectangle(300, 150, 50, 30));
// АЛГОРИТМ
// Обходим каждую сторону получившегося квадрата,
// формируя прямоугольник свободного пространства:
i = _quadsTotal;
while (i--) {
// Получаем область для каждой стороны. (Может быть null, если области не существует)
// Верхняя сторона:
quad = getFreeSpaceForTop(_quads[i]);
if (quad !== null)
_result.push(quad);
}
// РЕНДЕР.
// Рисунок:
_sprite.graphics.clear();
_sprite.x = _space.x;
_sprite.y = _space.y;
addChild(_sprite);
// Мир:
_sprite.graphics.lineStyle(1, 0x999999);
_sprite.graphics.drawRect(0, 0, _space.width, _space.height);
// Результат:
i = _result.length;
while (i--) {
quad = _result[i];
_sprite.graphics.lineStyle(1, Math.random() * 0xcccccc);
_sprite.graphics.drawRect(quad.x, quad.y, quad.width, quad.height);
}
// Квадраты:
i = _quadsTotal;
_sprite.graphics.lineStyle(1, 0x0);
_sprite.graphics.beginFill(0, 1);
while (i--) {
quad = _quads[i];
_sprite.graphics.drawRect(quad.x, quad.y, quad.width, quad.height);
}
}
// ПРИВАТ
private function createRandomQuad():Rectangle {
const minSize:uint = 10; // Минимальный размер стороны квадрата.
const maxSize:uint = 50; // Максимальный.
const quad:Rectangle = new Rectangle();
quad.width = Math.round(Math.random() * (maxSize - minSize) + minSize);
quad.height = Math.round(Math.random() * (maxSize - minSize) + minSize);
quad.x = Math.round(Math.random() * (_space.width - quad.width));
quad.y = Math.round(Math.random() * (_space.height - quad.height));
return quad;
}
private function getFreeSpaceForTop(currentQuad:Rectangle):Rectangle {
var i:uint;
var quad:Rectangle;
var free:Rectangle;
var value:Number;
var dx:Number;
var dy:Number;
// Получаем свободную область для верхней стороны.
// Получаем будущий прямоугольник области:
free = new Rectangle(0, 0, _space.width, _space.height - (_space.height - currentQuad.y));
// Обходим все имеющиеся прямоугольники:
i = _quadsTotal;
while (i--) {
quad = _quads[i];
// Проверка сама с собою пропускается:
if (quad === currentQuad)
continue;
// Пересечение свободной области с квадратом.
// Глубина пересечения по X:
if (quad.x > free.x)
dx = free.x - quad.x + free.width;
else
dx = quad.x - free.x + quad.width;
// Глубина пересечения по Y:
if (quad.y > free.y)
dy = free.y - quad.y + free.height;
else
dy = quad.y - free.y + quad.height;
// Обрезание по Y:
if (dy > 0) {
if (dx > 0) {
// Есть пересечение.
// Проверка типа пересечения, оно может быть частичным или сквозным:
if (dy < free.height) {
// Частичное пересечение.
// Выбираем способ обрезания:
if (quad.y > free.y) {
// Блок ниже нас.
// В зависимости от его расположения, обрезаемся справа или cлева:
if (quad.x > currentQuad.x) {
free.width -= dx;
}
else {
value = quad.x + quad.width;
if (value > free.x) {
free.x = value;
free.width = dx - quad.width;
}
}
}
else {
// Блок выше нас.
// Просто обрезаемся на величину пересечения:
free.y += dy;
free.height -= dy;
}
}
else {
// Сквозное пересечение.
continue;
}
}
// Нет пересечения по X.
continue;
}
// Нет пересечения по Y.
continue;
}
return free;
}
/*
private function hitTest(a:Rectangle, b:Rectangle):Boolean {
var value:Number;
// Проверка пересечеения двух прямоугольников.
// Приводим обоих в одну точку отсчёта, добавляя разницу к ширине и высоте.
// Проверка пересечения по X:
if (a.x > b.x)
value = b.x - a.x + b.width;
else
value = a.x - b.x + a.width;
if (value < 0)
return false;
// Проверка пересечения по Y:
if (a.y > b.y)
value = b.y - a.y + b.height;
else
value = a.y - b.y + a.height;
if (value < 0)
return false;
// Блоки пересекаются:
return true;
}
*/
}
}