Android Mapview：將重疊標記合併到一個新標記中

Question

所以我有一個帶有大量標記的MapView，其中大部分都集中在英里寬的集羣中。當縮放標記重疊並似乎只有一個。我想要達到的是在某個縮放級別下用重疊的標記替換重疊的標記，該標記將顯示標記的密度，並且onClick將縮放以顯示內部的所有標記。我知道我可以用蠻力測距來做到這一點，但是必須有更高效的方法。任何人都可以通過解決方案或者智能算法來實現這個目標？

Answer 1

嗯......假設標記沒有分組，分層或任何東西：爲什麼 - 在顯示它們之前 - 您是不是創建了一定密度的網格並將標記簡單地放入網格的單元格中？

如果您再計算幾個標記落入同一個bin（網格單元格） - 您可以對它們進行分組。如果你需要稍微更聰明的分組，你也可以檢查鄰近的單元格。

也許這聽起來有點原始，但：

• 沒有N^2種算法
• 關於輸入
• 沒有必要的排序沒有設想到另外它不會處理標記來顯示

---

網格的代碼：

注 - 我來自C++世界（通過[算法]標籤得到這裏），所以我會堅持僞C++。我不知道mapview的API。但如果這不能有效地翻譯成你正在使用的任何語言/圖書館，我會感到驚訝。

輸入： - 的標誌 列表 - 矩形觀看世界座標​​窗口（我們目前正在尋找世界的科）

在最簡單的形式，它會是這個樣子：

void draw(MarkerList mlist, View v) { 

    //binning: 

    list<Marker> grid[densityX][densityY]; //2D array with some configurable, fixed density 
    foreach(Marker m in mlist) { 
     if (m.within(v)) { 
      int2 binIdx; 
      binIdx.x=floor(densityX*(m.coord.x-v.x1)/(v.x2-v.x1)); 
      binIdx.y=floor(densityY*(m.coord.y-v.y1)/(v.y2-v.y1)); 
      grid[binIdx.x][binIdx.y].push(m); //just push the reference 
     } 

    //drawing: 

    for (int i=0; i<densityX; ++i) 
    for (int j=0; j<densityY; ++j) { 
     if (grid[i][j].size()>N) { 
      GroupMarker g; 
      g.add(grid[i][j]); //process the list of markers belonging to this cell 
      g.draw(); 
     } else { 
      foreach (Marker m in grid[i][j]) 
       m.draw() 
     } 
    } 

} 

可能出現的問題是不需要的網格拆分可能出現在某個聚簇組中，形成兩個GroupMarkers。爲了解決這個問題，你可能不僅要考慮一個網格單元，還要考慮其在「\ drawing」部分中的鄰居，並且 - 如果分組 - 將相鄰單元標記爲已訪問。

Answer 2

假設您的標記在一個ItemizedOverlay中組合在一起，您可以創建一個在地圖縮放時調用的方法。這將比較每個標記的像素座標以查看它們是否重疊並設置標記。然後在繪製方法中，您可以繪製分組標記或個人;

喜歡的東西：

//this would need to be wired to be called when the mapview is zoomed 
    //it sets the drawgrouped flag if co-ordinates are close together 
    Boolean drawGrouped=false; 
    public void onMapZoom(MapView mapView){ 
     //loop thru overlay items 
     Integer i,l=this.size(); 
     OverlayItem item; 
     Integer deltaX=null,deltaY=null; 
     Projection proj = mapView.getProjection(); 
     Point p=new Point(); 
     Integer x=null,y=null; 
     Integer tolerance = 10; //if co-ordinates less than this draw grouped icon 
     for(i=0;i<l;i++){ 
     //get the item 
     item=this.getItem(i); 
     //convert the overlays position to pixels 
     proj.toPixels(item.getPoint(), p); 
     proj.toPixels(item.getPoint(), p); 
     //compare co-ordinates 
     if(i==0){ 
      x=p.x; 
      y=p.y; 
      continue; 
     } 
     deltaX=Math.abs(p.x-x); 
     deltaY=Math.abs(p.y-y); 

     //if the co-ordinates are too far apart dont draw grouped 
     if(deltaX>tolerance || deltaY>tolerance){ 
      drawGrouped=false; 
      return; 
     } 
     x=p.x; 
     y=p.y; 
     } 
     //all co-ords are within the tolerance 
     drawGrouped=true; 
    } 

    public void draw(android.graphics.Canvas canvas, MapView mapView, boolean shadow){ 
     if(drawGrouped==true){ 
      //draw the grouped icon *needs to be optimised to only do it once 
      drawGrouped(canvas,mapView,shadow); 
      return; 
     } 
     //not grouped do regular drawing 
     super.draw(canvas, mapView, shadow); 
    } 

Answer 3

如果標記分組，你必須在什麼縮放級別的公平的想法，你應該顯示單個標記或標記組例如縮放級別> 17，然後顯示單個標記，否則顯示組標記。我使用的代碼這樣的事情在我的ItemizedOverlay改變我的標記：

@Override 
public void draw(Canvas canvas, MapView mapv, boolean shadow) 
{  
    int zoom = mapv.getZoomLevel(); 

    switch(zoom) 
    { 
     case 19: 
      setMarkersForZoomLevel19(); 
      break; 
     case 18: 
      setMarkersForZoomLevel18(); 
      break; 
     case 17: 
      setMarkersForZoomLevel17(); 
      break; 
     case 16: 
      setMarkersForZoomLevel16(); 
      break; 
     default: 
      // Hide the markers or remove the overlay from the map view.     
      mapv.getOverlays().clear(); 
    }  

    area.drawArea(canvas, mapv); 

    // Putting this call here rather than at the beginning, ensures that 
    // the Overlay items are drawn over the top of canvas stuff e.g. route lines. 
    super.draw(canvas, mapv, false);   

} 


private void setMarkersForZoomLevel19() 
{  
    for (JourneyOverlayItem item : mOverlays) 
    {    
     item.setMarker(areaPointIcon48);    
    } 
} 

如果它可能有一個集中的個體標記，你可以很容易地獲得最大和最小的緯度和經度以及它們之間的差異將給你經緯度範圍（這可以用來縮放跨度以顯示標記組）。除以2的跨度，你應該有放置組標記的中心點。

Answer 4

你在找什麼通常稱爲聚類。有一些常見的技術可以做到這一點，例如，你可以參考這個SO question，它會導致這post。

其基本思路是根據當前縮放級別將地圖分成平方（可以基於縮放級別緩存計算以避免在用戶開始縮放時重新計算），並根據它們屬於哪個平方。所以你最終會根據縮放級別進行某種分組，例如1-5級只畫出標記，5-8級將它們分成20英里的正方形，在50英里的正方形中放置9-10個，等等上。

這裏是SO另一個相關的問題，你可能想看看，不知道這雖然表現：Android Maps Point Clustering

Answer 5

以下基於像素的距離務實的解決辦法果然奏效最適合我：

http://www.appelsiini.net/2008/11/introduction-to-marker-clustering-with-google-maps

Answer 6

我將Cygnus X1的答案轉換爲Java。將此方法放入自定義疊加層中，並修改drawSingle（）和drawGroup（）以滿足您的需要。您也可以提高性能，例如將ArrayLists轉換爲原始數組。

@Override 
    public void draw(Canvas canvas, MapView mapView, boolean shadow) { 
     // binning: 
     int densityX = 10; 
     int densityY = 10; 
     // 2D array with some configurable, fixed density 
     List<List<List<OverlayItem>>> grid = new ArrayList<List<List<OverlayItem>>>(
       densityX); 

     for(int i = 0; i<densityX; i++){ 
      ArrayList<List<OverlayItem>> column = new ArrayList<List<OverlayItem>>(densityY); 
      for(int j = 0; j < densityY; j++){ 
       column.add(new ArrayList<OverlayItem>()); 
      } 
      grid.add(column); 
     } 

     for (OverlayItem m : mOverlays) { 
       int binX; 
       int binY; 

       Projection proj = mapView.getProjection(); 
       Point p = proj.toPixels(m.getPoint(), null); 

      if (isWithin(p, mapView)) { 
       double fractionX = ((double)p.x/(double)mapView.getWidth()); 
       binX = (int) (Math.floor(densityX * fractionX)); 
       double fractionY = ((double)p.y/(double)mapView.getHeight()); 
       binY = (int) (Math 
         .floor(densityX * fractionY)); 
//    Log.w("PointClusterer absolute", p.x+ ", "+p.y); 
//    Log.w("PointClusterer relative", fractionX+ ", "+fractionY); 
//    Log.w("PointClusterer portion", "Marker is in portion: " + binX 
//      + ", " + binY); 
       grid.get(binX).get(binY).add(m); // just push the reference 
      } 
     } 

     // drawing: 

     for (int i = 0; i < densityX; i++) { 
      for (int j = 0; j < densityY; j++) { 
       List<OverlayItem> markerList = grid.get(i).get(j); 
       if (markerList.size() > 1) { 
        drawGroup(canvas, mapView, markerList); 
       } else { 
        // draw single marker 
        drawSingle(canvas, mapView, markerList); 
       } 
      } 
     } 
    } 

    private void drawGroup(Canvas canvas, MapView mapView, 
      List<OverlayItem> markerList) { 
     GeoPoint point = markerList.get(0).getPoint(); 
     Point ptScreenCoord = new Point(); 
     mapView.getProjection().toPixels(point, ptScreenCoord); 
     Paint paint = new Paint(); 
     paint.setTextAlign(Paint.Align.CENTER); 
     paint.setTextSize(30); 
     paint.setAntiAlias(true); 
     paint.setARGB(150, 0, 0, 0); 
     // show text to the right of the icon 
     canvas.drawText("GROUP", ptScreenCoord.x, ptScreenCoord.y + 30, paint); 
    } 

    private void drawSingle(Canvas canvas, MapView mapView, 
      List<OverlayItem> markerList) { 
     for (OverlayItem item : markerList) { 
      GeoPoint point = item.getPoint(); 
      Point ptScreenCoord = new Point(); 
      mapView.getProjection().toPixels(point, ptScreenCoord); 
      Paint paint = new Paint(); 
      paint.setTextAlign(Paint.Align.CENTER); 
      paint.setTextSize(30); 
      paint.setAntiAlias(true); 
      paint.setARGB(150, 0, 0, 0); 
      // show text to the right of the icon 
      canvas.drawText("SINGLE", ptScreenCoord.x, ptScreenCoord.y + 30, 
        paint); 
     } 
    } 

    public static boolean isWithin(Point p, MapView mapView) { 
     return (p.x > 0 & p.x < mapView.getWidth() & p.y > 0 & p.y < mapView 
       .getHeight()); 
    } 
} 

Answer 7

這是我使用的方法。但是，它是O（n^2）。

引腳必須根據突出來排序。

突出最高的挑針。看看它周圍的所有引腳。吸收靠近該引腳的引腳。

然後移動到下一個最高的突出銷。照着做。重複。

簡單。

如果您移動地圖，放大圖像，縮小圖像，並且希望確保新圖釘未被重新繪製，情況就會變得複雜。因此，您需要檢查每個羣集是否必須在放大期間進行拆分，然後檢查每個羣集是否需要在縮小期間進行合併。然後你刪除不存在的引腳並添加新的引腳。對於添加的每個引腳，您都要檢查他們是否應該加入羣集或形成自己的羣集。