所以我有一个带有很多标记的 MapView，其中大部分都集中在英里宽的集群中。缩放时，标记重叠并且似乎只有一个。我想要实现的是在某个缩放级别用一个组标记替换重叠标记，该标记将显示标记的密度，onClick 将缩放以显示内部的所有标记。我知道我可以通过蛮力距离测量来做到这一点，但必须有更有效的方法。有人对我如何实现这一目标有任何解决方案或智能算法吗？
问问题
8574 次
7 回答
11
嗯......假设标记没有分组，分层或任何东西：为什么 - 在显示它们之前 - 你不创建一定密度的网格并将标记简单地放入网格的单元格中？
如果您然后计算几个标记落入同一个箱（网格单元） - 您可以将它们分组。如果您需要更巧妙的分组，您还可以检查相邻的单元格。
也许这听起来有点原始，但是：
- 没有 n^2 算法
- 没有关于输入顺序的假设
- 无需额外处理不会显示的标记
网格的代码：
注意 - 我来自 C++ 世界（通过 [algorithm] 标签来到这里），所以我会坚持使用伪 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()
}
}
}
可能出现的问题是，在某个集群组中可能会出现不需要的网格拆分，从而形成两个 GroupMarker。为了解决这个问题，您可能不仅要考虑一个网格单元，还要考虑“\drawing”部分中的相邻单元，并且 - 如果分组 - 将相邻单元标记为已访问。
于 2011-10-24T22:37:28.413 回答
3
我将 Cygnus X1 的答案转换为 Java。将此方法放在您的自定义 Overlay 中并修改 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());
}
}
于 2012-07-20T09:56:28.603 回答
3
以下基于像素距离的实用解决方案对我来说确实最有效：
http://www.appelsiini.net/2008/11/introduction-to-marker-clustering-with-google-maps
于 2011-10-28T13:22:07.137 回答
2
您正在寻找的通常称为聚类。有一些常见的技术可以做到这一点，例如，您可以参考这个SO question，它导致了这篇文章。
基本思想是根据当前缩放级别将地图划分为正方形（您可以根据缩放级别缓存计算以避免用户开始缩放时重新计算），并根据它们所属的正方形对它们进行分组。因此，您最终会根据缩放级别进行某种分组，即级别 1-5 只需绘制标记，级别 5-8 将它们分组为 20 英里的正方形，9-10 分组为 50 英里的正方形，等等上。
这是关于 SO 的另一个相关问题，您可能想看看，但不确定它的性能：Android Maps Point Clustering
于 2011-10-25T06:57:29.060 回答
2
假设您的标记在 ItemizedOverlay 中组合在一起，您可以创建一个在地图缩放时调用的方法。这将比较每个标记的像素坐标以查看它们是否重叠并设置标志。然后在 draw 方法中，您可以绘制分组标记或个人；
就像是：
//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);
}
于 2011-10-20T06:20:29.313 回答
1
如果您的标记被分组，您将清楚地知道应该在什么缩放级别显示单个标记或组标记，例如缩放级别> 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，您应该有放置组标记的中心点。
于 2011-10-20T23:10:27.997 回答
0
这是我使用的方法。但是，它是 O(n^2)。
引脚必须根据突出进行排序。
挑针最高突出。查看它周围的所有引脚。吸收该引脚附近的引脚。
然后移动到下一个最高突出的引脚。照着做。重复。
简单的。
如果您四处移动地图、放大、缩小地图，并且您希望确保不会重新绘制新的图钉，事情就会变得复杂。因此，您检查每个集群是否必须在放大期间拆分，然后检查每个集群是否必须在缩小期间合并。然后您删除已消失的引脚并添加新引脚。对于您添加的每个引脚，您检查它们是否应该加入集群或形成自己的集群。
于 2012-09-06T03:21:05.903 回答