摘要：需要實現一個地圖圖標聚合算法最終功能類似安居客在地圖搜索房源的功能當地圖縮放級別較大時僅用一個地圖標記顯示該區域總數當地圖縮小至一定級別時每條信息才可以顯示為多帶帶的圖標自己擬了一套算法基本思想是以網格遞歸分割全部數據點直到網格大小達到閾值或
需要實現一個地圖圖標聚合算法, 最終功能類似 安居客 在地圖搜索房源的功能. 當地圖縮放級別較大時, 僅用一個地圖標記顯示該區域總數; 當地圖縮小至一定級別時, 每條信息才可以顯示為多帶帶的圖標.
自己擬了一套算法, 基本思想是, 以網格遞歸分割全部數據點, 直到網格大小達到閾值, 或者每個網格內都僅存在至多一個數據點. 然后根據遞歸層次 (即網格層次), 將全部數據點依該層次存入一個樹型數據結構. 地圖縮放時即根據該樹型結構取出對應地圖縮放層次要顯示的數據點, 及聚合數量.
先上思路和偽代碼:
定義
常量:
單次等分一邊分母為 DIVIDER (方格 4 等分則 DIVIDER 為 2, 9 等分則 DIVIDER 為 3)
單元格可允許的最小邊長為 MIN_LENGTH
已知條件:
經緯度點隊列 list
變量:
覆蓋所有點所需正方形區域邊長為 area_length
覆蓋所有點所需正方形區域 左下角 (lon1, lat1)
覆蓋所有點所需正方形區域 右上角 (lon2, lat2)
分割的最小單元格邊長為 grid_length
分割的最小單元格經度差 grid_lon
分割的最小單元格緯度差 grid_lat
分割層級數為 layer_count
函數:
dis(point1, point2) // 兩點(經緯度)間距
lon2dis(lon) // 經度差轉距離
lat2dis(lat) // 緯度差轉距離
dis2lon(dis) // 距離轉經度差
dis2lat(dis) // 距離轉緯度差
數據結構:
point_layer {
point // 點的原始信息
index_list // 點的層級列表,層級由大到小降序排列 - [01, 22, 11]
}
index {
x // 某一層級內的 橫坐標
y // 某一層級內的 縱坐標
}
算法步驟 (偽代碼)
遍歷 list , 得到覆蓋所有點的最小邊界 (lon1, lat1) (lon2, lat2):
lon1 = lon2 = list.get(0).lon
lat1 = lat2 = list.get(0).lat
for (point in list); do
lon1 = lon1 < point.lon ? lon1 : point.lon
lat1 = lat1 < point.lat ? lat1 : point.lat
lon2 = lon2 > point.lon ? lon2 : point.lon
lat2 = lat2 > point.lat ? lat2 : point.lat
done
此邊界應適當擴大.
點過少或者區域過小時以大數值擴大邊界,點多時則以小數值擴大邊界:
lon1 = lon1 - offset
lat1 = lat1 - offset
lon2 = lon2 + offset
lat2 = lat2 + offset
確定 area_length 及 區域邊界坐標 (左上角, 右下角)
x = lat2dis(lat2 - lat1)
y = lon2dis(lon2 - lon1)
area_length = x > y ? x : y
根據 area_length 及 MIN_LENGTH 即可確定 grid_length 及 layer_count
layer_count = 1
grid_length = area_length
while (grid_length > MIN_LENGTH); do
grid_length = grid_length / DIVIDER
layer_count ++
done
grid_lon = dis2lon(grid_length)
grid_lat = dis2lat(grid_length)
根據以上求出的各值, 遍歷 list 逐個確定每個點所在的單元格編號.
編號規則可按從左到右, 從下到上順序等,這里按網格二維坐標編碼:
for (point in list); do
lon_delta = point.lon - lon1 // 距左上角經度
lat_delta = point.lat - lat1 // 距左上角緯度
nx = lon_delta / grid_lon // 整除取整,得到距左下角x軸格子數
ny = lat_delta / grid_lat // 整除取整,得到距左下角y軸格子數
// 按層級為每個點做標記,從最小層級開始遍歷
pl = new point_layer()
pl.point = point
idx_x = nx
idx_y = ny
for (int i = 0; i < layer_count; i ++); do
idx = new index()
idx.x = idx_x % DIVIDER // 取余得本層級內的x坐標
idx.y = idx_y % DIVIDER // 取余得本層級內的y坐標
pl.index_list.add(idx)
idx_x = idx.x / DIVIDER // 取除為取得上個層級坐標做準備
idx_y = idx.y / DIVIDER // 取除為取得上個層級坐標做準備
done
pl_list.add(pl)
done
實現
下面開始方案落地. 雖然寫的是 Android 程序, 但下面其實是純 java 代碼.
先定義一個標記抽象類(接口) IMarker:
public interface IMarker {
double getLatitude();
double getLongitude();
}
定義為接口便于和具體的地圖解耦. 因此這套算法即可以用于百度地圖, 也可以用于高德, 騰訊等地圖. 只需要繼承相應地圖的標記類, 然后再 implement 這個接口, 就可以應用這套算法了.
然后是最難寫的, 節點樹的數據結構:
package com.myapp.MapMarkerCluter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* author: lx
* date: 16-9-27
*/
public class IndexTree {
private HashMap> children;
private IndexTree parent;
private K index;
private T data;
private final Object mLock = new Object();
public IndexTree(K index, T data) {
this.index = index;
this.data = data;
}
public void setData(T data) {
this.data = data;
}
public T getData() {
return data;
}
public K getIndex() {
return index;
}
public void setParent(IndexTree parent) {
this.parent = parent;
}
public IndexTree putChild(K index, T data) {
if (index == null) {
throw new IllegalArgumentException("null index is not acceptable");
}
IndexTree node = getChild(index);
if (node != null) {
node.data = data;
} else {
node = new IndexTree<>(index, data);
node.parent = this;
synchronized (mLock) {
if (children == null) {
children = new HashMap<>();
}
children.put(node.index, node);
}
}
return node;
}
public boolean putNodeByIndexList(List indexList, T data) {
int length;
if (indexList == null || (length = indexList.size()) == 0) {
throw new IllegalArgumentException("empty index is not acceptable");
}
if (!indexList.get(0).equals(index)) {
return false;
}
if (indexList.size() == 1) {
this.data = data;
} else {
IndexTree parent = this;
K idx;
for (int i = 1; i < length; i ++) {
idx = indexList.get(i);
if (i == length - 1) {
// end of index, put data.
parent.putChild(idx, data);
} else {
// way index. create if not exist.
IndexTree node = parent.getChild(idx);
if (node == null) {
node = parent.putChild(idx, null);
}
parent = node;
}
}
}
return true;
}
public IndexTree getParent() {
return parent;
}
public IndexTree getRoot() {
IndexTree node = this;
while (node.parent != null) {
node = node.parent;
}
return node;
}
public IndexTree getChild(K index) {
if (children == null) {
return null;
} else {
return children.get(index);
}
}
public IndexTree getNodeByIndexList(List indexList) {
int length;
if (indexList == null || (length = indexList.size()) == 0) {
throw new IllegalArgumentException("empty index is not acceptable");
}
if (!indexList.get(0).equals(index)) {
return null;
}
if (indexList.size() == 1) {
return this;
} else {
IndexTree node = this;
K idx;
for (int i = 1; i < length; i ++) {
idx = indexList.get(i);
node = node.getChild(idx);
if (node == null) {
// search fail before reach index end, return null
return null;
}
}
return node;
}
}
public List getChildDataList() {
if (children == null) {
return null;
} else {
ArrayList list = new ArrayList<>(children.size());
synchronized (mLock) {
Iterator> it = children.values().iterator();
while (it.hasNext()) {
list.add(it.next().data);
}
}
return list;
}
}
public int getChildCount() {
if (children == null) {
return 0;
} else {
return children.size();
}
}
public Iterator> iterateChild() {
if (children == null) {
return null;
} else {
return children.values().iterator();
}
}
public List> getNodeListByLevel(int level) {
LinkedList> ret = new LinkedList<>();
if (level <= 1) {
ret.add(this);
return ret;
} else if (children == null || children.size() == 0) {
return null;
} else {
synchronized (mLock) {
Iterator> it = children.values().iterator();
while (it.hasNext()) {
List> list = it.next().getNodeListByLevel(level - 1);
if (list != null) {
ret.addAll(list);
}
}
}
return ret;
}
}
@Override
public String toString() {
return index + "-" + (children == null ? 0 : children.size());
}
}
此容器的各類查詢 (取點, 取列表, 取數量) 基本都由遞歸實現, 基本就是為了實現上面偽代碼邏輯而設計的樹型結構.
水平實在有限, 對自己寫出的這個泛型容器比較不滿意: 基本就只能在這個場景下專用. 并且封裝也不甚徹底, 很多邏輯本應在此實現, 但都放在了下面的 MarkerCluster 類中去實現了.
MarkerCluster 類似一個 manager, 即使用上面兩個基礎類 IMarker 及 IndexTree, 來實現最終的業務邏輯:
package com.myapp.MapMarkerCluter;
import com.fm1031.app.util.Log;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* author: lx
* date: 16-9-26
*/
public class MarkerCluster {
// 單次等分一邊分母
private int divider;
// 單元格可允許的最小邊長
private int grid_min_length;
private int area_length;
private double lon1;
private double lat1;
private double lon2;
private double lat2;
private double grid_lon;
private double grid_lat;
private int grid_length;
private int layer_count;
private List list;
private IndexTree index_tree;
public MarkerCluster(int divider, int gridMinLength) {
this.divider = divider;
this.grid_min_length = gridMinLength;
}
public boolean isValid() {
return index_tree != null &&
(index_tree.getChildCount() != 0 || index_tree.getData() != null);
}
public void reset() {
list = null;
index_tree = null;
}
public void cluster(List markerList) {
list = markerList;
cluster();
}
public void cluster() {
if (divider <= 0 || grid_min_length <= 0) {
throw new IllegalStateException("pre condition not met !");
}
if (list == null || list.size() == 0) {
Log.w("liuxu", "cluster with no data at all");
return;
}
index_tree = new IndexTree<>(new Index(0, 0), null);
lon1 = lon2 = list.get(0).getLongitude();
lat1 = lat2 = list.get(0).getLatitude();
for (int i = list.size() - 1; i >= 0; i --) {
IMarker m = list.get(i);
if (m.getLatitude() == 0 || m.getLongitude() == 0) {
list.remove(m);
continue;
}
lon1 = lon1 < m.getLongitude() ? lon1 : m.getLongitude();
lat1 = lat1 < m.getLatitude() ? lat1 : m.getLatitude();
lon2 = lon2 > m.getLongitude() ? lon2 : m.getLongitude();
lat2 = lat2 > m.getLatitude() ? lat2 : m.getLatitude();
}
if (list.size() == 0) {
// no valid marker in list, just return
Log.w("liuxu", "cluster with no data at all");
return;
}
{
// enlarge area
if (lat1 == lat2) {
lat1 -= 0.05D;
lat2 += 0.05D;
}
if (lon1 == lon2) {
lon1 -= 0.05D;
lon2 += 0.05D;
}
double d_lon = (lon2 - lon1) * divider / 2;
double d_lat = (lat2 - lat1) * divider / 2;
lon1 -= d_lon;
lon2 += d_lon / 2;
lat1 -= d_lat / 2;
lat2 += d_lat / 2;
}
int x_delta = lat2dis(lat2 - lat1);
int y_delta = lon2dis(lon2 - lon1);
area_length = x_delta > y_delta ? x_delta : y_delta;
layer_count = 1;
grid_length = area_length;
while (grid_length > grid_min_length) {
grid_length = grid_length / divider;
layer_count ++;
}
grid_lon = dis2lon(grid_length);
grid_lat = dis2lat(grid_length);
for (IMarker m : list) {
List index_list = getIndexByLatLon(m.getLatitude(), m.getLongitude());
IndexTree t = index_tree.getNodeByIndexList(index_list);
if (t != null && t.getData() != null) {
t.getData().addMarker(m);
} else {
MarkerInfo info = new MarkerInfo(m, index_list);
index_tree.putNodeByIndexList(info.index_list, info);
}
}
clusterData(index_tree);
}
public List getIndexByLatLon(double lat, double lon) {
ArrayList index_list = new ArrayList<>(layer_count);
double lon_delta = lon - lon1;
double lat_delta = lat - lat1;
int nx = (int) (lon_delta / grid_lon);
int ny = (int) (lat_delta / grid_lat);
int idx_x = nx > 1 ? nx - 1 : 0;
int idx_y = ny > 1 ? ny - 1 : 0;
for (int i = 0; i < layer_count; i ++) {
Index idx = new Index(idx_x % divider, idx_y % divider);
idx_x = idx_x / divider;
idx_y = idx_y / divider;
index_list.add(0, idx);
}
return index_list;
}
public int getLevelByArea(
double lat_bottom, double lon_left, double lat_top, double lon_right) {
if (lat_bottom > lat2 || lat_top < lat1 || lon_left > lon2 || lon_right < lon1) {
// out of range
return 0;
}
if ((lat_top - lat_bottom) > 3 * (lat2 - lat1)) {
return 0;
}
int dis_lat = lat2dis(lat_top - lat_bottom);
int dis_lon = lon2dis(lon_right - lon_left);
int dis = dis_lat < dis_lon ? dis_lat : dis_lon;
int level = getLevelByDis(dis * 2 / 3) + 1;
level = level < layer_count ? level : layer_count;
//Log.d("liuxu", "getLevelByArea, level: " + level);
return level;
}
public List getMarkerListByLevel(int level) {
List> nodeList = index_tree.getNodeListByLevel(level);
if (nodeList != null && nodeList.size() != 0) {
ArrayList list = new ArrayList<>(nodeList.size());
for (IndexTree n : nodeList) {
list.add(n.getData());
}
return list;
} else {
return null;
}
}
public List getMarkerListByArea(
double lat_bottom, double lon_left, double lat_top, double lon_right) {
return getMarkerListByLevel(getLevelByArea(lat_bottom, lon_left, lat_top, lon_right));
}
public MarkerInfo clusterData(IndexTree index_tree) {
int childCount = index_tree.getChildCount();
if (childCount == 0) {
return index_tree.getData();
} else {
MarkerInfo data = index_tree.getData();
if (data == null) {
int marker_count = 0;
int center_x = divider / 2;
int center_y = divider / 2;
double offset = divider * divider;
MarkerInfo childData = null;
Iterator> it = index_tree.iterateChild();
while (it != null && it.hasNext()) {
IndexTree tree = it.next();
marker_count += clusterData(tree).marker_count;
double f = Math.pow(tree.getIndex().x - center_x, 2) +
Math.pow(tree.getIndex().y - center_y, 2);
if (f < offset) {
offset = f;
childData = tree.getData();
}
}
if (childData != null) {
data = new MarkerInfo(
childData.marker,
childData.index_list.subList(0, childData.index_list.size() - 1));
data.marker_count = marker_count;
index_tree.setData(data);
}
}
return data;
}
}
public int getLevelByDis(int dis) {
int level = layer_count;
int d = grid_length;
while (d < dis) {
level --;
d = d * divider;
}
return level > 0 ? level : 0;
}
public boolean isEndPointMarker(MarkerInfo marker) {
if (marker == null || marker.getIndexList() == null) {
return false;
}
return marker.getIndexList().size() == layer_count;
}
public List getEndPointDataList(MarkerInfo marker) {
List list = new ArrayList<>();
return getEndPointDataList(marker, list);
}
private List getEndPointDataList(MarkerInfo marker, List list) {
if (list == null) {
list = new ArrayList<>();
}
if (isEndPointMarker(marker)) {
if (marker.getMarkerList() != null) {
list.addAll(marker.getMarkerList());
} else {
list.add(marker.getMarker());
}
return list;
} else {
IndexTree node = index_tree.getNodeByIndexList(marker.getIndexList());
List childList = node.getChildDataList();
for (MarkerInfo m : childList) {
getEndPointDataList(m, list);
}
return list;
}
}
// ===========================================
// about index list
public static List getCommonIndexList(List index1, List index2) {
if (index1 == null || index2 == null) {
return null;
}
int size1 = index1.size();
int size2 = index2.size();
int size = size1 < size2 ? size1 : size2;
if (size == 0) {
return null;
}
ArrayList list = new ArrayList<>(size);
for (int i = 0; i < size; i ++) {
Index idx1 = index1.get(i);
Index idx2 = index2.get(i);
if (idx1.equals(idx2)) {
list.add(idx1);
} else {
break;
}
}
return list;
}
public static boolean containsIndexList(List list1, List list2) {
if (list1 == null || list2 == null) {
return false;
}
if (list1.size() < list2.size()) {
return false;
}
for (int i = 0; i < list1.size(); i ++) {
if (!list1.get(i).equals(list2.get(i))) {
return false;
}
}
return true;
}
public static boolean equalsIndexList(List list1, List list2) {
if (list1 == null || list2 == null) {
return false;
}
if (list1.size() != list2.size()) {
return false;
}
for (int i = 0; i < list1.size(); i ++) {
if (!list1.get(i).equals(list2.get(i))) {
return false;
}
}
return true;
}
private Comparator index_comparator = new Comparator() {
@Override
public int compare(Index lhs, Index rhs) {
if (lhs.x < rhs.x) {
return -1;
} else if (lhs.y < rhs.y) {
return 1;
} else {
return 0;
}
}
};
// =========================================
public static int lon2dis(double lon) {
return (int) Math.abs(lon * 111 * 1000);
}
public static int lat2dis(double lat) {
return (int) Math.abs(lat * 111 * 1000);
}
public static double dis2lon(int dis) {
return Math.abs((double) dis / 1000 / 111);
}
public static double dis2lat(int dis) {
return Math.abs((double) dis / 1000 / 111);
}
public static String indexList2string(List list) {
if (list == null || list.size() == 0) return null;
StringBuilder sb = new StringBuilder();
for (Index idx : list) {
sb.append("[").append(idx.x).append(",").append(idx.y).append("]");
}
return sb.toString();
}
// =========================================
public static class Index {
int x;
int y;
public Index(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object that) {
if (this == that) return true;
if (that == null) return false;
if (!(that instanceof Index)) return false;
Index index = (Index) that;
return (this.x == index.x && this.y == index.y);
}
@Override
public int hashCode() {
return 31 * x + y;
}
@Override
public String toString() {
return "[" + x + "," + y + "]";
}
}
public static class MarkerInfo {
IMarker marker;
List marker_list;
List index_list;
int marker_count;
public MarkerInfo(IMarker marker, List index_list) {
this.marker = marker;
this.index_list = index_list;
this.marker_count = 1;
}
public void addMarker(IMarker marker) {
if (marker_list == null) {
marker_list = new LinkedList<>();
if (this.marker != null) {
marker_list.add(this.marker);
}
}
marker_list.add(marker);
marker_count = marker_list.size();
}
public IMarker getMarker() {
return marker;
}
public List getMarkerList() {
return marker_list;
}
public boolean isMarkerListEmpty() {
return marker_list != null && marker_list.size() != 0;
}
public int getMarkerCount() {
return marker_count;
}
public List getIndexList() {
return index_list;
}
public String getIndexListString() {
return indexList2string(index_list);
}
@Override
public String toString() {
return getIndexListString() + getMarkerCount();
}
}
}
后記
該模塊與具體地圖完全解耦, 百度, 高德, 騰訊 地圖都能用.
不說效率如何, 起碼最終功能是實現了. 但算法實現水平確實弱了點, 很多地方寫的不滿意.
可優化的東西也很多, 比如: 目前遞歸等分是按正方形進行的, 如果給出的數據點的列表分布趨于正方形, 則該算法效率尚可; 如果數據點列表分布在一個窄帶內, 則有很大優化余地; 如果數據點列表在較大范圍內較稀疏, 則效率很差.
這套東西運行一年倒也沒出什么錯誤, 后續就是新需求趕新需求, 也就沒心思去優化這東西了. 各位大牛輕噴~.
