Don't reload the entire bbox when panning, just the newly uncovered bits.
authorRichard Fairhurst <richard@systemeD.net>
Tue, 27 Dec 2011 15:04:56 +0000 (15:04 +0000)
committerRichard Fairhurst <richard@systemeD.net>
Tue, 27 Dec 2011 15:04:56 +0000 (15:04 +0000)
Thanks to Matt for the clever code and to Tom for helping with the AS3 port!

net/systemeD/halcyon/Map.as
net/systemeD/halcyon/connection/Connection.as
net/systemeD/halcyon/connection/XMLBaseConnection.as
net/systemeD/halcyon/connection/XMLConnection.as
net/systemeD/halcyon/connection/bboxes/Box.as [new file with mode: 0755]
net/systemeD/halcyon/connection/bboxes/FetchSet.as [new file with mode: 0644]
net/systemeD/halcyon/connection/bboxes/Interval.as [new file with mode: 0755]
potlatch2.mxml

index b84e0fc6a90e7eb6150e2da4563e5f2ed80f85f7..3902f367248f05ea2502f938472ef562443c5772 100644 (file)
@@ -222,7 +222,6 @@ package net.systemeD.halcyon {
         * The bounding box for the download is taken from the current map edges.
         */
                public function download():void {
-                       this.dispatchEvent(new MapEvent(MapEvent.DOWNLOAD, {minlon:edge_l, maxlon:edge_r, maxlat:edge_t, minlat:edge_b} ));
                        for (var i:uint=0; i<paintContainer.numChildren; i++)
                                if(getLayerAt(i).visible == true) {
                     getLayerAt(i).connection.loadBbox(edge_l,edge_r,edge_t,edge_b);
index 5893d8491f3a151fe99c3922ceb3ad6521807df6..4a7e12ba6e1b17268f256474f535be3a8e562dd6 100644 (file)
@@ -7,6 +7,7 @@ package net.systemeD.halcyon.connection {
     import net.systemeD.halcyon.AttentionEvent;
     import net.systemeD.halcyon.MapEvent;
     import net.systemeD.halcyon.connection.actions.*;
+    import net.systemeD.halcyon.connection.bboxes.*;
     import net.systemeD.halcyon.Globals;
 
        public class Connection extends EventDispatcher {
@@ -78,6 +79,10 @@ package net.systemeD.halcyon.connection {
                public static var RESUME_REDRAW:String = "resume_redraw";
         public static var TRACES_LOADED:String = "traces_loaded";
 
+               /** maximum number of /map calls to request for each pan/zoom */
+               protected const MAX_BBOXES:uint=3;
+               protected var fetchSet:FetchSet = new FetchSet(MAX_BBOXES);
+
         // store the data we download
         private var negativeID:Number = -1;
         private var nodes:Object = {};
@@ -94,7 +99,6 @@ package net.systemeD.halcyon.connection {
         private var traces:Vector.<Trace> = new Vector.<Trace>();
         private var nodePositions:Object = {};
         protected var traces_loaded:Boolean = false;
-               private var loadedBboxes:Array = [];
 
                /** maximum number of ways to keep in memory before purging */
                protected const MAXWAYS:uint=3000;
@@ -392,29 +396,12 @@ package net.systemeD.halcyon.connection {
                        return modified;
                }
 
-               // Keep track of the bboxes we've loaded
-
-               /** Has the data within this bbox already been loaded? */
-               protected function isBboxLoaded(left:Number,right:Number,top:Number,bottom:Number):Boolean {
-                       var l:Number,r:Number,t:Number,b:Number;
-                       for each (var box:Array in loadedBboxes) {
-                               l=box[0]; r=box[1]; t=box[2]; b=box[3];
-                               if (left>=l && left<=r && right>=l && right<=r && top>=b && top<=t && bottom>=b && bottom<=t) {
-                                       return true;
-                               }
-                       }
-                       return false;
-               }
-               /** Mark that bbox is loaded */
-               protected function markBboxLoaded(left:Number,right:Number,top:Number,bottom:Number):void {
-                       if (isBboxLoaded(left,right,top,bottom)) return;
-                       loadedBboxes.push([left,right,top,bottom]);
-               }
                /** Purge all data if number of ways exceeds limit */
                public function purgeIfFull(left:Number,right:Number,top:Number,bottom:Number):void {
                        if (waycount<=MAXWAYS) return;
                        purgeOutside(left,right,top,bottom);
-                       loadedBboxes=[[left,right,top,bottom]];
+                       fetchSet=new FetchSet(MAX_BBOXES);
+                       fetchSet.add(new Box().fromBbox(left,bottom,right,top));
                }
 
                // Changeset tracking
index 48159ba880ac46a68381727f8f0512c77155dcd0..1a62138c3dcca7e77f9f0d946eb65d6879a17520 100644 (file)
@@ -7,6 +7,7 @@ package net.systemeD.halcyon.connection {
        import org.iotashan.oauth.*;
 
        import net.systemeD.halcyon.MapEvent;
+    import net.systemeD.halcyon.connection.bboxes.*;
 
        /**
        * XMLBaseConnection is the common code between connecting to an OSM server
@@ -42,6 +43,7 @@ package net.systemeD.halcyon.connection {
                                        minlat=map.bounds.@minlat;
                                        maxlat=map.bounds.@maxlat;
                                        singleEntityRequest=false;
+                                       fetchSet.add(new Box().fromBbox(minlon,minlat,maxlon,maxlat));
                                }
 
                                for each(var relData:XML in map.relation) {
@@ -155,8 +157,6 @@ package net.systemeD.halcyon.connection {
                                                }
                                        }
                                }
-                       
-                               markBboxLoaded(minlon,maxlon,maxlat,minlat);
                                registerPOINodes();
                        }
 
index 9b94f2079f92792359cfcd5266fc59f2c8d6609b..d07ef96dd8e91cf80d82434a30410dbdda59323f 100644 (file)
@@ -9,6 +9,7 @@ package net.systemeD.halcyon.connection {
 
        import net.systemeD.halcyon.AttentionEvent;
        import net.systemeD.halcyon.MapEvent;
+    import net.systemeD.halcyon.connection.bboxes.*;
 
     /**
     * XMLConnection provides all the methods required to connect to a live
@@ -18,6 +19,8 @@ package net.systemeD.halcyon.connection {
     */
        public class XMLConnection extends XMLBaseConnection {
 
+               private const MARGIN:Number=0.05;
+
         /**
         * Create a new XML connection
         * @param name The name of the connection
@@ -38,21 +41,24 @@ package net.systemeD.halcyon.connection {
                override public function loadBbox(left:Number,right:Number,
                                                                top:Number,bottom:Number):void {
             purgeIfFull(left,right,top,bottom);
-            if (isBboxLoaded(left,right,top,bottom)) return;
-
-            // enlarge bbox by 20% on each edge
-            var xmargin:Number=(right-left)/5;
-            var ymargin:Number=(top-bottom)/5;
-            left-=xmargin; right+=xmargin;
-            bottom-=ymargin; top+=ymargin;
-
-            var mapVars:URLVariables = new URLVariables();
-            mapVars.bbox= left+","+bottom+","+right+","+top;
-
-            var mapRequest:URLRequest = new URLRequest(apiBaseURL+"map");
-            mapRequest.data = mapVars;
-
-            sendLoadRequest(mapRequest);
+                       var requestBox:Box=new Box().fromBbox(left,bottom,right,top);
+                       var boxes:Array=fetchSet.getBoxes(requestBox,MAX_BBOXES);
+                       for each (var box:Box in boxes) {
+                               // enlarge bbox by given margin on each edge
+                               var xmargin:Number=(box.right-box.left)*MARGIN;
+                               var ymargin:Number=(box.top-box.bottom)*MARGIN;
+                               left  =box.left  -xmargin; right=box.right+xmargin;
+                               bottom=box.bottom-ymargin; top  =box.top  +ymargin;
+
+                               dispatchEvent(new MapEvent(MapEvent.DOWNLOAD, {minlon:left, maxlon:right, maxlat:top, minlat:bottom} ));
+
+                               // send HTTP request
+                               var mapVars:URLVariables = new URLVariables();
+                               mapVars.bbox=left+","+bottom+","+right+","+top;
+                               var mapRequest:URLRequest = new URLRequest(apiBaseURL+"map");
+                               mapRequest.data = mapVars;
+                               sendLoadRequest(mapRequest);
+                       }
                }
 
                override public function loadEntityByID(type:String, id:Number):void {
@@ -76,7 +82,6 @@ package net.systemeD.halcyon.connection {
                        dispatchEvent(new Event(LOAD_COMPLETED));
         }
         private function mapLoadStatus(event:HTTPStatusEvent):void {
-            trace("loading map status = "+event.status);
         }
 
         protected var appID:OAuthConsumer;
diff --git a/net/systemeD/halcyon/connection/bboxes/Box.as b/net/systemeD/halcyon/connection/bboxes/Box.as
new file mode 100755 (executable)
index 0000000..ed9443a
--- /dev/null
@@ -0,0 +1,123 @@
+package net.systemeD.halcyon.connection.bboxes {
+       
+       public class Box {
+
+               public var x:Interval;
+               public var y:Interval;
+               
+               function Box():void {
+               }
+               
+               public function get left():Number   { return x._min; }
+               public function get right():Number  { return x._max; }
+               public function get bottom():Number { return y._min; }
+               public function get top():Number    { return y._max; }
+               
+               // Initialise from either a bbox or two Intervals
+
+               public function fromIntervals(x:Interval,y:Interval):Box {
+                       this.x=x; this.y=y;
+                       return this;
+               }
+               public function fromBbox(minx:Number,miny:Number,maxx:Number,maxy:Number):Box {
+                       x=new Interval(minx,maxx);
+                       y=new Interval(miny,maxy);
+                       return this;
+               }
+               
+               // If this box has any area, whether it contains a valid amount of space.
+
+               public function get valid():Boolean {
+                       return (x.valid && y.valid);
+               }
+
+               // Whether this box intersects another.
+
+               public function intersects(other:Box):Boolean {
+                       return (x.intersects(other.x) && y.intersects(other.y));
+               }
+               
+               // Intersection. May return a box that isn't valid.
+               public function intersection(other:Box):Box {
+                       return (new Box().fromIntervals(x.intersection(other.x), y.intersection(other.y)));
+               }
+
+               // Union. Return a Box covering this Box and the other.
+               public function union(other:Box):Box {
+                       return (new Box().fromIntervals(x.union(other.x), y.union(other.y)));
+               }
+
+               // Inverse. Returns an array of 4 Boxes covering all space except for this box.
+               public function get inverse():Array {
+                       return [
+                               new Box().fromBbox(-Infinity, y._max,    Infinity, Infinity),
+                               new Box().fromBbox(-Infinity, y._min,    x._min,   y._max  ),
+                               new Box().fromBbox(x._max,    y._min,    Infinity, y._max  ),
+                               new Box().fromBbox(-Infinity, -Infinity, Infinity, y._min  )
+                       ];
+               }
+
+               // Subtraction. take the inverse of one bbox and intersect it with this one. returns an array of Boxes.
+               public function subtract(other:Box):Array {
+                       var inverses:Array=other.inverse;
+                       var results:Array=[];
+                       var candidate:Box;
+                       for each (var i:Box in inverses) {
+                               candidate=intersection(i);
+                               if (candidate.valid) results.push(candidate);
+                       }
+                       return results;
+               }
+
+               // Subtract all Boxes in given array. Resulting set of boxes will be disjoint.
+               public function subtractAll(others:Array):Array {
+                       var memo:Array=[this];
+                       for each (var other:Box in others) {
+                               var subtracted:Array=[];
+                               for each (var b:Box in memo) {
+                                       subtracted=subtracted.concat(b.subtract(other));
+                               }
+                               memo=subtracted;
+                       }
+                       // do we need to flatten memo here?
+                       return memo;
+               }
+
+               // Is this box directly adjacent to the other, with no gap in between?
+
+               public function adjacentTo(other:Box):Boolean {
+                       return (((x.equals(other.x)) && ((y._min == other.y._max) || (y._max == other.y._min))) ||
+                                       ((y.equals(other.y)) && ((x._min == other.x._max) || (x._max == other.x._min))));
+               }
+
+               // Merge as many boxes as possible without increasing the total area of the set of boxes. This is done by
+               // identifying edges along which boxes are adjacent. Note that the input set must be disjoint.
+               //
+               // This is an O(n^2) algorithm, so it's going to be very slow on large numbers of boxes. There's 
+               // almost certainly a better algorithm out there to do the same thing in better time. but it's nice
+               // and simple.
+
+               public static function merge(boxes:Array):Array {
+                       if (boxes.length==0) return [];
+                       var first:Box=boxes.shift();
+                       var kept:Array=[];
+                       for each (var box:Box in boxes) {
+                               if (first.adjacentTo(box)) { first=first.union(box); }
+                               else kept.push(box);
+                       }
+                       return [first].concat(Box.merge(kept));
+               }
+
+               public function equals(other:Box):Boolean {
+                       return (x.equals(other.x) && y.equals(other.y));
+               }
+               
+               public function get size():Number {
+                       return (x.size*y.size);
+               }
+
+               public function toString():String {
+                       return ("Box["+x._min+","+y._min+","+x._max+","+y._max+"]");
+               }
+       }
+}
diff --git a/net/systemeD/halcyon/connection/bboxes/FetchSet.as b/net/systemeD/halcyon/connection/bboxes/FetchSet.as
new file mode 100644 (file)
index 0000000..a43c511
--- /dev/null
@@ -0,0 +1,88 @@
+package net.systemeD.halcyon.connection.bboxes {
+       
+       public class FetchSet {
+
+               private var existing:Array;
+
+               function FetchSet(max:int):void {
+                       existing=[];
+               }
+
+               public function getBoxes(bbox:Box,maxBoxes:uint):Array {
+                       var bits:Array=Box.merge(bbox.subtractAll(existing));
+                       var toFetch:Array=optimalPart(maxBoxes,bits);
+                       return toFetch;
+               }
+               
+               public function add(bbox:Box):void {
+                       existing.push(bbox);
+               }
+
+               private function partitions(set:Array, yield:Function):void {
+                       if (set.length==0) { yield([]); return; }
+                       var z:Number=Math.pow(2,set.length)/2;
+                       for (var i:uint=0; i<z; i++) {
+                               var parts:Array= [ [], [] ];
+                               var c:uint=i;
+                               for each (var item:Box in set) {
+                                       parts[c & 1].push(item);
+                                       c>>=1;
+                               }
+                               partitions(parts[1],function(b:Array):void {
+                                       var result:Array;
+                                       if (b.length) { result=[parts[0]].concat(b); } else { result=[parts[0]]; }
+                                       yield(result);
+                               });
+                       }
+               }
+               
+               // select only the partitions of the set which have a certain size, or smaller
+
+               private function partsOfSize(n:int, set:Array):Array {
+                       var rv:Array=[];
+                       partitions(set, function(x:Array):void {
+                               if (x.length<=n) rv.push(x);
+                       });
+                       return rv;
+               }
+
+               // find the optimal partition - the one which requests the smallest amount of extra space - 
+               // given the set p of partitions
+
+               private function optimalPart(n:int, set:Array):Array {
+                       var p:Array=partsOfSize(n,set);
+                       var q:Array=p.sort(function(a:Array,b:Array):Number {
+                               var aw:Number = wasteSize(a, set);
+                               var bw:Number = wasteSize(b, set);
+                               if (aw < bw) return -1;
+                               else if (aw > bw) return 1;
+                               else return 0;
+                       });
+                       return unionPartitions(q[0]);
+               }
+
+               private function wasteSize(boxes:Array, set:Array):Number {
+                       var waste:Number = 0;
+                       unionPartitions(boxes).forEach(function(b:Box,index:int,array:Array):void {
+                               var included:Number = 0;
+                               set.forEach(function(s:Box,index:int,array:Array):void {
+                                       s = s.intersection(b);
+                                       if (s.valid) included += s.size;
+                               });
+                               waste += b.size - included;
+                       });
+                       return waste;
+               }
+
+               private function unionPartitions(a:Array):Array {
+                       return a.map(function(bs:Array,index:int,array:Array):Box {
+                               var box:Box = bs[0];
+                               bs.forEach(function(b:Box,index:int,array:Array):void {
+                                       box=box.union(b);
+                               });
+                               return box;
+                       });
+               }
+
+       }
+}
diff --git a/net/systemeD/halcyon/connection/bboxes/Interval.as b/net/systemeD/halcyon/connection/bboxes/Interval.as
new file mode 100755 (executable)
index 0000000..3d54e4c
--- /dev/null
@@ -0,0 +1,68 @@
+package net.systemeD.halcyon.connection.bboxes {
+       
+       public class Interval {
+
+               public var _min:Number;
+               public var _max:Number;
+               
+               function Interval(min:Number,max:Number):void {
+                       _min=min;
+                       _max=max;
+               }
+
+               public function contains(x:Number):Boolean { return (x>=_min && x<_max); }
+               public function get valid():Boolean { return (_max>_min); }
+               public function get size():Number { return (_max-_min); }
+
+               public function intersects(other:Interval):Boolean { return (_max>other._min && _min<other._max); }
+               public function equals(other:Interval):Boolean { return (_min==other._min && _max==other._max); }
+               public function union(other:Interval):Interval { return new Interval(Math.min(_min,other._min), Math.max(_max,other._max)); }
+               public function intersection(other:Interval):Interval { return new Interval(Math.max(_min,other._min), Math.min(_max,other._max)); }
+               
+               public function toString():String { return ("Interval["+_min+","+_max+"]"); }
+
+               // Merge an array of possibly overlapping intervals into a set of disjoint intervals.
+               public static function merge(intervals:Array):Array {
+                       intervals.sort(compareMinimum);
+                       var memo:Array=[];
+                       for each (var elem:Interval in intervals) {
+                               var last:Interval=memo.pop();
+                               if (!last) { 
+                                       memo=[elem];
+                               } else if (last.intersects(elem)) {
+                                       memo.push(last.union(elem));
+                               } else {
+                                       memo.push(last);
+                                       memo.push(elem);
+                               }
+                       }
+                       return memo;
+               }
+
+               // Returns the largest empty interval in the given set of intervals.
+               
+               public static function largestEmpty(intervals:Array):Interval {
+                       var gaps:Array=[];
+                       intervals=merge(intervals);
+                       for (var i:uint=0; i<=intervals.length-2; i++) {
+                               gaps.push(new Interval(intervals[i]._max, intervals[i+1]._min));
+                       }
+                       gaps.sort(compareSize);
+                       return gaps[gaps.length-1];
+               }
+
+               // Comparison methods for sorting
+
+               private static function compareMinimum(a:Interval, b:Interval):int {
+                       if (a._min>b._min) { return 1; }
+                       if (a._min<b._min) { return -1; }
+                       return 0;
+               }
+
+               private static function compareSize(a:Interval, b:Interval):int {
+                       if (a.size>b.size) { return 1; }
+                       if (a.size<b.size) { return -1; }
+                       return 0;
+               }
+       }
+}
index 32bb6d19bf733b15bb1b5787aab287d397cc3bdd..52d44d72cf58d7526ab9a2b15bc4d809dcb73c05 100644 (file)
             updateDataWorking();
         }
                private function updateDataWorking():void {
-                       if (loadcount>0 && savecount>0) { dataWorking.text="Loading/saving..."; }
-                       else if (loadcount>0)           { dataWorking.text="Loading data..."; }
-                       else if (savecount>0)           { dataWorking.text="Saving data..."; }
-                       else                            { dataWorking.text=""; }
+                       var t:String;
+                       if (loadcount>0 && savecount>0) { t="Loading/saving#..."; }
+                       else if (loadcount>0)           { t="Loading data#..."; }
+                       else if (savecount>0)           { t="Saving data..."; }
+                       else                            { t=""; }
+                       dataWorking.text=t.replace("#",(loadcount>1) ? (" ("+loadcount+")") : "");
                        dataWorking.visible=(dataWorking.text!="");
                }
         private function onDataDirty(event:Event):void {