資料結構

1type Point = { id: number; x: number; y: number };
2const CAPACITY = 4, MAX_DEPTH = 10;
3 
4class QuadNode {
5  points: Point[] | null = [];
6  children: QuadNode[] | null = null;
7  constructor(public x: number, public y: number, public size: number, public depth: number) {}
8 
9  child(p: Point): QuadNode {
10    const half = this.size / 2;
11    return this.children![(p.x >= this.x + half ? 1 : 0) + (p.y >= this.y + half ? 2 : 0)];
12  }
13}
14 
15class QuadTree {
16  root = new QuadNode(0, 0, 1, 0);
17  visited = 0;
18  checked = 0;
19 
20  insert(p: Point): void {
21    let node = this.root;
22    while (node.children) node = node.child(p);
23    node.points!.push(p);
24    if (node.points!.length > CAPACITY && node.depth < MAX_DEPTH) this.split(node);
25  }
26 
27  private split(node: QuadNode): void {
28    const half = node.size / 2;
29    node.children = [0, 1, 2, 3].map((i) =>
30      new QuadNode(node.x + (i & 1 ? half : 0), node.y + (i & 2 ? half : 0), half, node.depth + 1));
31    const moving = node.points!;
32    node.points = null;
33    for (const q of moving) node.child(q).points!.push(q);
34    for (const c of node.children) {
35      if (c.points!.length > CAPACITY && c.depth < MAX_DEPTH) this.split(c);
36    }
37  }
38 
39  query(cx: number, cy: number, r: number): number[] {
40    this.visited = 0;
41    this.checked = 0;
42    const found: number[] = [];
43    const walk = (node: QuadNode): void => {
44      const dx = Math.max(node.x - cx, 0, cx - (node.x + node.size));
45      const dy = Math.max(node.y - cy, 0, cy - (node.y + node.size));
46      if (dx * dx + dy * dy > r * r) return;
47      this.visited++;
48      if (node.children) { node.children.forEach(walk); return; }
49      for (const p of node.points!) {
50        this.checked++;
51        const ex = p.x - cx, ey = p.y - cy;
52        if (ex * ex + ey * ey <= r * r) found.push(p.id);
53      }
54    };
55    walk(this.root);
56    return found.sort((a, b) => a - b);
57  }
58}
59 
60const BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";
61 
62function geohash(x: number, y: number, chars: number): string {
63  let xlo = 0, xhi = 1, ylo = 0, yhi = 1, out = "", value = 0;
64  for (let bit = 0; bit < chars * 5; bit++) {
65    if (bit % 2 === 0) {
66      const mid = (xlo + xhi) / 2;
67      value = value * 2 + (x >= mid ? 1 : 0);
68      if (x >= mid) xlo = mid; else xhi = mid;
69    } else {
70      const mid = (ylo + yhi) / 2;
71      value = value * 2 + (y >= mid ? 1 : 0);
72      if (y >= mid) ylo = mid; else yhi = mid;
73    }
74    if (bit % 5 === 4) { out += BASE32[value]; value = 0; }
75  }
76  return out;
77}
78 
79class GeohashIndex {
80  buckets = new Map<string, Point[]>();
81  cols: number;
82  rows: number;
83  checked = 0;
84 
85  constructor(public chars: number) {
86    this.cols = 2 ** Math.ceil((chars * 5) / 2);
87    this.rows = 2 ** Math.floor((chars * 5) / 2);
88  }
89 
90  insert(p: Point): void {
91    const cell = geohash(p.x, p.y, this.chars);
92    const bucket = this.buckets.get(cell) ?? [];
93    bucket.push(p);
94    this.buckets.set(cell, bucket);
95  }
96 
97  /** Assumes r is no larger than a cell. */
98  query(cx: number, cy: number, r: number): number[] {
99    this.checked = 0;
100    const found: number[] = [];
101    const ix = Math.floor(cx * this.cols), iy = Math.floor(cy * this.rows);
102    for (let dy = -1; dy <= 1; dy++) {
103      for (let dx = -1; dx <= 1; dx++) {
104        const nx = ix + dx, ny = iy + dy;
105        if (nx < 0 || ny < 0 || nx >= this.cols || ny >= this.rows) continue;
106        const cell = geohash((nx + 0.5) / this.cols, (ny + 0.5) / this.rows, this.chars);
107        for (const p of this.buckets.get(cell) ?? []) {
108          this.checked++;
109          const ex = p.x - cx, ey = p.y - cy;
110          if (ex * ex + ey * ey <= r * r) found.push(p.id);
111        }
112      }
113    }
114    return found.sort((a, b) => a - b);
115  }
116}