net/systemeD/halcyon/connection/bboxes/Box.as

   1 package net.systemeD.halcyon.connection.bboxes {
   2
   3         public class Box {
   4
   5                 public var x:Interval;
   6                 public var y:Interval;
   7
   8                 function Box():void {
   9                 }
  10
  11                 public function get left():Number   { return x._min; }
  12                 public function get right():Number  { return x._max; }
  13                 public function get bottom():Number { return y._min; }
  14                 public function get top():Number    { return y._max; }
  15
  16                 // Initialise from either a bbox or two Intervals
  17
  18                 public function fromIntervals(x:Interval,y:Interval):Box {
  19                         this.x=x; this.y=y;
  20                         return this;
  21                 }
  22                 public function fromBbox(minx:Number,miny:Number,maxx:Number,maxy:Number):Box {
  23                         x=new Interval(minx,maxx);
  24                         y=new Interval(miny,maxy);
  25                         return this;
  26                 }
  27
  28                 // If this box has any area, whether it contains a valid amount of space.
  29
  30                 public function get valid():Boolean {
  31                         return (x.valid && y.valid);
  32                 }
  33
  34                 // Whether this box intersects another.
  35
  36                 public function intersects(other:Box):Boolean {
  37                         return (x.intersects(other.x) && y.intersects(other.y));
  38                 }
  39
  40                 // Intersection. May return a box that isn't valid.
  41                 public function intersection(other:Box):Box {
  42                         return (new Box().fromIntervals(x.intersection(other.x), y.intersection(other.y)));
  43                 }
  44
  45                 // Union. Return a Box covering this Box and the other.
  46                 public function union(other:Box):Box {
  47                         return (new Box().fromIntervals(x.union(other.x), y.union(other.y)));
  48                 }
  49
  50                 // Inverse. Returns an array of 4 Boxes covering all space except for this box.
  51                 public function get inverse():Array {
  52                         return [
  53                                 new Box().fromBbox(-Infinity, y._max,    Infinity, Infinity),
  54                                 new Box().fromBbox(-Infinity, y._min,    x._min,   y._max  ),
  55                                 new Box().fromBbox(x._max,    y._min,    Infinity, y._max  ),
  56                                 new Box().fromBbox(-Infinity, -Infinity, Infinity, y._min  )
  57                         ];
  58                 }
  59
  60                 // Subtraction. take the inverse of one bbox and intersect it with this one. returns an array of Boxes.
  61                 public function subtract(other:Box):Array {
  62                         var inverses:Array=other.inverse;
  63                         var results:Array=[];
  64                         var candidate:Box;
  65                         for each (var i:Box in inverses) {
  66                                 candidate=intersection(i);
  67                                 if (candidate.valid) results.push(candidate);
  68                         }
  69                         return results;
  70                 }
  71
  72                 // Subtract all Boxes in given array. Resulting set of boxes will be disjoint.
  73                 public function subtractAll(others:Array):Array {
  74                         var memo:Array=[this];
  75                         for each (var other:Box in others) {
  76                                 var subtracted:Array=[];
  77                                 for each (var b:Box in memo) {
  78                                         subtracted=subtracted.concat(b.subtract(other));
  79                                 }
  80                                 memo=subtracted;
  81                         }
  82                         // do we need to flatten memo here?
  83                         return memo;
  84                 }
  85
  86                 // Is this box directly adjacent to the other, with no gap in between?
  87
  88                 public function adjacentTo(other:Box):Boolean {
  89                         return (((x.equals(other.x)) && ((y._min == other.y._max) || (y._max == other.y._min))) ||
  90                                         ((y.equals(other.y)) && ((x._min == other.x._max) || (x._max == other.x._min))));
  91                 }
  92
  93                 // Merge as many boxes as possible without increasing the total area of the set of boxes. This is done by
  94                 // identifying edges along which boxes are adjacent. Note that the input set must be disjoint.
  95                 //
  96                 // This is an O(n^2) algorithm, so it's going to be very slow on large numbers of boxes. There's
  97                 // almost certainly a better algorithm out there to do the same thing in better time. but it's nice
  98                 // and simple.
  99
 100                 public static function merge(boxes:Array):Array {
 101                         if (boxes.length==0) return [];
 102                         var first:Box=boxes.shift();
 103                         var kept:Array=[];
 104                         for each (var box:Box in boxes) {
 105                                 if (first.adjacentTo(box)) { first=first.union(box); }
 106                                 else kept.push(box);
 107                         }
 108                         return [first].concat(Box.merge(kept));
 109                 }
 110
 111                 public function equals(other:Box):Boolean {
 112                         return (x.equals(other.x) && y.equals(other.y));
 113                 }
 114
 115                 public function get size():Number {
 116                         return (x.size*y.size);
 117                 }
 118
 119                 public function toString():String {
 120                         return ("Box["+x._min+","+y._min+","+x._max+","+y._max+"]");
 121                 }
 122         }
 123 }