2008-09-16 7 views
22

マップ上の点のクラスタリング(lat/longs)を調べています。高速かつスケーラビリティのある適切なアルゴリズムに関する推奨事項はありますか?マッピングアプリケーション用のクラスタリングアルゴリズム


@Gilligan:はい - 私は一連のlat/lngとマップビューポートを持っています。私は混乱を取り除くために一緒に近いポイントをクラスタリングしようとしています。

私はすでに問題(see here)の解決方法を持っていますが、問題を効率的に解決する正式なアルゴリズムがあるかどうかは疑問です。

+0

削除しないされた場合は、緯度と経度によって与えられる物理的位置に基づいてクラスタリングしていますか? –

+0

達成したいことを示すコードを投稿することはできますか?私はあなたが「クラスタリング」を意味するのかと混同しています。それらを世界の地図にプロットしていますか? – Gilligan

答えて

6

仮想アースアプリケーションについては、クラスタリングを使用しました。 hereです。高速で簡単に拡張可能な稲妻です。

4

QuadTileスキームを使用してすべてのポイントのインデックスを作成してから、縮尺に基づいてさらに4分割します。同じ位置にあるすべてのポイントは、インデックス内でお互いに近くなり、クラスタリングを効率的に実行できます。

QuadTilesはMorton Codesの例であり、そのウィキペディアの記事からリンクされているpythonの例があります。

1

私はさまざまなライブラリを見て、彼らは非常に複雑で単語ので、私は私自身のクラスタリングアルゴリズム

を作ることにしました。ここに私のコードは、この計算は、//

static int OFFSET = 268435456; 
    static double RADIUS = 85445659.4471; 
    static double pi = 3.1444; 

public static double lonToX(double lon) { 
     return Math.round(OFFSET + RADIUS * lon * pi/180); 
    } 

    public static double latToY(double lat) { 
     return Math.round(OFFSET 
       - RADIUS 
       * Math.log((1 + Math.sin(lat * pi/180)) 
         /(1 - Math.sin(lat * pi/180)))/2); 
    } 
のJava

に行くを理解することができませんでした特定のズームレベルで牽引LAT長い点間の画素距離

public static int pixelDistance(double lat1, double lon1, double lat2, 
      double lon2, int zoom) { 
     double x1 = lonToX(lon1); 
     double y1 = latToY(lat1); 

     double x2 = lonToX(lon2); 
     double y2 = latToY(lat2); 

     return (int) (Math 
       .sqrt(Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2))) >> (21 - zoom); 
    } 

//実際クラスタを算出する主な機能1.緯度の長い点のArrayListを長さに反復します。 2.内側のループ同じアライリストのコピーが、i + 1の位置から反復されます。つまり、トップループのインデックスを残します。 3.ピクセルの距離が非常に少ない場合、0番目の要素がセントロイドの中心とみなされ、それをクラスタに入れます 4.クラスタを形成したトップarraylistとコピーarraylistからすべての要素を削除します。 5インデックスを0から再初期化してプロセスを再開します。 6選択重心がないクラスタは、その要素が

static ArrayList<Cluster> cluster(ArrayList<Marker> markers, int zoom) { 

     ArrayList<Cluster> clusterList = new ArrayList<Cluster>(); 

     ArrayList<Marker> originalListCopy = new ArrayList<Marker>(); 

     for (Marker marker : markers) { 
      originalListCopy.add(marker); 
     } 

     /* Loop until all markers have been compared. */ 
     for (int i = 0; i < originalListCopy.size();) { 

      /* Compare against all markers which are left. */ 

      ArrayList<Marker> markerList = new ArrayList<Marker>(); 
      for (int j = i + 1; j < markers.size();) { 
       int pixelDistance = pixelDistance(markers.get(i).getLatitude(), 
         markers.get(i).getLongitude(), markers.get(j) 
           .getLatitude(), markers.get(j).getLongitude(), 
         zoom); 

       if (pixelDistance < 40) { 

        markerList.add(markers.get(i)); 
        markerList.add(markers.get(j)); 

        markers.remove(j); 

        originalListCopy.remove(j); 
        j = i + 1; 
       } else { 
        j++; 
       } 

      } 

      if (markerList.size() > 0) { 
       Cluster cluster = new Cluster(clusterList.size(), markerList, 
         markerList.size() + 1, originalListCopy.get(i) 
           .getLatitude(), originalListCopy.get(i) 
           .getLongitude()); 
       clusterList.add(cluster); 
       originalListCopy.remove(i); 
       markers.remove(i); 
       i = 0; 

      } else { 
       i++; 
      } 

      /* If a marker has been added to cluster, add also the one */ 
      /* we were comparing to and remove the original from array. */ 

     } 
     return clusterList; 
    } 

Just pass in your array list here containing latitude and longitude 

then to display clusters 
here goes the function 


@Override 
    public void onTaskCompleted(ArrayList<FlatDetails> flatDetailsList) { 

     LatLngBounds.Builder builder = new LatLngBounds.Builder(); 

     originalListCopy = new ArrayList<FlatDetails>(); 
     ArrayList<Marker> markersList = new ArrayList<Marker>(); 
     for (FlatDetails detailList : flatDetailsList) { 

      markersList.add(new Marker(detailList.getLatitude(), detailList 
        .getLongitude(), detailList.getApartmentTypeString())); 

      originalListCopy.add(detailList); 

      builder.include(new LatLng(detailList.getLatitude(), detailList 
        .getLongitude())); 

     } 

     LatLngBounds bounds = builder.build(); 
     int padding = 0; // offset from edges of the map in pixels 
     CameraUpdate cu = CameraUpdateFactory.newLatLngBounds(bounds, padding); 

     googleMap.moveCamera(cu); 

     ArrayList<Cluster> clusterList = Utils.cluster(markersList, 
       (int) googleMap.getCameraPosition().zoom); 

     // Removes all markers, overlays, and polylines from the map. 
     googleMap.clear(); 

     // Zoom in, animating the camera. 
     googleMap.animateCamera(CameraUpdateFactory.zoomTo(previousZoomLevel), 
       2000, null); 

     CircleOptions circleOptions = new CircleOptions().center(point) // 
       // setcenter 
       .radius(3000) // set radius in meters 
       .fillColor(Color.TRANSPARENT) // default 
       .strokeColor(Color.BLUE).strokeWidth(5); 

     googleMap.addCircle(circleOptions); 

     for (Marker detail : markersList) { 

      if (detail.getBhkTypeString().equalsIgnoreCase("1 BHK")) { 
       googleMap.addMarker(new MarkerOptions() 
         .position(
           new LatLng(detail.getLatitude(), detail 
             .getLongitude())) 
         .snippet(String.valueOf("")) 
         .title("Flat" + flatDetailsList.indexOf(detail)) 
         .icon(BitmapDescriptorFactory 
           .fromResource(R.drawable.bhk1))); 
      } else if (detail.getBhkTypeString().equalsIgnoreCase("2 BHK")) { 
       googleMap.addMarker(new MarkerOptions() 
         .position(
           new LatLng(detail.getLatitude(), detail 
             .getLongitude())) 
         .snippet(String.valueOf("")) 
         .title("Flat" + flatDetailsList.indexOf(detail)) 
         .icon(BitmapDescriptorFactory 
           .fromResource(R.drawable.bhk_2))); 

      } 

      else if (detail.getBhkTypeString().equalsIgnoreCase("3 BHK")) { 
       googleMap.addMarker(new MarkerOptions() 
         .position(
           new LatLng(detail.getLatitude(), detail 
             .getLongitude())) 
         .snippet(String.valueOf("")) 
         .title("Flat" + flatDetailsList.indexOf(detail)) 
         .icon(BitmapDescriptorFactory 
           .fromResource(R.drawable.bhk_3))); 

      } else if (detail.getBhkTypeString().equalsIgnoreCase("2.5 BHK")) { 
       googleMap.addMarker(new MarkerOptions() 
         .position(
           new LatLng(detail.getLatitude(), detail 
             .getLongitude())) 
         .snippet(String.valueOf("")) 
         .title("Flat" + flatDetailsList.indexOf(detail)) 
         .icon(BitmapDescriptorFactory 
           .fromResource(R.drawable.bhk2))); 

      } else if (detail.getBhkTypeString().equalsIgnoreCase("4 BHK")) { 
       googleMap.addMarker(new MarkerOptions() 
         .position(
           new LatLng(detail.getLatitude(), detail 
             .getLongitude())) 
         .snippet(String.valueOf("")) 
         .title("Flat" + flatDetailsList.indexOf(detail)) 
         .icon(BitmapDescriptorFactory 
           .fromResource(R.drawable.bhk_4))); 

      } else if (detail.getBhkTypeString().equalsIgnoreCase("5 BHK")) { 
       googleMap.addMarker(new MarkerOptions() 
         .position(
           new LatLng(detail.getLatitude(), detail 
             .getLongitude())) 
         .snippet(String.valueOf("")) 
         .title("Flat" + flatDetailsList.indexOf(detail)) 
         .icon(BitmapDescriptorFactory 
           .fromResource(R.drawable.bhk5))); 

      } else if (detail.getBhkTypeString().equalsIgnoreCase("5+ BHK")) { 
       googleMap.addMarker(new MarkerOptions() 
         .position(
           new LatLng(detail.getLatitude(), detail 
             .getLongitude())) 
         .snippet(String.valueOf("")) 
         .title("Flat" + flatDetailsList.indexOf(detail)) 
         .icon(BitmapDescriptorFactory 
           .fromResource(R.drawable.bhk_5))); 

      } 

      else if (detail.getBhkTypeString().equalsIgnoreCase("2 BHK")) { 
       googleMap.addMarker(new MarkerOptions() 
         .position(
           new LatLng(detail.getLatitude(), detail 
             .getLongitude())) 
         .snippet(String.valueOf("")) 
         .title("Flat" + flatDetailsList.indexOf(detail)) 
         .icon(BitmapDescriptorFactory 
           .fromResource(R.drawable.bhk_2))); 

      } 
     } 

     for (Cluster cluster : clusterList) { 

      BitmapFactory.Options options = new BitmapFactory.Options(); 
      options.inMutable = true; 
      options.inPurgeable = true; 
      Bitmap bitmap = BitmapFactory.decodeResource(getResources(), 
        R.drawable.cluster_marker, options); 

      Canvas canvas = new Canvas(bitmap); 

      Paint paint = new Paint(); 
      paint.setColor(getResources().getColor(R.color.white)); 
      paint.setTextSize(30); 

      canvas.drawText(String.valueOf(cluster.getMarkerList().size()), 10, 
        40, paint); 

      googleMap.addMarker(new MarkerOptions() 
        .position(
          new LatLng(cluster.getClusterLatitude(), cluster 
            .getClusterLongitude())) 
        .snippet(String.valueOf(cluster.getMarkerList().size())) 
        .title("Cluster") 
        .icon(BitmapDescriptorFactory.fromBitmap(bitmap))); 

     } 

    } 




ANY QUESTIONS OR DOUBTS PLEASE ASK WILL CLEAR THEM ALL ...........THANKS 
+0

テキストによる説明はどうぞ。 –

+0

コードのみの回答は一般的に推奨されません...このコードの使用方法の詳細/問題の解決方法に関する詳細情報を含めてください。 –

+0

こんにちはParagとColey Brigmanのコードにはインラインコメントがあります。あなたは私に説明したいと思っている部分を私に教えてください。 – user1530779

関連する問題