// Name: KDTree.JavaScript.debug.js
// Assembly: Zebra.Web.Mapping
// Version: 1.0.0.0
// FileVersion: 1.0.0.0
// KDTree.JavaScript.js
//
KDTree = new Object();
//Type.createNamespace('KDTree');
////////////////////////////////////////////////////////////////////////////////
// KDTree._hPoint
KDTree._hPoint = function KDTree__hPoint(x, n) {
///
/// Hyper-Point class supporting KDTree class
///
///
///
///
///
///
///
this.coord = new Array(x.length);
for (var i = 0; i < x.length; ++i) {
this.coord[i] = x[i];
}
}
KDTree._hPoint.sqrdist = function KDTree__hPoint$sqrdist(x, y) {
///
///
///
///
///
var dist = 0;
for (var i = 0; i < x.coord.length; ++i) {
var diff = (x.coord[i] - y.coord[i]);
dist += (diff * diff);
}
return dist;
}
KDTree._hPoint.eucdist = function KDTree__hPoint$eucdist(x, y) {
///
///
///
///
///
return Math.sqrt(KDTree._hPoint.sqrdist(x, y));
}
KDTree._hPoint.prototype = {
coord: null,
clone: function KDTree__hPoint$clone() {
///
return new KDTree._hPoint(this.coord, this.coord.length);
},
equals: function KDTree__hPoint$equals(p) {
///
///
///
for (var i = 0; i < this.coord.length; ++i) {
if (this.coord[i] !== p.coord[i]) {
return false;
}
}
return true;
},
toString: function KDTree__hPoint$toString() {
///
var s = '';
for (var i = 0; i < this.coord.length; ++i) {
s = s + this.coord[i] + ' ';
}
return s;
}
}
////////////////////////////////////////////////////////////////////////////////
// KDTree._hRect
KDTree._hRect = function KDTree__hRect(vmin, vmax) {
///
/// Hyper-Rectangle class supporting KDTree class
///
///
///
///
///
///
///
///
///
this.min = vmin.clone();
this.max = vmax.clone();
}
KDTree._hRect.infiniteHRect = function KDTree__hRect$infiniteHRect(d) {
///
///
///
var vmin = new KDTree._hPoint(new Array(d), d);
var vmax = new KDTree._hPoint(new Array(d), d);
for (var i = 0; i < d; ++i) {
vmin.coord[i] = Number.NEGATIVE_INFINITY;
vmax.coord[i] = Number.POSITIVE_INFINITY;
}
return new KDTree._hRect(vmin, vmax);
}
KDTree._hRect.prototype = {
min: null,
max: null,
clone: function KDTree__hRect$clone() {
///
return new KDTree._hRect(this.min, this.max);
},
closest: function KDTree__hRect$closest(t) {
///
///
///
var p = new KDTree._hPoint(new Array(t.coord.length), t.coord.length);
for (var i = 0; i < t.coord.length; ++i) {
if (t.coord[i] <= this.min.coord[i]) {
p.coord[i] = this.min.coord[i];
}
else if (t.coord[i] >= this.max.coord[i]) {
p.coord[i] = this.max.coord[i];
}
else {
p.coord[i] = t.coord[i];
}
}
return p;
},
intersection: function KDTree__hRect$intersection(r) {
///
///
///
var newmin = new KDTree._hPoint(new Array(this.min.coord.length), this.min.coord.length);
var newmax = new KDTree._hPoint(new Array(this.min.coord.length), this.min.coord.length);
for (var i = 0; i < this.min.coord.length; ++i) {
newmin.coord[i] = Math.max(this.min.coord[i], r.min.coord[i]);
newmax.coord[i] = Math.min(this.max.coord[i], r.max.coord[i]);
if (newmin.coord[i] >= newmax.coord[i]) {
return null;
}
}
return new KDTree._hRect(newmin, newmax);
},
area: function KDTree__hRect$area() {
///
var a = 1;
for (var i = 0; i < this.min.coord.length; ++i) {
a *= (this.max.coord[i] - this.min.coord[i]);
}
return a;
},
toString: function KDTree__hRect$toString() {
///
return this.min + '\n' + this.max + '\n';
}
}
////////////////////////////////////////////////////////////////////////////////
// KDTree.KDTree
KDTree.KDTree = function KDTree_KDTree(k) {
///
///
///
///
///
///
///
///
this._m_K = k;
this._m_root = null;
}
KDTree.KDTree.prototype = {
_m_K: 0,
_m_root: null,
_m_count: 0,
insert: function KDTree_KDTree$insert(key, value) {
///
///
///
///
if (key.length !== this._m_K) {
throw new Error('KeySize');
}
else {
try {
this._m_root = KDTree._kdNode.ins(new KDTree._hPoint(key, key.length), value, this._m_root, 0, this._m_K);
}
catch (e) {
throw e;
}
}
this._m_count++;
},
search: function KDTree_KDTree$search(key) {
///
///
///
if (key.length !== this._m_K) {
throw new Error('KeySize');
}
var kd = KDTree._kdNode.srch(new KDTree._hPoint(key, key.length), this._m_root, this._m_K);
return ((!kd) ? null : kd.v);
},
remove: function KDTree_KDTree$remove(key) {
///
///
if (key.length !== this._m_K) {
throw new Error('KeySize');
}
else {
var t = KDTree._kdNode.srch(new KDTree._hPoint(key, key.length), this._m_root, this._m_K);
if (!t) {
throw new Error('KeyMissing');
}
else {
t.deleted = true;
}
this._m_count--;
}
},
nearest: function KDTree_KDTree$nearest(key, n) {
///
///
///
///
///
if (n < 0 || n > this._m_count) {
throw new Error('Number of neighbors cannot be negative or greater than number of nodes');
}
if (key.length !== this._m_K) {
throw new Error('KeySize');
}
var nbrs = new Array(n);
var nnl = new KDTree._nearestNeighborList(n);
var hr = KDTree._hRect.infiniteHRect(key.length);
var max_dist_sqd = Number.MAX_VALUE;
var keyp = new KDTree._hPoint(key, key.length);
KDTree._kdNode.nnbr(this._m_root, keyp, hr, max_dist_sqd, 0, this._m_K, nnl);
for (var i = 0; i < n; ++i) {
var kd = nnl.removeHighest();
nbrs[n - i - 1] = kd.v;
}
return nbrs;
},
range: function KDTree_KDTree$range(lowk, uppk) {
///
///
///
///
///
if (lowk.length !== uppk.length) {
throw new Error('KeySize');
}
else if (lowk.length !== this._m_K) {
throw new Error('KeySize');
}
else {
var v = [];
KDTree._kdNode.rsearch(new KDTree._hPoint(lowk, lowk.length), new KDTree._hPoint(uppk, uppk.length), this._m_root, 0, this._m_K, v);
var o = new Array(v.length);
for (var i = 0; i < v.length; ++i) {
var n = v[i];
o[i] = n.v;
}
return o;
}
},
toString: function KDTree_KDTree$toString() {
///
return this._m_root.toString(0);
},
itemCount: function () {return this._m_count;}
}
////////////////////////////////////////////////////////////////////////////////
// KDTree._kdNode
KDTree._kdNode = function KDTree__kdNode(key, val) {
///
/// K-D Tree node class
///
///
///
///
///
///
///
///
///
///
///
///
///
///
///
this.k = key;
this.v = val;
this.left = null;
this.right = null;
this.deleted = false;
}
KDTree._kdNode.ins = function KDTree__kdNode$ins(key, val, t, lev, K) {
///
///
///
///
///
///
///
///
///
///
///
if (!t) {
t = new KDTree._kdNode(key, val);
}
else if (key.equals(t.k)) {
if (t.deleted) {
t.deleted = false;
t.v = val;
}
else {
//throw (new Error('KeyDuplicate'));
}
}
else if (key.coord[lev] > t.k.coord[lev]) {
t.right = KDTree._kdNode.ins(key, val, t.right, (lev + 1) % K, K);
}
else {
t.left = KDTree._kdNode.ins(key, val, t.left, (lev + 1) % K, K);
}
return t;
}
KDTree._kdNode.srch = function KDTree__kdNode$srch(key, t, K) {
///
///
///
///
///
///
///
for (var lev = 0; t; lev = (lev + 1) % K) {
if (!t.deleted && key.equals(t.k)) {
return t;
}
else if (key.coord[lev] > t.k.coord[lev]) {
t = t.right;
}
else {
t = t.left;
}
}
return null;
}
KDTree._kdNode.rsearch = function KDTree__kdNode$rsearch(lowk, uppk, t, lev, K, v) {
///
///
///
///
///
///
///
///
///
///
///
///
if (!t) {
return;
}
if (lowk.coord[lev] <= t.k.coord[lev]) {
KDTree._kdNode.rsearch(lowk, uppk, t.left, (lev + 1) % K, K, v);
}
var j;
for (j = 0; j < K && lowk.coord[j] <= t.k.coord[j] && uppk.coord[j] >= t.k.coord[j]; j++) {
}
if (j == K) {
v.push(t);
}
if (uppk.coord[lev] > t.k.coord[lev]) {
KDTree._kdNode.rsearch(lowk, uppk, t.right, (lev + 1) % K, K, v);
}
}
KDTree._kdNode.nnbr = function KDTree__kdNode$nnbr(kd, target, hr, max_dist_sqd, lev, K, nnl) {
///
///
///
///
///
///
///
///
///
///
///
///
///
///
if (!kd) {
return;
}
var s = lev % K;
var pivot = kd.k;
var pivot_to_target = KDTree._hPoint.sqrdist(pivot, target);
var left_hr = hr;
var right_hr = hr.clone();
left_hr.max.coord[s] = pivot.coord[s];
right_hr.min.coord[s] = pivot.coord[s];
var target_in_left = target.coord[s] < pivot.coord[s];
var nearer_kd;
var nearer_hr;
var further_kd;
var further_hr;
if (target_in_left) {
nearer_kd = kd.left;
nearer_hr = left_hr;
further_kd = kd.right;
further_hr = right_hr;
}
else {
nearer_kd = kd.right;
nearer_hr = right_hr;
further_kd = kd.left;
further_hr = left_hr;
}
KDTree._kdNode.nnbr(nearer_kd, target, nearer_hr, max_dist_sqd, lev + 1, K, nnl);
var nearest = nnl.getHighest();
var dist_sqd;
if (!nnl.isCapacityReached()) {
dist_sqd = Number.MAX_VALUE;
}
else {
dist_sqd = nnl.getMaxPriority();
}
max_dist_sqd = Math.min(max_dist_sqd, dist_sqd);
var closest = further_hr.closest(target);
if (KDTree._hPoint.eucdist(closest, target) < Math.sqrt(max_dist_sqd)) {
if (pivot_to_target < dist_sqd) {
nearest = kd;
dist_sqd = pivot_to_target;
if (!kd.deleted) {
nnl.insert(kd, dist_sqd);
}
if (nnl.isCapacityReached()) {
max_dist_sqd = nnl.getMaxPriority();
}
else {
max_dist_sqd = Number.MAX_VALUE;
}
}
KDTree._kdNode.nnbr(further_kd, target, further_hr, max_dist_sqd, lev + 1, K, nnl);
var temp_nearest = nnl.getHighest();
var temp_dist_sqd = nnl.getMaxPriority();
if (temp_dist_sqd < dist_sqd) {
nearest = temp_nearest;
dist_sqd = temp_dist_sqd;
}
}
else if (pivot_to_target < max_dist_sqd) {
nearest = kd;
dist_sqd = pivot_to_target;
}
}
KDTree._kdNode._pad = function KDTree__kdNode$_pad(n) {
///
///
///
var s = '';
for (var i = 0; i < n; ++i) {
s += ' ';
}
return s;
}
KDTree._kdNode._hrcopy = function KDTree__kdNode$_hrcopy(hr_src, hr_dst) {
///
///
///
///
KDTree._kdNode._hpcopy(hr_src.min, hr_dst.min);
KDTree._kdNode._hpcopy(hr_src.max, hr_dst.max);
}
KDTree._kdNode._hpcopy = function KDTree__kdNode$_hpcopy(hp_src, hp_dst) {
///
///
///
///
for (var i = 0; i < hp_dst.coord.length; ++i) {
hp_dst.coord[i] = hp_src.coord[i];
}
}
KDTree._kdNode.prototype = {
k: null,
v: null,
left: null,
right: null,
deleted: false,
toString: function KDTree__kdNode$toString(depth) {
///
///
///
var s = this.k + ' ' + this.v + ((this.deleted) ? '*' : '');
if (this.left) {
s = s + '\n' + KDTree._kdNode._pad(depth) + 'L ' + this.left.toString(depth + 1);
}
if (this.right) {
s = s + '\n' + KDTree._kdNode._pad(depth) + 'R ' + this.right.toString(depth + 1);
}
return s;
}
}
////////////////////////////////////////////////////////////////////////////////
// KDTree._nearestNeighborList
KDTree._nearestNeighborList = function KDTree__nearestNeighborList(capacity) {
///
/// Bjoern Heckel's solution to the KD-Tree n-nearest-neighbor problem
///
///
///
///
///
///
///
///
///
///
///
this.m_Capacity = capacity;
this.m_Queue = new KDTree._priorityQueue(this.m_Capacity, Number.POSITIVE_INFINITY);
}
KDTree._nearestNeighborList.prototype = {
m_Queue: null,
m_Capacity: 0,
getMaxPriority: function KDTree__nearestNeighborList$getMaxPriority() {
///
if (!this.m_Queue.length()) {
return Number.POSITIVE_INFINITY;
}
return this.m_Queue.getMaxPriority();
},
insert: function KDTree__nearestNeighborList$insert(_object, priority) {
///
///
///
///
///
if (this.m_Queue.length() < this.m_Capacity) {
this.m_Queue.add(_object, priority);
return true;
}
if (priority > this.m_Queue.getMaxPriority()) {
return false;
}
this.m_Queue.remove();
this.m_Queue.add(_object, priority);
return true;
},
isCapacityReached: function KDTree__nearestNeighborList$isCapacityReached() {
///
return this.m_Queue.length() >= this.m_Capacity;
},
getHighest: function KDTree__nearestNeighborList$getHighest() {
///
return this.m_Queue.front();
},
isEmpty: function KDTree__nearestNeighborList$isEmpty() {
///
return !this.m_Queue.length();
},
getSize: function KDTree__nearestNeighborList$getSize() {
///
return this.m_Queue.length();
},
removeHighest: function KDTree__nearestNeighborList$removeHighest() {
///
return this.m_Queue.remove();
}
}
////////////////////////////////////////////////////////////////////////////////
// KDTree._priorityQueue
KDTree._priorityQueue = function KDTree__priorityQueue(capacity, maxPriority) {
///
///
///
///
///
///
///
///
///
///
///
///
///
///
this._maxPriority = Number.POSITIVE_INFINITY;
this._maxPriority = maxPriority;
this._init(capacity);
}
KDTree._priorityQueue.prototype = {
_data: null,
_value: null,
_count: 0,
_capacity: 0,
_init: function KDTree__priorityQueue$_init(size) {
///
///
this._capacity = size;
this._data = new Array(this._capacity + 1);
this._value = new Array(this._capacity + 1);
this._value[0] = this._maxPriority;
this._data[0] = null;
},
add: function KDTree__priorityQueue$add(element, priority) {
///
///
///
///
if (this._count++ >= this._capacity) {
this._expandCapacity();
}
this._value[this._count] = priority;
this._data[this._count] = element;
this._bubbleUp(this._count);
},
remove: function KDTree__priorityQueue$remove() {
///
if (!this._count) {
return null;
}
var element = this._data[1];
this._data[1] = this._data[this._count];
this._value[1] = this._value[this._count];
this._data[this._count] = null;
this._value[this._count] = 0;
this._count--;
this._bubbleDown(1);
return element;
},
front: function KDTree__priorityQueue$front() {
///
return this._data[1];
},
getMaxPriority: function KDTree__priorityQueue$getMaxPriority() {
///
return this._value[1];
},
_bubbleDown: function KDTree__priorityQueue$_bubbleDown(pos) {
///
///
var element = this._data[pos];
var priority = this._value[pos];
var child;
for (; pos * 2 <= this._count; pos = child) {
child = pos * 2;
if (child !== this._count) {
if (this._value[child] < this._value[child + 1]) {
child++;
}
}
if (priority < this._value[child]) {
this._value[pos] = this._value[child];
this._data[pos] = this._data[child];
}
else {
break;
}
}
this._value[pos] = priority;
this._data[pos] = element;
},
_bubbleUp: function KDTree__priorityQueue$_bubbleUp(pos) {
///
///
var element = this._data[pos];
var priority = this._value[pos];
while (this._value[pos / 2] < priority) {
this._value[pos] = this._value[pos / 2];
this._data[pos] = this._data[pos / 2];
pos /= 2;
}
this._value[pos] = priority;
this._data[pos] = element;
},
_expandCapacity: function KDTree__priorityQueue$_expandCapacity() {
this._capacity = this._count * 2;
},
clear: function KDTree__priorityQueue$clear() {
for (var i = 1; i < this._count; i++) {
this._data[i] = null;
}
this._count = 0;
},
length: function KDTree__priorityQueue$length() {
///
return this._count;
}
}
// ---- Do not remove this footer ----
// Generated using Script# v0.5.1.0 (http://projects.nikhilk.net)
// -----------------------------------