パート1の問題の説明
1.1特定のタスク
このジョブタスクは軌道圧縮です。 GPSデータレコードファイルが与えられた場合、各レコードには、経度と寸法の2つの座標フィールドが含まれています。すべてのレコードには、緯度と経度の座標があり、軌道を形成します。圧縮軌道の距離誤差が30m未満になるように、適切な圧縮アルゴリズムを使用する必要があります。
1.2プログラム入力
このプログラムの入力は、GPSデータレコードファイルです。
1.3データ出力
出力フォームは、3つの部分、圧縮ポイントのIDシーケンスと座標、ポイント数、平均距離誤差、および圧縮率を含むファイルです。
2番目の部分への回答
問題の説明によれば、問題を解決し、問題解決は次の手順に分けられます。
2.1データ前処理
このプログラム入力はGPSデータレコードファイルであり、合計3150行のレコードがあり、各レコード行はいくつかのフィールドに分割されます。質問によると、経度と緯度の座標フィールドに注意を払うだけです。元のデータファイルのいくつかのレコードを図2.1に示します。
図2.1元のデータファイルの部分的な記録の概略図
図2.1に示すように、元のデータファイルの各レコードの緯度および経度調整フィールドデータのストレージ形式は、典型的なGPS座標式表現法です。つまり、学位区分形式、フォームはdddmm.mmmmmm、dddは程度を表します。このデータの前処理では、次の2つの座標ポイント間の距離の計算を促進するために、学位区分形式の緯度と経度座標データを程度の形式に変換する必要があります。変換方法はDDD+mm.mmmm/60です。ここでは、小数点の後に6桁を保持し、変換されたフォームはddd.xxxxxxです。
例として、最初の記録（11628.2491、3955.6535）の緯度と経度の座標を取得します。変換結果は（116.470818、39.927558）です。すべてのレコードの緯度と経度の座標はメソッドを使用して実行され、変換された座標ポイントごとにIDを生成し、一意に識別できます。圧縮後、予約されたすべてのポイントのIDを出力する必要があります。
2.2 Douglas-Peucker軌道圧縮アルゴリズム
軌道圧縮アルゴリズムは、2つのカテゴリに分けられます。つまり、ロスレス圧縮と損失のある圧縮です。ロスレス圧縮アルゴリズムには主にHuffmanコーディングが含まれ、Losy Compressionアルゴリズムはバッチ処理方法とオンラインデータ圧縮法に分けられます。バッチ処理方法には、DP（Douglas-Peucker）アルゴリズム、TD-TR（トップダウン時間比）アルゴリズム、およびBellmanアルゴリズムが含まれます。オンラインデータ圧縮方法には、スライディングウィンドウ、開いたウィンドウ、安全なエリアベースの方法などが含まれます。
時間が限られているため、この軌道圧縮のために、比較的単純なDPアルゴリズムを使用することにしました。
DPアルゴリズムの手順は次のとおりです。
（1）曲線の開始時と端で2つの点AとBの間に直線ABを接続し、直線が曲線のコードです。
（2）曲線上の他のすべてのポイントを横断し、各ポイントから直線ABまでの距離を見つけ、最大距離でポイントCを見つけ、DMAXとして最大距離を記録します。
（3）距離dmaxを事前定義されたしきい値dmaxサイズと比較します。 dmax <dmaxの場合、直線abは曲線セグメントの近似として使用され、曲線セグメントが処理されます。
（4）dmax> = dmaxの場合、ポイントcは曲線abを2つのセクションACとCBに分割し、（1）から（3）これら2つのセクションのステップをそれぞれ実行します。
（5）すべての曲線が処理されると、各セグメンテーションポイントによって形成されるポリラインが順番に接続されています。つまり、元の曲線の経路です。
2.3ポイントからラインまでの距離
DPアルゴリズムでは、ポイントから直線までの距離を見つける必要があります。この距離とは、垂直方向のユーロのような距離、つまり、直線ABの外側のポイントCから線ABまでの距離dを指します。ここでは、ポイントa、b、およびcはすべて緯度と経度の座標です。三角形の等面積方法を使用して距離dを見つけます。特定の方法は、ポイントA、B、およびCが三角形を形成します。この三角形の面積、つまり通常の方法（下x高さ/2）とヘレン式を見つけるには、2つの方法があります。ヘレンフォーミュラは次のとおりです。
それぞれ副長さA、B、およびCの三角形があるとします。三角形の面積は、次の式から取得できます。
ここで、pは半分周囲です：
ヘレンフォーミュラから三角形の面積を見つけることができ、高さが距離dである高さのサイズを見つけることができます。ヘレン式を使用するには、3ポイントA、B、およびCの間の距離を見つける必要があります。距離式は教師によって与えられ、距離関数を直接呼び出すことができます。
注：距離を見つけた後、絶対値を追加して、距離が負になるのを防ぎます。
2.4平均エラーを解決します
平均誤差は、圧縮中に無視されたポイントから距離の合計を対応するラインセグメントに無視して、ポイントの総数で除算することによって得られる値を指します。
2.5圧縮率の解決策
圧縮比計算式は次のとおりです。
2.6データ結果ファイルの生成
上記の処理と計算の後、圧縮後の残りのポイントのIDを書き込み、ポイント数、平均距離エラー、圧縮率、およびその他のパラメーターを最終結果ファイルに書き込み、質問に対する答えが完了します。
パート3コードの実装
このプログラムはJava言語で書かれており、Intellij Idea 14.0.2の開発環境があります。コードは2つのクラスに分かれています。 1つは、緯度と経度のポイント情報を保存するために使用されるENポイントクラスであり、もう1つはTraujectoryCompressionMainクラスで、データ処理、DPアルゴリズム、ポイントツーライン距離、平均エラーなどの関数を記述するために使用されます。
3.1一般的な手順プロセス
プログラム全体のフローには、主に次の手順が含まれています。
（1）関連するアレイリスト配列とファイルオブジェクトを定義します。その中には、3つの配列アレイオブジェクトがあります。つまり、元の緯度と経度座標配列pgpsarryinit、フィルタリングされたポイント座標配列PGPSArrayFilter、およびフィルター処理された並べ替えられたポイント調整配列PGPSArrayFilterSort; 5つのファイルオブジェクトがあります。つまり、元のデータファイルオブジェクトFGPS、圧縮結果データファイルオブジェクトOGPS、変換された元の緯度および経度座標ポイントを維持するデータファイルFinitGPSポイント、シミュレーションテストファイルftestinitpointとftestfilterpointです。
（2）元のポイントの座標を取得し、ファイルに書き込みます。主に2つの操作を含みます。ファイルを読み取り、ファイルを書き込みます。
（3）軌道圧縮を実行します。
（4）圧縮された緯度と経度の座標を並べ替えます。
（5）シミュレーションテストファイルを生成し、R言語ツールを使用してグラフィックを描画して最終結果を取得します。
（6）平均誤差と圧縮率を見つけ、平均誤差は関数によって得られ、圧縮率は直接計算されます。
（7）フィルタリングされたポイントID、ポイント数、平均エラー、圧縮率など、最終結果を結果ファイルに記述します。
3.2特定の実装コード
（1）enpoint.java
パッケージcc.xidian.main; Import java.text.decimalformat;/*** 2015/12/20。*/public class enpoints実装<enpoint> {public int id; // point idpublic double pe; //縦心パブリックダブルPn; = new Decimalformat（ "0.000000"）; return this.id+"＃"+this.pn+"、"+this.pe;} public string getTestString（）{decimalformat df = new Decimalformat（ "0.0000000"）; return df.format（this.pn）+"+df.format（this.format（this.pe）; getResultString（）{decimalformat df = new decimalformat（ "0.000000"）; return this.id+"＃"+df.format（this.pn）+"+df.format（this.pe）;}@overridepublic int compareto（enpoint other）{if（this.id <other.id <other.id） else if（this.id> other.id）return1; elsereturn0;}}（2）traultoryCompressionMain.java
パッケージcc.xidian.main; Import java.io。*;インポートjava.text.decimalformat; import java.util。*; import java.util.list;/*** 2015/12/19によって作成された。 Exception{//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pGPSArrayInit = new ArrayList <enpoint>（）; //元のレコード緯度と経度座標配列アレイリスト<enpoint> pgpsArrayFilter = new ArrayList <enpoint>（）; file（ "2007-10-14-gps.log"）; //元のデータファイルオブジェクトファイルogps = newファイル（ "2015-12-25-gps-result.log"）;小数点入り後の数字FINITGPSPOINT = new File（ "2007-10-14-gps-enpoint.log"）; //変換されたファイルの後に元の緯度と経度座標ポイントの変換されたデータファイルを保持しますftestinitpoint = newファイル（ " file（ "2015-12-25-gps-filtertestpoint.log"）; //フィルタリングされた緯度および経度座標ポイントデータファイルに使用 simulation//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pgpsarrayinit）; //変換された元の緯度と経度のポイントデータをファイルシステムに書き込みます。out.println（pgpsarrayinit.size（））; coordinates//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 30.0; //最大距離エラーしきい値pgpsarrayfilter.add（pgpsarrayinit.get（0））; //最初の元の緯度と経度の座標を取得し、ろ過された配列pgpsarrayfilter.add（pgpsarrayinit.get（pgpsarrayinit.get）;経度ポイントとフィルタリングされた配列に追加しますenpoint [] enpinit = new enpoint [pgpsarrayinit.size（）]; iinit.next（）; jj ++;} //配列のポイントの座標をポイント配列int start = 0; // start subscript int = pgpsarrayinit.size（）-1; // end subcrict trajcoccressc（enpinit、pgpsarrayfilter、dmax）; System.out.println（pgpsArrayfilter.size（））; //出力圧縮 points//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ENPoint[pGPSArrayFilter.size()];//Use an array of points to receive filtered point coordinates, for the following sorting Iterator<ENPoint> iF = pGPSArrayFilter.iterator();int i = 0;while(iF.hasNext()){enpFilter[i] = iF.next();i++;}//Copy the point coordinates in ArrayList to theポイントアレイアレイ.sort（enpfilter）; // sort for（int j = 0; j <enpfilter.length; j ++）{pgpsarrayfiltersort.add（enpfilter [j]）; //ソートされたポイント座標を新しいアレイリストに書き込みます 配列}// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - pgpsArrayFilterSort）; //フィルタリングされた緯度と経度のデータポイントをシミュレーションファイルに書き込み、形式は「経度、寸法」です //-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- getMeanDisterRor（PGPSArrayInit、PGPSArrayFiltersort）; //平均エラーを見つけますSystem.out.println（mderror）; ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ （double）pgpsarrayfilter.size（）/pgpsarrayinit.size（）*100; //圧縮率を見つけます System.out.println(cRate);//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------および圧縮率writefilterpointtofile（ogps、pgpsarrayfilterstort、mderror、crate）; ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- @param fgps：ソースデータファイル* @return pgpsarrayinit：すべてのポイント座標を保存するreturn arraylistアレイ* @throws例外*/public static arraylist <enpoint> getenpointfromfile（ファイルfgps）スロー例arrayList <enpoint>（）; if（fgps.exists（）&& fgps.isfile（））{inputstreamreader read = new fileinputStream（fgps））; bufferedReader breader = new bufferedReader（read）; string str; string strgps; int i = 0; str.split（ "）; enpoint p = new enpoint（）; p.id = i; i ++; p.pe =（dftodu（strgps [3]））; p.pn =（dftodu（strgps [5]））; pgpsarray.add（p）;} breader.close（）;フィルタリングされたポイントの結果ファイル* @param outgpsfile：result file* @param pgpspointfilter：フィルタリングポイント* @param mderror：平均距離エラー* @paramクレート* @throws例外*/パブリックサティックボイドwritefilterpointtofile（ファイルoutgpsfile、deblist <クレート）{iterator <Enpoint> ifilter = pgpspointfilter.iterator（）; randomaccessfile rfilter = new randomaccessfile（outgpsfile、 "rw"） bfilter = sfilter.getBytes（）; rfilter.write（bfilter）;} string strmc = "＃"+integer.toString（pgpspointfilter.size（））+"、"+double.toString（mderror）+"、"+double.toString（n "+"+"+"+"+"+"+"+ strmc.getBytes（）; rfilter.write（bmc）; rfilter.close（）;}/***関数：変換された元の緯度と経度のデータポイントをファイルに保存* @param outgpsfile* @param pgpspointfilter* @param pgpspointfilter）スロー例外{iterator <tonpoint> ifilter = pgpspointfilter.iterator（）; randomaccessfile rfilter = new randomaccessfile（outgpsfile、 "rw"）; while（ifilter.hasnext（））{enpoint p = ifilter.next p.toString（）+"/n"; byte [] bfilter = sfilter.getBytes（）; rfilter.write（bfilter）;} rfilter.close（）;}/***関数：視覚的テストのためのテストファイルへの配列に緯度と経度の調整データを書き込みます。 @throws Exception*/public static void writeTestpointTofile（file outgpsfile、arraylist <enpoint> pgpspointfilter）スロー例外{iterator <enpoint> ifilter = pgpspointfilter.iterator（）; randomaccessfile rfilter = new randomaccessfile（outgpsfile "）; while（ifilter.hasnext（））{enpote p = ifilter.next（）; string sfilter = p.getestString（）+"/n"; byte [] bfilter = sfilter.getBytes（）; rfilter.write（bfilter）;} rfilter.cord int cordclose（）;学位* @param str：元の緯度および経度座標* @return：対応する*/public static dftodu（string str）{int indexd = str.indexof（ '。'）; string strm = str.substring（0、indexd-2）; string strn = str.-substring（indexd-2）; double d = d = d = substring（0、indexd-2）; Double.ParseDouble（STRM）+Double.ParseDouble（STRN）/60; return D double.ParseDouble（df.format（d））;}/***関数：ポイントPXと、トライアングルの領域を使用してポイントPAとPBによって決定される直線を計算します（ヘレンフォーミュラを使用して見つける）配置*/public static double Distosement（enpoint PA、enpoint Pb、enpoint Px）{double a = math.abs（geodist（pa、pb））; double b = math.abs（pa、px））; double c = math.abs（geodist（pb、px））; double p =（a+b+c）/2.0; doube Math.sqrt（math.abs（p*（pa）*（pb）*（pc）））; double d = s*2.0/a; return D pb）{double radlat1 = rad（pa.pn）; double radlat2 = rad（pb.pn）; defalta_lon = rad（pb.pe -pa.pe）; double top_1 = math.cos（radlat2） * math.sin（delta_lon）; double top_2 = math.cos（radlat1） * math.sin（ Math.sin（radlat1） * math.cos（radlat2） * math.cos（delta_lon）; double top = math.sqrt（top_1 + top_2 * top_2）; double bott.sin（radlat1） * math.sin（radlat2） + math.cos（radlat1） * math.cos（radlat2） * Math.cos（delta_lon）; double delta_sigma = math.atan2（top、bottom）; double distance = delta_sigma* 6378137.0; return distance;}/*** function* @param d：angle* @return the Return the Return the Return the Return the Return static double rad（double dable d*最大距離制限に応じて、元の軌道はDPメソッドを使用して再帰的にサンプリングされ、圧縮軌道を取得します* @param enpinit：元の緯度および経度座標ポイント配列* @param enparrayfilter：フィルター付きポイント座標配列を維持* @param start* @param dimatived：edparam dmax：@param dmax：@param dmaxifid bigified distict* @param dmaxifid bigified statcript* @param trajcompressc（enpoint [] enpinit、arraylist <enpoint> enparrayfilter、int start、int end、double dmax）{if（start <end）{//再帰条件二重maxdist = 0; //最大距離int cur_pt = 0 ;/現在のサブスクリプトDistosegment（enpinit [start]、enpinit [end]、enpinit [i]）; //対応するラインセグメントまでの距離（curdist> maxdist）{maxdist = curdist;} //最大距離の場合、最大距離の場合、最大距離の場合の最大距離の場合、最大距離の場合、最大距離の場合、最大距離の場合は、最大距離の場合、最大距離の場合、最大距離の場合、最大距離の場合、 dmax）{enparrayfilter.add（enpinit [cur_pt]）; //現在のポイントをフィルタリングされた配列に追加//元のラインセグメントを現在のポイントを中心とした2つのセグメントに分解し、それぞれ再帰処理を実行し、それぞれtrajcoccressc（enpinit、enparrayfilter、cur_pt、dmax）; trajcompressc（enpinit、enparrayfilter、cur_pt、end、dmax）;}}}/***関数：平均距離エラー* @param pgpsarrayinit* @param pgpsarrayfiltersort* @param pgpsarrayfiltersort* @return：urturn（arr dibaring dioutic getmean pgpsarrayinit、arraylist <enpote> pgpsarrayfiltersort）{double sumdist = 0.0; for（int i = 1; i <pgpsarrayfiltersort.size（）; i ++）{int start = pgpsarrayfiltersort.get（i-1）.id; int = pgpsarrayfiltertort.id.id; j = start+1; j <end; j ++）{sumdist+= distosegment（pgpsarrayinit.get（start）、pgpsarrayinit.get（end）、pgpsarrayinit.get（j））;}}パートIVの手順の結果
4.1プログラム出力結果
圧縮結果：
（1）ポイントの総数：140ポイント。 （2）平均距離エラー：7.943786; （3）圧縮率：4.4444％
4.2シミュレーション結果
軌道圧縮の後、元の緯度と経度の座標ポイントを圧縮およびフィルターされた緯度と経度の座標ポイントに変換します。これらの2つのポイントを書き込み、データを2つのファイルに調整し、これらの2つのファイルに従って圧縮の前後に軌跡を描画し、それらを比較します。比較結果に基づいて、軌道圧縮アルゴリズムが効果的かどうかを確認できます。最終的な比較結果を図4.1に示します。
パート5の概要
このプログラムの執筆プロセス中に、私はさまざまな問題に遭遇し、多くのプログラミング経験を学びました。以下は、遭遇した問題と解決策の要約であり、最終的にプログラムの欠点の改善のための提案を提出しました。
5.1遭遇した問題と解決策
質問1：緯度および経度座標順序の問題
解決策：距離式のパラメーターは、緯度が前面にあり、経度が後ろにあることであり、緯度と経度の座標ポイントの順序を調整する必要があることです。
質問2：距離を負にすることはできません
解決策：見つかった距離が負にならないことを確認し、絶対値関数を追加します。
質問3：DPアルゴリズムの実装の詳細
解決策：添え字の問題を解決するためにアレイリスト配列を使用し始めました。再帰的に解くと大きなエラーがありました。その後、再帰のために通常の配列のサブスクリプを使用するように切り替えましたが、結果ははるかに優れていました。
5.2既存の欠点と見通し
（1）軌道圧縮を実行するとき、DPアルゴリズムは最も単純なアルゴリズムであり、最適ではありません。良い結果を持ついくつかのアルゴリズムを使用して、再び軌道圧縮を実行できます。
（2）この実験のデータレコードは3,150であり、データの量は大きくありません。 10億のデータがある場合はどうすればよいですか？ハードウェア、分散、データの前処理、データセグメンテーション、および優れたパフォーマンスのデータウェアハウスを検討できます。
上記は、軌道圧縮を実装するためのJavaプログラミングのDouglas-Peuckerアルゴリズムの詳細なコードに関するこの記事の完全な内容です。私はそれが誰にでも役立つことを願っています。欠点がある場合は、それを指摘するためにメッセージを残してください。このサイトへのご支援をありがとうございました！