Uzamsal ve Aralık Araması (Spatial & Range Searching) Algoritması

1class KDNode {
2  point: [number, number];
3  left: KDNode | null = null;
4  right: KDNode | null = null;
5  constructor(pt: [number, number]) { this.point = pt; }
6}
7
8function insertKD(node: KDNode | null, pt: [number, number], depth: number): KDNode {
9  if (node === null) return new KDNode(pt);
10  const cd = depth % 2; // Coordinate dimension (0 for X, 1 for Y)
11  if (pt[cd] < node.point[cd]) {
12    node.left = insertKD(node.left, pt, depth + 1);
13  } else {
14    node.right = insertKD(node.right, pt, depth + 1);
15  }
16  return node;
17}
18
19function searchRangeKD(
20  node: KDNode | null,
21  xmin: number, ymin: number, xmax: number, ymax: number,
22  depth: number,
23  results: [number, number][]
24) {
25  if (node === null) return;
26
27  const [x, y] = node.point;
28  if (x >= xmin && x <= xmax && y >= ymin && y <= ymax) {
29    results.push(node.point);
30  }
31
32  const cd = depth % 2;
33  const val = cd === 0 ? x : y;
34  const minVal = cd === 0 ? xmin : ymin;
35  const maxVal = cd === 0 ? xmax : ymax;
36
37  if (minVal <= val) {
38    searchRangeKD(node.left, xmin, ymin, xmax, ymax, depth + 1, results);
39  }
40  if (maxVal >= val) {
41    searchRangeKD(node.right, xmin, ymin, xmax, ymax, depth + 1, results);
42  }
43}