Yakınlık Problemleri (Proximity Problems) Algoritması

1function distance(p1: [number, number], p2: [number, number]): number {
2  return Math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2);
3}
4
5function closestPairRecursive(ptsX: [number, number][], ptsY: [number, number][]): number {
6  const n = ptsX.length;
7  if (n <= 3) {
8    let minD = Infinity;
9    for (let i = 0; i < n; i++) {
10      for (let j = i + 1; j < n; j++) {
11        minD = Math.min(minD, distance(ptsX[i], ptsX[j]));
12      }
13    }
14    return minD;
15  }
16
17  const mid = Math.floor(n / 2);
18  const midPoint = ptsX[mid];
19
20  // Noktaları sol ve sağ olarak ayır
21  const leftX = ptsX.slice(0, mid);
22  const rightX = ptsX.slice(mid);
23
24  const leftY = ptsY.filter((p) => p[0] <= midPoint[0]);
25  const rightY = ptsY.filter((p) => p[0] > midPoint[0]);
26
27  const dl = closestPairRecursive(leftX, leftY);
28  const dr = closestPairRecursive(rightX, rightY);
29  let d = Math.min(dl, dr);
30
31  // Şerit tespiti
32  const strip = ptsY.filter((p) => Math.abs(p[0] - midPoint[0]) < d);
33
34  for (let i = 0; i < strip.length; i++) {
35    for (let j = i + 1; j < strip.length && (strip[j][1] - strip[i][1]) < d; j++) {
36      d = Math.min(d, distance(strip[i], strip[j]));
37    }
38  }
39
40  return d;
41}