Scala实现DP(道格拉斯-普克)算法

Scala实现DP(道格拉斯-普克)算法

DP算法介绍

算法实现

scala实现

// 创建一个Point类
case class Point(x: Double, y: Double)


// 方法实现
 def dp(pts: Seq[Point], tolerance: Double): Seq[Point] = {

    if (pts.size < 3) return pts

    val listBuffer = new ListBuffer[Point]()
    listBuffer.append(pts.head)

    def dpRunner(pts: Seq[Point], tolerance: Double): Unit = {

      val head = pts.head
      val last = pts.last

      // 首尾点连成的线段
      val lineSegment: LineSegment = LineSegment(head, last)

      //求曲线上所有点到直线的垂直距离，并找出最大距离dmax
      //最大距离的点
      val maxDistancePoint = pts.maxBy(lineSegment.distancep)

      // 最大距离
      val maxDistance: Double = lineSegment.distancep(maxDistancePoint)

      //最大距离点的索引
      val maxPointIndex = pts.indexOf(maxDistancePoint)

      // 如果最大距离小于给定的阈值，则将曲线中间的所有点舍去
      if (maxDistance < tolerance) {
        listBuffer.append(last)
      } else {
        // 如果最大距离大于给定的阈值，则以该点为界将曲线划分为两部分，重复以上步骤
        dpRunner(pts.slice(0, maxPointIndex + 1), tolerance)
        dpRunner(pts.slice(maxPointIndex, pts.size), tolerance)
      }
    }

    dpRunner(pts, tolerance)
    listBuffer
  }

// 数据测试
def main(args: Array[String]): Unit = {

    val pts: Seq[Point] = Seq(
      Point(107.605, 137.329),
      Point(122.274, 169.126),
      Point(132.559, 179.311),
      Point(153.324, 184.276),
      Point(171.884, 174.654),
      Point(186.408, 168.634),
      Point(196.566, 145.204),
      Point(200.549, 127.877),
      Point(211.391, 118.179),
      Point(216.318, 116.547),
      Point(225.197, 122.796),
      Point(231.064, 135.459),
      Point(240.835, 143.398),
      Point(254.630, 144.933),
      Point(265.055, 158.761),
      Point(271.004, 159.660),
      Point(274.474, 173.979)
    )

    dp(pts, 8).foreach(println)

  }

结果：

Point(107.605,137.329)
Point(122.274,169.126)
Point(153.324,184.276)
Point(186.408,168.634)
Point(200.549,127.877)
Point(216.318,116.547)
Point(274.474,173.979)

参考资料

https://segmentfault.com/a/1190000016734779