道格拉斯-普克算法(Douglas–Peucker algorithm，亦稱為拉默-道格拉斯-普克算法、疊代適應點算法、分裂與合併算法)是將曲線近似表示為一系列點，並減少點的數量的一種算法。它的優點是具有平移和旋轉不變性，給定曲線與閾值後，抽樣結果一定。
基本介紹
- 中文名：道格拉斯-普克算法
- 外文名：Douglas–Peucker algorithm
- 亦稱為：拉默-道格拉斯-普克算法
- 提出：1973年
簡要說明,詳細步驟,實現代碼,
簡要說明
道格拉斯-普克算法(Douglas–Peucker algorithm，亦稱為拉默-道格拉斯-普克算法、疊代適應點算法、分裂與合併算法)是將曲線近似表示為一系列點，並減少點的數量的一種算法。該算法的原始類型分別由烏爾斯·拉默（Urs Ramer）於1972年以及大衛·道格拉斯（David Douglas）和托馬斯·普克（Thomas Peucker）於1973年提出，並在之後的數十年中由其他學者予以完善。
算法的基本思路是:對每一條曲線的首末點虛連一條直線,求所有點與直線的距離,並找出最大距離值dmax ,用dmax與限差D相比:若dmax <D,這條曲線上的中間點全部捨去;若dmax ≥D,保留dmax 對應的坐標點,並以該點為界,把曲線分為兩部分,對這兩部分重複使用該方法。
詳細步驟
(1) 在曲線首尾兩點間虛連一條直線,求出其餘各點到該直線的距離，如右圖（1）。
（2）選其最大者與閾值相比較,若大於閾值,則離該直線距離最大的點保留,否則將直線兩端點間各點全部捨去，如右圖（2），第4點保留。
（3）依據所保留的點,將已知曲線分成兩部分處理,重複第1、2步操作，疊代操作，即仍選距離最大者與閾值比較,依次取捨,直到無點可捨去，最後得到滿足給定精度限差的曲線點坐標，如圖（3）、（4）依次保留第6點、第7點，捨去其他點,即完成線的化簡。
實現代碼
packagecom.mapbar.jts;/***ClassPoint.java*/publicclassPoint{ /***點的X坐標*/ privatedoublex = 0; /***點的Y坐標*/ privatedoubley = 0; /***點所屬的曲線的索引*/ privateintindex = 0; publicdoublegetX() { returnx; } publicvoidsetX(doublex) { this.x = x; } publicdoublegetY() { returny; } publicvoidsetY(doubley) { this.y = y; } publicintgetIndex() { returnindex; } publicvoidsetIndex(intindex) { this.index = index; } /***點數據的構造方法* *@param x *點的X坐標 *@param y *點的Y坐標 *@param index點所屬的曲線的索引 */ publicPoint(doublex, doubley, intindex){ this.x = x; this.y = y; this.index = index; }}packagecom.mapbar.jts;importjava.util.ArrayList;importjava.util.List;importcom.vividsolutions.jts.geom.Coordinate;importcom.vividsolutions.jts.geom.Geometry;importcom.vividsolutions.jts.io.ParseException;importcom.vividsolutions.jts.io.WKTReader;/***ClassDouglas.java*/publicclassDouglas{ /***存儲採樣點數據的鍊表*/ publicList < Point > points = newArrayList < Point > (); /***控制數據壓縮精度的極差*/ privatestaticfinaldoubleD = 1; privateWKTReaderreader; /***構造Geometry**@paramstr*@return*/ publicGeometrybuildGeo(Stringstr) { try { if (reader == null) { reader = newWKTReader(); } returnreader.read(str); } catch(ParseExceptione) { thrownewRuntimeException("buildGeometryError", e); } } /***讀取採樣點*/ publicvoidreadPoint() { Geometryg = buildGeo("LINESTRING(14,23,42,66,77,86,95,1010)"); Coordinate[] coords = g.getCoordinates(); for (inti = 0; i < coords.length; i++) { Pointp = newPoint(coords[i].x, coords[i].y, i); points.add(p); } } /***對矢量曲線進行壓縮**@paramfrom*曲線的起始點*@paramto*曲線的終止點*/ publicvoidcompress(Pointfrom, Pointto) { /***壓縮算法的開關量*/ booleanswitchvalue = false; /***由起始點和終止點構成的直線方程一般式的係數*/ System.out.println(from.getY()); System.out.println(to.getY()); doubleA = (from.getY() - to.getY()) / Math.sqrt(Math.pow((from.getY() - to.getY()), 2) + Math.pow((from.getX() - to.getX()), 2)); /***由起始點和終止點構成的直線方程一般式的係數*/ doubleB = (to.getX() - from.getX()) / Math.sqrt(Math.pow((from.getY() - to.getY()), 2) + Math.pow((from.getX() - to.getX()), 2)); /***由起始點和終止點構成的直線方程一般式的係數*/ doubleC = (from.getX() * to.getY() - to.getX() * from.getY()) / Math.sqrt(Math.pow((from.getY() - to.getY()), 2) + Math.pow((from.getX() - to.getX()), 2)); doubled = 0; doubledmax = 0; intm = points.indexOf(from); intn = points.indexOf(to); if (n == m + 1) return; Pointmiddle = null; List < Double > distance = newArrayList < Double > (); for (inti = m + 1; i < n; ++) { d = Math.abs(A * (points.get(i).getX()) + B * (points.get(i).getY()) + C) / Math.sqrt(Math.pow(A, 2) + Math.pow(B, 2)); distance.add(d); } dmax = distance.get(0); for (intj = 1; j < distance.size(); j++) { if (distance.get(j) > dmax) dmax = distance.get(j); } if (dmax > D) switchvalue = true; else switchvalue = false; if (!switchvalue) { //刪除Points(m,n)內的坐標 for (inti = m + 1; i < n; i++) points.get(i).setIndex( - 1); } else { for (inti = m + 1; i < n; i++) { if ((Math.abs(A * (points.get(i).getX()) + B * (points.get(i).getY()) + C) / Math.sqrt(Math.pow(A, 2) + Math.pow(B, 2)) == dmax)) middle = points.get(i); } compress(from, middle); compress(middle, to); } } publicstaticvoidmain(String[] args) { Douglasd = newDouglas(); d.readPoint(); d.compress(d.points.get(0), d.points.get(d.points.size() - 1)); for (inti = 0; i < d.points.size(); i++) { Pointp = d.points.get(i); if (p.getIndex() > -1) { System.out.print(p.getX() + "" + p.getY() + ","); } } }}