1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
L.DistanceGrid = function (cellSize) {
this._cellSize = cellSize;
this._sqCellSize = cellSize * cellSize;
this._grid = {};
this._objectPoint = { };
};
L.DistanceGrid.prototype = {
addObject: function (obj, point) {
var x = this._getCoord(point.x),
y = this._getCoord(point.y),
grid = this._grid,
row = grid[y] = grid[y] || {},
cell = row[x] = row[x] || [],
stamp = L.Util.stamp(obj);
this._objectPoint[stamp] = point;
cell.push(obj);
},
updateObject: function (obj, point) {
this.removeObject(obj);
this.addObject(obj, point);
},
//Returns true if the object was found
removeObject: function (obj, point) {
var x = this._getCoord(point.x),
y = this._getCoord(point.y),
grid = this._grid,
row = grid[y] = grid[y] || {},
cell = row[x] = row[x] || [],
i, len;
delete this._objectPoint[L.Util.stamp(obj)];
for (i = 0, len = cell.length; i < len; i++) {
if (cell[i] === obj) {
cell.splice(i, 1);
if (len === 1) {
delete row[x];
}
return true;
}
}
},
eachObject: function (fn, context) {
var i, j, k, len, row, cell, removed,
grid = this._grid;
for (i in grid) {
row = grid[i];
for (j in row) {
cell = row[j];
for (k = 0, len = cell.length; k < len; k++) {
removed = fn.call(context, cell[k]);
if (removed) {
k--;
len--;
}
}
}
}
},
getNearObject: function (point) {
var x = this._getCoord(point.x),
y = this._getCoord(point.y),
i, j, k, row, cell, len, obj, dist,
objectPoint = this._objectPoint,
closestDistSq = this._sqCellSize,
closest = null;
for (i = y - 1; i <= y + 1; i++) {
row = this._grid[i];
if (row) {
for (j = x - 1; j <= x + 1; j++) {
cell = row[j];
if (cell) {
for (k = 0, len = cell.length; k < len; k++) {
obj = cell[k];
dist = this._sqDist(objectPoint[L.Util.stamp(obj)], point);
if (dist < closestDistSq ||
dist <= closestDistSq && closest === null) {
closestDistSq = dist;
closest = obj;
}
}
}
}
}
}
return closest;
},
_getCoord: function (x) {
var coord = Math.floor(x / this._cellSize);
return isFinite(coord) ? coord : x;
},
_sqDist: function (p, p2) {
var dx = p2.x - p.x,
dy = p2.y - p.y;
return dx * dx + dy * dy;
}
};
|
