需要實(shí)現(xiàn)一個(gè)地圖圖標(biāo)聚合算法, 最終功能類似 安居客 在地圖搜索房源的功能. 當(dāng)?shù)貓D縮放級(jí)別較大時(shí), 僅用一個(gè)地圖標(biāo)記顯示該區(qū)域總數(shù); 當(dāng)?shù)貓D縮小至一定級(jí)別時(shí), 每條信息才可以顯示為單獨(dú)的圖標(biāo).
自己擬了一套算法, 基本思想是, 以網(wǎng)格遞歸分割全部數(shù)據(jù)點(diǎn), 直到網(wǎng)格大小達(dá)到閾值, 或者每個(gè)網(wǎng)格內(nèi)都僅存在至多一個(gè)數(shù)據(jù)點(diǎn). 然后根據(jù)遞歸層次 (即網(wǎng)格層次), 將全部數(shù)據(jù)點(diǎn)依該層次存入一個(gè)樹型數(shù)據(jù)結(jié)構(gòu). 地圖縮放時(shí)即根據(jù)該樹型結(jié)構(gòu)取出對(duì)應(yīng)地圖縮放層次要顯示的數(shù)據(jù)點(diǎn), 及聚合數(shù)量.
先上思路和偽代碼:
定義
常量:
單次等分一邊分母為 DIVIDER (方格 4 等分則 DIVIDER 為 2, 9 等分則 DIVIDER 為 3)
單元格可允許的最小邊長(zhǎng)為 MIN_LENGTH
已知條件:
經(jīng)緯度點(diǎn)隊(duì)列 list
變量:
覆蓋所有點(diǎn)所需正方形區(qū)域邊長(zhǎng)為 area_length
覆蓋所有點(diǎn)所需正方形區(qū)域 左下角 (lon1, lat1)
覆蓋所有點(diǎn)所需正方形區(qū)域 右上角 (lon2, lat2)
分割的最小單元格邊長(zhǎng)為 grid_length
分割的最小單元格經(jīng)度差 grid_lon
分割的最小單元格緯度差 grid_lat
分割層級(jí)數(shù)為 layer_count
函數(shù):
dis(point1, point2) // 兩點(diǎn)(經(jīng)緯度)間距
lon2dis(lon) // 經(jīng)度差轉(zhuǎn)距離
lat2dis(lat) // 緯度差轉(zhuǎn)距離
dis2lon(dis) // 距離轉(zhuǎn)經(jīng)度差
dis2lat(dis) // 距離轉(zhuǎn)緯度差
數(shù)據(jù)結(jié)構(gòu):
point_layer {
point // 點(diǎn)的原始信息
index_list // 點(diǎn)的層級(jí)列表,層級(jí)由大到小降序排列 - [01, 22, 11]
}
index {
x // 某一層級(jí)內(nèi)的 橫坐標(biāo)
y // 某一層級(jí)內(nèi)的 縱坐標(biāo)
}
算法步驟 (偽代碼)
- 遍歷
list, 得到覆蓋所有點(diǎn)的最小邊界(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
此邊界應(yīng)適當(dāng)擴(kuò)大.
點(diǎn)過少或者區(qū)域過小時(shí)以大數(shù)值擴(kuò)大邊界,點(diǎn)多時(shí)則以小數(shù)值擴(kuò)大邊界:
lon1 = lon1 - offset
lat1 = lat1 - offset
lon2 = lon2 + offset
lat2 = lat2 + offset
- 確定
area_length及 區(qū)域邊界坐標(biāo) (左上角, 右下角)
x = lat2dis(lat2 - lat1)
y = lon2dis(lon2 - lon1)
area_length = x > y ? x : y
- 根據(jù)
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)
- 根據(jù)以上求出的各值, 遍歷 list 逐個(gè)確定每個(gè)點(diǎn)所在的單元格編號(hào).
編號(hào)規(guī)則可按從左到右, 從下到上順序等,這里按網(wǎng)格二維坐標(biāo)編碼:
for (point in list); do
lon_delta = point.lon - lon1 // 距左上角經(jīng)度
lat_delta = point.lat - lat1 // 距左上角緯度
nx = lon_delta / grid_lon // 整除取整,得到距左下角x軸格子數(shù)
ny = lat_delta / grid_lat // 整除取整,得到距左下角y軸格子數(shù)
// 按層級(jí)為每個(gè)點(diǎn)做標(biāo)記,從最小層級(jí)開始遍歷
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 // 取余得本層級(jí)內(nèi)的x坐標(biāo)
idx.y = idx_y % DIVIDER // 取余得本層級(jí)內(nèi)的y坐標(biāo)
pl.index_list.add(idx)
idx_x = idx.x / DIVIDER // 取除為取得上個(gè)層級(jí)坐標(biāo)做準(zhǔn)備
idx_y = idx.y / DIVIDER // 取除為取得上個(gè)層級(jí)坐標(biāo)做準(zhǔn)備
done
pl_list.add(pl)
done
實(shí)現(xiàn)
下面開始方案落地. 雖然寫的是 Android 程序, 但下面其實(shí)是純 java 代碼.
先定義一個(gè)標(biāo)記抽象類(接口) IMarker:
public interface IMarker {
double getLatitude();
double getLongitude();
}
定義為接口便于和具體的地圖解耦. 因此這套算法即可以用于百度地圖, 也可以用于高德, 騰訊等地圖. 只需要繼承相應(yīng)地圖的標(biāo)記類, 然后再 implement 這個(gè)接口, 就可以應(yīng)用這套算法了.
然后是最難寫的, 節(jié)點(diǎn)樹的數(shù)據(jù)結(jié)構(gòu):
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<K, T> {
private HashMap<K, IndexTree<K, T>> children;
private IndexTree<K, T> 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<K, T> parent) {
this.parent = parent;
}
public IndexTree<K, T> putChild(K index, T data) {
if (index == null) {
throw new IllegalArgumentException("null index is not acceptable");
}
IndexTree<K, T> 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<K> 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<K, T> 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<K, T> node = parent.getChild(idx);
if (node == null) {
node = parent.putChild(idx, null);
}
parent = node;
}
}
}
return true;
}
public IndexTree<K, T> getParent() {
return parent;
}
public IndexTree<K, T> getRoot() {
IndexTree<K, T> node = this;
while (node.parent != null) {
node = node.parent;
}
return node;
}
public IndexTree<K, T> getChild(K index) {
if (children == null) {
return null;
} else {
return children.get(index);
}
}
public IndexTree<K, T> getNodeByIndexList(List<K> 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<K, T> 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<T> getChildDataList() {
if (children == null) {
return null;
} else {
ArrayList<T> list = new ArrayList<>(children.size());
synchronized (mLock) {
Iterator<IndexTree<K, T>> 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<IndexTree<K, T>> iterateChild() {
if (children == null) {
return null;
} else {
return children.values().iterator();
}
}
public List<IndexTree<K, T>> getNodeListByLevel(int level) {
LinkedList<IndexTree<K, T>> ret = new LinkedList<>();
if (level <= 1) {
ret.add(this);
return ret;
} else if (children == null || children.size() == 0) {
return null;
} else {
synchronized (mLock) {
Iterator<IndexTree<K, T>> it = children.values().iterator();
while (it.hasNext()) {
List<IndexTree<K, T>> 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());
}
}
此容器的各類查詢 (取點(diǎn), 取列表, 取數(shù)量) 基本都由遞歸實(shí)現(xiàn), 基本就是為了實(shí)現(xiàn)上面?zhèn)未a邏輯而設(shè)計(jì)的樹型結(jié)構(gòu).
水平實(shí)在有限, 對(duì)自己寫出的這個(gè)泛型容器比較不滿意: 基本就只能在這個(gè)場(chǎng)景下專用. 并且封裝也不甚徹底, 很多邏輯本應(yīng)在此實(shí)現(xiàn), 但都放在了下面的 MarkerCluster 類中去實(shí)現(xiàn)了.
MarkerCluster 類似一個(gè) manager, 即使用上面兩個(gè)基礎(chǔ)類 IMarker 及 IndexTree, 來實(shí)現(xiàn)最終的業(yè)務(wù)邏輯:
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;
// 單元格可允許的最小邊長(zhǎng)
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<? extends IMarker> list;
private IndexTree<Index, MarkerInfo> 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<? extends IMarker> 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> index_list = getIndexByLatLon(m.getLatitude(), m.getLongitude());
IndexTree<Index, MarkerInfo> 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<Index> getIndexByLatLon(double lat, double lon) {
ArrayList<Index> 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<MarkerInfo> getMarkerListByLevel(int level) {
List<IndexTree<Index, MarkerInfo>> nodeList = index_tree.getNodeListByLevel(level);
if (nodeList != null && nodeList.size() != 0) {
ArrayList<MarkerInfo> list = new ArrayList<>(nodeList.size());
for (IndexTree<Index, MarkerInfo> n : nodeList) {
list.add(n.getData());
}
return list;
} else {
return null;
}
}
public List<MarkerInfo> 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, MarkerInfo> 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<IndexTree<Index, MarkerInfo>> it = index_tree.iterateChild();
while (it != null && it.hasNext()) {
IndexTree<Index, MarkerInfo> 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<IMarker> getEndPointDataList(MarkerInfo marker) {
List<IMarker> list = new ArrayList<>();
return getEndPointDataList(marker, list);
}
private List<IMarker> getEndPointDataList(MarkerInfo marker, List<IMarker> 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<Index, MarkerInfo> node = index_tree.getNodeByIndexList(marker.getIndexList());
List<MarkerInfo> childList = node.getChildDataList();
for (MarkerInfo m : childList) {
getEndPointDataList(m, list);
}
return list;
}
}
// ===========================================
// about index list
public static List<Index> getCommonIndexList(List<Index> index1, List<Index> 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<Index> 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<Index> list1, List<Index> 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<Index> list1, List<Index> 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> index_comparator = new Comparator<Index>() {
@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<Index> 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<IMarker> marker_list;
List<Index> index_list;
int marker_count;
public MarkerInfo(IMarker marker, List<Index> 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<IMarker> getMarkerList() {
return marker_list;
}
public boolean isMarkerListEmpty() {
return marker_list != null && marker_list.size() != 0;
}
public int getMarkerCount() {
return marker_count;
}
public List<Index> getIndexList() {
return index_list;
}
public String getIndexListString() {
return indexList2string(index_list);
}
@Override
public String toString() {
return getIndexListString() + getMarkerCount();
}
}
}
后記
該模塊與具體地圖完全解耦, 百度, 高德, 騰訊 地圖都能用.
不說效率如何, 起碼最終功能是實(shí)現(xiàn)了. 但算法實(shí)現(xiàn)水平確實(shí)弱了點(diǎn), 很多地方寫的不滿意.
可優(yōu)化的東西也很多, 比如: 目前遞歸等分是按正方形進(jìn)行的, 如果給出的數(shù)據(jù)點(diǎn)的列表分布趨于正方形, 則該算法效率尚可; 如果數(shù)據(jù)點(diǎn)列表分布在一個(gè)窄帶內(nèi), 則有很大優(yōu)化余地; 如果數(shù)據(jù)點(diǎn)列表在較大范圍內(nèi)較稀疏, 則效率很差.
這套東西運(yùn)行一年倒也沒出什么錯(cuò)誤, 后續(xù)就是新需求趕新需求, 也就沒心思去優(yōu)化這東西了. 各位大牛輕噴~.
