/**
 * ==========================================
 * 轨迹抽稀工具
 * RDP（几何抽稀） + DBSCAN（停留点识别）
 * 坐标统一使用：
 *   x -> 经度 (lon)
 *   y -> 纬度 (lat)
 * 返回字段仅包含：x、y、ag、tm、sp
 * ==========================================
 */

interface Point {
  x: number
  y: number
  ag: any
  tm: any
  sp: any
}

/* ================= DBSCAN ================= */

/**
 * DBSCAN 聚类算法（基于经纬度球面距离）
 */
class DBSCAN {
  private epsilon: number
  private minPts: number
  private data: Point[]
  private labels: number[]
  private cellSize: number
  private grid: Map<string, number[]>

  constructor(epsilon: number, minPts: number, data: Point[]) {
    this.epsilon = epsilon // km
    this.minPts = minPts
    this.data = data
    this.labels = Array.from({ length: data.length }, () => 0)

    // 空间网格索引（加速邻域查询）
    this.cellSize = this.epsilon / 110.574
    this.grid = new Map()

    for (let i = 0; i < data.length; i++) {
      const { x, y } = data[i]
      const xIndex = Math.floor(x / this.cellSize)
      const yIndex = Math.floor(y / this.cellSize)
      const key = `${xIndex},${yIndex}`

      if (!this.grid.has(key))
        this.grid.set(key, [])
      this.grid.get(key)!.push(i)
    }
  }

  // 球面距离（Haversine）
  distance(a, b) {
    const lat1 = a.y
    const lon1 = a.x
    const lat2 = b.y
    const lon2 = b.x

    const dLat = (lat2 - lat1) * Math.PI / 180
    const dLon = (lon2 - lon1) * Math.PI / 180

    const s
      = Math.sin(dLat / 2) ** 2
        + Math.cos(lat1 * Math.PI / 180)
        * Math.cos(lat2 * Math.PI / 180)
        * Math.sin(dLon / 2) ** 2

    return 6371 * 2 * Math.atan2(Math.sqrt(s), Math.sqrt(1 - s))
  }

  regionQuery(index) {
    const neighbors = []
    const { x, y } = this.data[index]
    const xIndex = Math.floor(x / this.cellSize)
    const yIndex = Math.floor(y / this.cellSize)

    for (let i = -1; i <= 1; i++) {
      for (let j = -1; j <= 1; j++) {
        const key = `${xIndex + i},${yIndex + j}`
        const cell = this.grid.get(key)
        if (!cell)
          continue

        for (const idx of cell) {
          if (this.distance(this.data[index], this.data[idx]) < this.epsilon) {
            neighbors.push(idx)
          }
        }
      }
    }
    return neighbors
  }

  dbscan() {
    let clusterId = 0

    for (let i = 0; i < this.data.length; i++) {
      if (this.labels[i] !== 0)
        continue

      const neighbors = this.regionQuery(i)
      if (neighbors.length < this.minPts) {
        this.labels[i] = -1
        continue
      }

      clusterId++
      this.expandCluster(i, neighbors, clusterId)
    }

    return this.labels
  }

  expandCluster(index, neighbors, clusterId) {
    this.labels[index] = clusterId
    let i = 0

    while (i < neighbors.length) {
      const n = neighbors[i]

      if (this.labels[n] === -1) {
        this.labels[n] = clusterId
      }
      else if (this.labels[n] === 0) {
        this.labels[n] = clusterId
        const nn = this.regionQuery(n)
        if (nn.length >= this.minPts) {
          neighbors.push(...nn)
        }
      }
      i++
    }
  }
}

/* ================= RDP ================= */

function getDecimalDigits(num) {
  const str = num.toString()
  const match = str.match(/\.(\d+)/)
  return match ? match[1].length : 0
}

function perpendicularDistance(p, s, e) {
  const x0 = p.x
  const y0 = p.y
  const x1 = s.x
  const y1 = s.y
  const x2 = e.x
  const y2 = e.y

  const num = Math.abs((y2 - y1) * x0 - (x2 - x1) * y0 + x2 * y1 - y2 * x1)
  const den = Math.sqrt((y2 - y1) ** 2 + (x2 - x1) ** 2)

  return den === 0
    ? Math.hypot(x0 - x1, y0 - y1)
    : num / den
}

function rdp(points, epsilon) {
  if (points.length < 3)
    return points

  let maxDist = 0
  let index = 0
  const start = points[0]
  const end = points[points.length - 1]

  for (let i = 1; i < points.length - 1; i++) {
    const d = perpendicularDistance(points[i], start, end)
    if (d > maxDist) {
      maxDist = d
      index = i
    }
  }

  if (maxDist > epsilon) {
    const left = rdp(points.slice(0, index + 1), epsilon)
    const right = rdp(points.slice(index), epsilon)
    return left.slice(0, -1).concat(right)
  }
  else {
    return [start, end]
  }
}

/* ================= 主函数 ================= */

/**
 * 轨迹抽稀主入口
 * @param {Array} data 原始轨迹
 * @param {number} rdpEpsilon RDP 精度（度）
 * @param {number} dbscanEpsilon DBSCAN 半径（km）
 * @param {number} minPts DBSCAN 最小点数
 */
export function trajectoryThinning(
  data: any[],
  rdpEpsilon = 0.000001,
  dbscanEpsilon = 0.01,
  minPts = 20,
): Point[] {
  if (!Array.isArray(data) || data.length === 0)
    return []

  // 1️⃣ 数据清洗
  const cleaned: Point[] = data
    .filter(p =>
      p.x && p.y
      && p.ag !== undefined
      && p.tm !== undefined
      && p.sp !== undefined
      && getDecimalDigits(p.x) > 3
      && getDecimalDigits(p.y) > 3,
    )
    .map(p => ({
      x: +p.x,
      y: +p.y,
      ag: p.ag,
      tm: p.tm,
      sp: p.sp,
    }))
    .sort((a, b) => a.tm - b.tm)

  if (!cleaned.length)
    return []

  // 2️⃣ 按 tm 去重
  const dedup: Point[] = []
  for (let i = 0; i < cleaned.length; i++) {
    if (!cleaned[i + 1] || cleaned[i].tm !== cleaned[i + 1].tm) {
      dedup.push(cleaned[i])
    }
  }

  // 3️⃣ RDP 抽稀
  const rdpPoints: Point[] = rdp(dedup, rdpEpsilon)
  if (!rdpPoints.length)
    return []

  // 4️⃣ DBSCAN 聚类
  const labels = runDbscan(dbscanEpsilon, minPts, rdpPoints)

  // 5️⃣ 结果整理
  return modifyArray(labels, rdpPoints)
    .filter(Boolean)
    .map(p => ({
      x: +p.x.toFixed(6),
      y: +p.y.toFixed(6),
      ag: p.ag,
      tm: p.tm,
      sp: p.sp,
    }))
}

/* ================= 工具函数 ================= */

function runDbscan(epsilon: number, minPts: number, data: Point[]): number[] {
  if (data.length < minPts) {
    return Array.from({ length: data.length }, () => -1)
  }
  return new DBSCAN(epsilon, minPts, data).dbscan()
}

function modifyArray(labels: number[], points: Point[]): Point[] {
  const groups: Record<number, { index: number, tm: number }[]> = {}
  const result: (Point | 0)[] = Array.from({ length: points.length }, () => 0)

  for (let i = 0; i < labels.length; i++) {
    const id = labels[i]
    if (id === -1)
      continue
    if (!groups[id])
      groups[id] = []
    groups[id].push({ index: i, tm: points[i].tm })
  }

  for (const group of Object.values(groups)) {
    group.sort((a, b) => a.tm - b.tm)
    result[group[0].index] = points[group[0].index]
    result[group[group.length - 1].index] = points[group[group.length - 1].index]
  }

  // 噪声点全部保留
  for (let i = 0; i < labels.length; i++) {
    if (labels[i] === -1) {
      result[i] = points[i]
    }
  }

  return result.filter(Boolean) as Point[]
}