折れ線を簡略化する方法(Ramer-Douglas-Peucker法)

2020-10-26
#algorithm

マウスやタッチで描いた軌跡を扱う際にすべての頂点を用いるのは煩雑なので点群を簡略化したい、といった時にどうしたらいいか調べてみた。

線を引く場合に mousemove イベントコールバックで得られた点をつないでいくが、のちのち扱う場合にはまっすぐな部分の途中の点は無駄なので省いてしまいたい。 まっすぐかどうかをどうやって判定したらいいか、曲率を考慮して求められないかなどと考えていたんだけど、 Ramer–Douglas–Peucker法 というアルゴリズムがあるとのことで試してみた。

アルゴリズムは非常に簡潔で、

  • 始点と終点を結ぶ直線に対して垂線をおろしたとき、中点の中で距離が一番遠いものを選ぶ
  • 距離が基準値以下だったら直線とみなして、間の点は省く
  • 基準値以上だったら中点で分割して、再帰的に繰り返す
// Ramer-Douglas-Peucker algorithm.
// https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
function douglasPeucker(pointList, start, end, epsilon) {
  // Find the point with the maximum distance.
  const n = end - start
  let dmax = 0
  let index = (n >> 1) + start
  for (let i = start; ++i < end - 1; ) {
    let d = perpendicularDistance(pointList[i], pointList[start], pointList[end - 1])
    if (d > dmax) {
      index = i
      dmax = d
    }
  }

  // If max distance is greater than epsilon, recursively simplify
  if (dmax > epsilon) {
    // Recursive call.
    const recResults1 = douglasPeucker(pointList, start, index + 1, epsilon)
    const recResults2 = douglasPeucker(pointList, index, end, epsilon)

    // Build the result list.
    for (let i = 1; i < recResults2.length; ++i)
      recResults1.push(recResults2[i])
    return recResults1
  } else {
    return [pointList[start], pointList[end - 1]]
  }
}

精度も制御できて、結果もいい感じ。

このアルゴリズムを使えば、例えば一定時間ごとにGPSで緯度経度を記録したものをマップ上に表示する際にズームに合わせて間引くなど、いろいろ応用できると思う。

関連

関連記事

新着記事