DBSCAN

1function dbscan(
2  pts: Array<[x: number, y: number]>,
3  eps: number,
4  minPts: number,
5) {
6  const labels = new Map<number, number>() // индекс → кластер | -1 = шум
7  let cluster = 0
8 
9  for (let i = 0; i < pts.length; i++) {
10    if (labels.has(i)) continue
11    const neighbors = pts
12      .map((p, j) => ({ j, d: dist(pts[i]!, p) }))
13      .filter((n) => n.d <= eps)
14 
15    if (neighbors.length < minPts) {
16      labels.set(i, -1) // пока шум
17      continue
18    }
19 
20    labels.set(i, cluster) // core-точка: новый кластер
21    const queue = neighbors.map((n) => n.j).filter((j) => j !== i)
22    while (queue.length > 0) {
23      const j = queue.shift()!
24      if (labels.get(j) === -1) labels.set(j, cluster) // шум → border
25      if (labels.has(j)) continue
26      labels.set(j, cluster)
27      const n2 = pts.map((p, k) => ({ k, d: dist(pts[j]!, p) })).filter((n) => n.d <= eps)
28      if (n2.length >= minPts) queue.push(...n2.map((n) => n.k).filter((k) => !labels.has(k)))
29    }
30    cluster++
31  }
32  return labels
33}