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

2020-10-26

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

線を引く場合に 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]]
}
}