Алгоритм кластеризации для картографического приложения
-
09-06-2019 - |
Вопрос
Я изучаю точки кластеризации на карте (широта / долгота).Есть ли какие-либо рекомендации относительно подходящего алгоритма, который был бы быстрым и масштабируемым?
Более конкретно, у меня есть ряд координат широты / долготы и окно просмотра карты.Я пытаюсь сгруппировать точки, расположенные близко друг к другу, чтобы удалить беспорядок.
У меня уже есть решение этой проблемы (смотрите здесь), только мне интересно, существует ли какой-либо формальный алгоритм, который эффективно решает проблему.
Решение
Для приложения virtual earth я использовал описанную кластеризацию здесь.Он молниеносен и легко расширяем.
Другие советы
Взломы Google Maps имеет хак, "Взлом 69.Кластеризация маркеров при высоком уровне масштабирования ", на этом.
Кроме того, смотрите Википедия об алгоритмах кластеризации.
Вы могли бы посмотреть на индексацию всех ваших точек с помощью Квадтильный составьте схему, а затем, основываясь на масштабе, продвигайтесь дальше по квадратичным разделениям.Тогда все точки, расположенные аналогичным образом, будут находиться рядом друг с другом в вашем индексе, что позволит эффективно выполнить кластеризацию.
Квадратичные таблицы являются примером Коды Мортона, и есть пример python, связанный с этой статьей в Википедии, который может помочь.
Я просмотрел различные библиотеки и нашел их настолько сложными, что не мог понять ни слова, поэтому решил создать свой собственный алгоритм кластеризации
Вот мой код на Java
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);
}
// Это вычисляет расстояние в пикселях между точками наибольшей длины при определенном уровне масштабирования
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.Список массивов с широкими точками повторяется до длины .2.внутренний цикл копия того же arraylist повторяется с позиции i + 1, т.е. оставляя индекс верхнего цикла 3.0-й элемент берется за центр центроида, а все остальные точки сравниваются, если расстояние между ними в пикселях намного меньше, добавьте его в кластер 4.удалите все элементы из верхнего списка массивов и скопируйте 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