-
-
Notifications
You must be signed in to change notification settings - Fork 150
/
spatial-grid2.ts
69 lines (63 loc) · 1.99 KB
/
spatial-grid2.ts
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
import type { Fn, Nullable, Pair } from "@thi.ng/api";
import { isNumber } from "@thi.ng/checks/is-number";
import { Heap } from "@thi.ng/heaps/heap";
import { clamp } from "@thi.ng/math/interval";
import type { ReadonlyVec, Vec } from "@thi.ng/vectors";
import { addN2 } from "@thi.ng/vectors/addn";
import { distSq2 } from "@thi.ng/vectors/distsq";
import { subN2 } from "@thi.ng/vectors/subn";
import { ASpatialGrid } from "./aspatial-grid.js";
import { __addResults, CMP } from "./utils.js";
const TMP: Vec = [];
export class SpatialGrid2<K extends ReadonlyVec, V> extends ASpatialGrid<K, V> {
constructor(
min: ReadonlyVec,
size: ReadonlyVec,
res: ReadonlyVec | number
) {
super(min, size, isNumber(res) ? [res, res] : res);
this._cells = new Array(this._res[0] * this._res[1]);
}
copy(): SpatialGrid2<K, V> {
return <SpatialGrid2<K, V>>super.copy();
}
empty() {
return new SpatialGrid2<K, V>(this._min, this._size, this._res);
}
protected doQuery<T>(
fn: Fn<Pair<K, V>, T>,
k: K,
r: number,
limit = Infinity,
acc: T[] = []
) {
const id1 = this.findIndex(subN2(TMP, k, r));
const id2 = this.findIndex(addN2(TMP, k, r));
const stride = this._res[0];
const x1 = id1 % stride;
const x2 = id2 % stride;
const y1 = ((id1 / stride) | 0) * stride;
const y2 = ((id2 / stride) | 0) * stride;
const cells = this._cells;
let c: Nullable<Pair<K, V>[]>;
let x: number, y: number;
r *= r;
const heap = new Heap<[number, Nullable<Pair<K, V>>?]>([[r]], {
compare: CMP,
});
const sel = heap.values;
for (y = y1; y <= y2; y += stride) {
for (x = x1; x <= x2; x++) {
c = cells[y + x];
c && c.length && this.queryCell(distSq2, heap, c, k, limit);
}
}
return __addResults(fn, sel, acc);
}
protected findIndex(k: ReadonlyVec) {
const { _min: min, _res1: res1, _invSize: invSize } = this;
const kx = clamp((k[0] - min[0]) * invSize[0], 0, res1[0]);
const ky = clamp((k[1] - min[1]) * invSize[1], 0, res1[1]);
return (kx | 0) + (ky | 0) * this._res[0];
}
}