]> git.openstreetmap.org Git - potlatch2.git/blob - net/systemeD/halcyon/connection/bboxes/FetchSet.as
Don't reload the entire bbox when panning, just the newly uncovered bits.
[potlatch2.git] / net / systemeD / halcyon / connection / bboxes / FetchSet.as
1 package net.systemeD.halcyon.connection.bboxes {
2         
3         public class FetchSet {
4
5                 private var existing:Array;
6
7                 function FetchSet(max:int):void {
8                         existing=[];
9                 }
10
11                 public function getBoxes(bbox:Box,maxBoxes:uint):Array {
12                         var bits:Array=Box.merge(bbox.subtractAll(existing));
13                         var toFetch:Array=optimalPart(maxBoxes,bits);
14                         return toFetch;
15                 }
16                 
17                 public function add(bbox:Box):void {
18                         existing.push(bbox);
19                 }
20
21                 private function partitions(set:Array, yield:Function):void {
22                         if (set.length==0) { yield([]); return; }
23                         var z:Number=Math.pow(2,set.length)/2;
24                         for (var i:uint=0; i<z; i++) {
25                                 var parts:Array= [ [], [] ];
26                                 var c:uint=i;
27                                 for each (var item:Box in set) {
28                                         parts[c & 1].push(item);
29                                         c>>=1;
30                                 }
31                                 partitions(parts[1],function(b:Array):void {
32                                         var result:Array;
33                                         if (b.length) { result=[parts[0]].concat(b); } else { result=[parts[0]]; }
34                                         yield(result);
35                                 });
36                         }
37                 }
38                 
39                 // select only the partitions of the set which have a certain size, or smaller
40
41                 private function partsOfSize(n:int, set:Array):Array {
42                         var rv:Array=[];
43                         partitions(set, function(x:Array):void {
44                                 if (x.length<=n) rv.push(x);
45                         });
46                         return rv;
47                 }
48
49                 // find the optimal partition - the one which requests the smallest amount of extra space - 
50                 // given the set p of partitions
51
52                 private function optimalPart(n:int, set:Array):Array {
53                         var p:Array=partsOfSize(n,set);
54                         var q:Array=p.sort(function(a:Array,b:Array):Number {
55                                 var aw:Number = wasteSize(a, set);
56                                 var bw:Number = wasteSize(b, set);
57                                 if (aw < bw) return -1;
58                                 else if (aw > bw) return 1;
59                                 else return 0;
60                         });
61                         return unionPartitions(q[0]);
62                 }
63
64                 private function wasteSize(boxes:Array, set:Array):Number {
65                         var waste:Number = 0;
66                         unionPartitions(boxes).forEach(function(b:Box,index:int,array:Array):void {
67                                 var included:Number = 0;
68                                 set.forEach(function(s:Box,index:int,array:Array):void {
69                                         s = s.intersection(b);
70                                         if (s.valid) included += s.size;
71                                 });
72                                 waste += b.size - included;
73                         });
74                         return waste;
75                 }
76
77                 private function unionPartitions(a:Array):Array {
78                         return a.map(function(bs:Array,index:int,array:Array):Box {
79                                 var box:Box = bs[0];
80                                 bs.forEach(function(b:Box,index:int,array:Array):void {
81                                         box=box.union(b);
82                                 });
83                                 return box;
84                         });
85                 }
86
87         }
88 }