1.算法概述

道格拉斯算法是一種曲線的點簡化算法。

一般來說，在計算機中表示一條曲線往往使用若干個點來表示，將點連接后形成的折線來趨近想要表示的曲線。點的數(shù)量越多，就越貼合想要表示的曲線。

點的數(shù)量過多，就需要更多的空間去保存，同時，涉及傳輸或者計算，如將點的現(xiàn)象傳輸給前端或者用點生成復(fù)雜圖像，往往需要更多的時間。

在不影響最終繪制效果的前提下，可以將曲線中的點進行適當(dāng)刪除。這個步驟就是點的簡化。而在對精確度要求不高的情況下，可以簡化更多。

2.算法步驟

算法的基本思路是:

• 假設(shè)要簡化一條曲線，曲線的兩個端點分別是A和B，容忍度為D，D為一個數(shù)值（距離），用于判斷一個點是否要保留；
• 端點AB連接后得到的直線為AB；
• 遍歷曲線上的所有點,計算所有點到AB的距離， 尋找曲線上離AB最遠的點C。
• 假設(shè)C到AB的距離為dMax，將dMax與D相比;
• 如果dMax <D,則只保留AB兩點，這個時候，認為曲線是一條直線;
• 如果dMax ≥D,保留對應(yīng)的點C,并對AC和CB之間的曲線重復(fù)上述流程。

3.代碼實現(xiàn)

package Util

import (
    "math"
)

/*
* @author dust347
* @brief
*/
//point
type Point struct{
    X float64
    Y float64
}


//計算兩點之間距離
func GetDistPt(x1, y1 float64, x2, y2 float64) float64 {
    return math.Sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))
}

//計算點到另外兩點所確定的直線的距離
func GetDistPt2Line(linePtX1, linePtY1 float64, linePtX2, linePtY2 float64, x, y float64) float64 {
    //如果線的兩個點一樣，相當(dāng)于計算兩點之間距離
    if (linePtX1 == linePtX2) && (linePtY1 == linePtY2) {
        return GetDistPt(linePtX1, linePtY1, x, y)
    }

    d := (linePtY2*x-linePtY1*x + linePtX1*y-linePtX2*y + linePtX2*linePtY1-linePtX1*linePtY2) / math.Sqrt((linePtY2-linePtY1)*(linePtY2-linePtY1)+(linePtX2-linePtX1)*(linePtX2-linePtX1))
    return math.Abs(d)
}

//道格拉斯抽稀算法
func Douglas(vecPt []Point, tolerance float64) (vecPtRes []Point) {
    l := len(vecPt)
    if l <= 2 {         //小于兩個點直接返回
        return vecPt
    }


    //用于標記哪些點需要保留
    m := make(map[int]bool)

    //兩端點必保留
    m[0] = true
    m[l-1] = true
    douglas(&vecPt, 0, l-1, tolerance, &m)

    //返回數(shù)據(jù)
    for i, pt := range vecPt {
        if m[i] {
            vecPtRes = append(vecPtRes, pt)
        }
    }
    return
}

func douglas(vecPt *[]Point, l, r int, tolerance float64, m *map[int]bool) {
    if r - l <= 1 {
        return
    }

    //取兩個端點的數(shù)據(jù)
    x1, y1 := pt2float((*vecPt)[l])
    x2, y2 := pt2float((*vecPt)[r])

    var maxDist float64 = -1        //記錄最大距離
    var keepIndex int = -1          //記錄要保留的點的index

    for i := l+1; i < r; i++ {
        x, y := pt2float((*vecPt)[i])
        d := GetDistPt2Line(x1, y1, x2, y2, x, y)

        if d > maxDist {
            maxDist = d
            keepIndex = i
        }
    }

    if maxDist > tolerance {
        (*m)[keepIndex] = true
        douglas(vecPt, l, keepIndex, tolerance, m)
        douglas(vecPt, keepIndex, r, tolerance, m)
    }
}

func pt2float(pt Point) (float64, float64) {
    return pt.X, pt.Y
}