在 Android 開發教學筆記 - 透過 Google Maps API 畫出 GPS 路徑 提到關於繪製 GPS 路徑的方式之一，然而，有時路徑長度過長，如兩三千個 GPS 座標，則可能造成路徑繪圖的負擔。
在此嘗試降低 GPS 個數的方式：
- 以連續兩點為單位，計算差距，差距小於某數值則刪去
- 以連續三個點為單位，所建立的兩段直線的角度，若角度大過某個數值，則把中間點去除
其中前者會存在一些哪些點可刪或不可刪問題，並且去除個數有限，後者則是計算量大，刪除的效果不錯，在 2011_01_03_Schwechat_Brno.gpx 測資中，可以從不重複的一千多點縮小到兩、三百點，但仍會有畫出的路徑與道路偏移的問題，例外則是角度選擇的部份
簡單的角度實做，就是計算兩向量的 cosine 數值，將越靠近 -1 的進行刪除的動作，也就是兩向量越接近 180 度的直線。
片段程式碼：
public static void main(String a[] )
{
double logs[] = { 25.051981, 121.522751, /* ... , */ 25.064867, 121.526154 };
ArrayList<Double> data = new ArrayList<Double>();
for( int i=0; i<logs.length ; ++i )
data.add( new Double( logs[i] ) );
System.out.println( data.size() );
data = rebuildGSPLogs( data , 0 );
System.out.println( data.size() );
}
//
// list = { lat1, lng1, lat2, lng2, ... };
//
private ArrayList<Double> rebuildGSPLogsByAngleCheck( ArrayList<Double> list , int at )
{
if( at < 2 ) // begin at second point
at = 2;
// if( list.size() > at + 6 && at >= 0 )
while( list.size() > at + 6 && at >= 0 )
{
double x1 = list.get(at).floatValue() , y1 = list.get(at+1).floatValue() , x2 = list.get(at+2).floatValue(), y2 = list.get(at+3).floatValue() , x3 = list.get(at+4).floatValue() , y3 = list.get(at+5).floatValue();
double nx1 = x1-x2 ,nx2 = x3 - x2, ny1 = y1-y2 , ny2 = y3-y2;
double len1 = Math.sqrt( nx1*nx1 + ny1*ny1 ) , len2 = Math.sqrt( nx2*nx2 + ny2*ny2 );
if( len1 == 0 )
{
list.remove(at+2); // lat
list.remove(at+2); // lng
}
else if( len2 == 0 )
{
list.remove(at+4); // lat
list.remove(at+4); // lng
}
else
{
double checkCos = (nx1*nx2 + ny1*ny2 )/len1/len2 ;
if( checkCos > -0.986025 ) // >= -1 : keep all
{
at+=2;
}
else
{
list.remove(at+2); // lat
list.remove(at+2); // lng
}
}
// return rebuildGSPLogsByAngleCheck( list , at );
}
return list;
}
有些需要留意的點，原先把 rebuildGSPLogsByAngleCheck 寫成遞迴，在桌機上跑很正常，但移植到 Android 模擬器上，大概沒跑多久就掛了，查了錯誤訊息才得知 out of stack，所幸程式碼只需改個 2 行就改成非遞迴式。
除此之外，在繪圖方面，也可以採用一些方式提昇效率：
- 扣除重複位置的點
- 僅繪出可視地圖範圍內的路徑
對於前者部分，是因為就算 GPS 座標不同，在進行繪製的過程中，會先轉成對應的繪圖座標，在這樣的情境下，有些非常相近的 GPS 座標，其實是會被對應成同一個繪圖點，解法很簡單，就只要用個 Hash 就可以解掉；後者問題是在於一條路徑很長，但顯是在地圖上只是很小的一段路程，因此可以只挑出目前地圖看得見的部分進行繪製，也就是將 GPS 座標轉成繪圖座標，此時去判斷該繪圖座標的位置是不是落在目前螢幕顯示的區域，如判斷 X >= 0 && Y >= 0 && X < width && Y < height 。
然而，處理可見路徑的繪圖部分，有以下的問題：
由於兩點構成一條線，因此有可能下一個點已經超出目前顯示地圖的範圍，但剛剛畫的點離 MapView 邊框還有段距離，依據上述的條件則不會畫出連接線，導致看起來像路徑已經斷掉，這種情況也會發生在移動地圖時，前一個點已超出範圍，則會看到之前的路線斷掉。
解決方式有兩種：
- 使用一個 diff 數值來判斷，例如原先是判斷畫點得座標必須在 0 ~ mapView.getWidth() 且 0 ~ mapView.getHeight() 範圍才顯示，現在再加上一點數值來增大範圍
- x + diff >= 0 && x <= mapView.getWidth() && y + diff >= 0 && y <= mapView.getHeight()
- 使用兩個 list 來處理，假設整條路徑共有 n 個點，且第 x 點代表第一個被畫在螢幕上的點，那使用一個 stack 記錄 1~ x - 1 個點，第二個 list 記錄 x+1 ~ n 個點，以輔助繪出路徑 x-1 與 x 的路徑，以及 x 與 x+1 的路徑，以此解決路線斷掉的問題。如果並沒有一個 x 點會被畫出，那只好去找尋在可視地圖中，有沒有哪條線比較接近目前的位置，有的話則把它會出來，在此使用 cosine 的計算，挑選數值最接近 -1 的，代表夾角接近 180 度
第一種解法：
int diff = 100;
boolean useMoveTo = true;
for( int i=0; i<logs.length ; i+=2 )
{
out = getPixelXYFromGeoValue( p, logs[i], logs[i+1] );
if( out.x + diff < 0 || out.y + diff < 0 || out.x > mapView.getWidth() + diff || out.y > mapView.getHeight() + diff )
{
useMoveTo = true;
}
else if( useMoveTo ) // i = 0
{
myPath.moveTo(out.x, out.y);
useMoveTo = false;
}
else if( i+2 != logs.length )
{
myPath.lineTo(out.x, out.y);
}
else
{
myPath.setLastPoint(out.x, out.y);
}
}
第二種：
boolean useMoveTo = true;
int pCnt = 0;
HashMap<Point,String> hashMap = new HashMap<Point,String>();
Point check = getPixelXYFromGeoValue( p, srcLogs[gps_at], srcLogs[gps_at+1]);
ArrayList<Point> UseFF = new ArrayList<Point>();
ArrayList<Point> UsePP = new ArrayList<Point>();
for( int i=0; i<logs.length ; i+=2 )
{
out = getPixelXYFromGeoValue( p, logs[i], logs[i+1] );
if( hashMap.containsKey(out) )
continue;
hashMap.put(out, out.x+"-"+out.y);
if( out.x < 0 || out.y < 0 || out.x > mapView.getWidth() || out.y > mapView.getHeight() )
{
if( pCnt < 1 )
UsePP.add( out );
else
UseFF.add( out );
continue;
}
else if ( pCnt < 1 )
{
int size = UsePP.size();
if( size > 0 )
{
myPath.moveTo( UsePP.get(size-1).x, UsePP.get(size-1).y);
useMoveTo = false;
UsePP.clear();
}
}
else
{
int size = UseFF.size();
if( size > 0 )
{
myPath.lineTo( UseFF.get(0).x, UseFF.get(0).y);
if( size > 1 )
{
myPath.moveTo( UseFF.get(size-1).x, UseFF.get(size-1).y);
}
UseFF.clear();
useMoveTo = false;
}
}
pCnt++;
if( useMoveTo )
{
myPath.moveTo(out.x, out.y);
useMoveTo = false;
}
else if( i+2 != logs.length )
{
myPath.lineTo(out.x, out.y);
}
else
{
myPath.setLastPoint(out.x, out.y);
}
}
if ( pCnt < 1 )
{
int size = UsePP.size();
if( size > 1 )
{
double diff = 1;
int checkAt = -1;
for( int i=0 ; i+1<size; ++i )
{
double x1 = UsePP.get(i).x - check.x ;
double y1 = UsePP.get(i).y - check.y ;
double x2 = UsePP.get(i+1).x - check.x ;
double y2 = UsePP.get(i+1).y - check.y ;
double l1 = Math.sqrt( x1*x1 + y1*y1 );
double l2 = Math.sqrt( x2*x2 + y2*y2 );
double checkCos = (x1*x2 + y1*y2 )/l1/l2 ;
if( checkCos < diff )
{
diff = checkCos;
checkAt = i;
}
}
if( checkAt > -1 )
{
myPath.moveTo( UsePP.get(checkAt).x, UsePP.get(checkAt).y);
myPath.lineTo( UsePP.get(checkAt+1).x, UsePP.get(checkAt+1).y);
}
UsePP.clear();
}
}
else
{
int size = UseFF.size();
if( size > 0 )
{
myPath.lineTo( UseFF.get(0).x, UseFF.get(0).y);
UseFF.clear();
}
}
雖然降低 GPS 個數可以提升路徑繪圖的效率，但也因此失去精準度，特別是 Zoom Level 越高時，會看到路徑偏移很嚴重，或許還可以搭配 Zoom Level 來決定是否要做 GPS 個數的刪減囉
沒有留言:
張貼留言