2011年1月6日 星期四

Android 開發筆記 - 調整 GPS 座標個數,以提昇路徑繪圖效率

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 個數的刪減囉


沒有留言:

張貼留言