Algoritmo de clúster para aplicaciones de mapeo
Estoy buscando puntos de agrupación en un mapa (latitud/longitud). ¿Hay recomendaciones en cuanto a un algoritmo adecuado que sea rápido y escalable?
Más específicamente, tengo una serie de coordenadas de latitud/longitud y una ventana de mapa. Estoy tratando de agrupar los puntos que están juntos para eliminar el desorden.
Ya tengo una solución al problema ( ver aquí ), solo me pregunto si hay algún algoritmo formal que resuelva el problema de manera eficiente.
Google Maps Hacks tiene un hacke, "Hack 69. Marcadores de clústeres a altos niveles de zoom" , en eso.
Además, vea Wikipedia en algoritmos de agrupamiento .
Podría ver la indexación de todos sus puntos usando un esquema A Quadtile , y luego se basa en la escala más abajo en el quad-Splits que va. Todos los puntos ubicados de manera similar se encontrarán entre sí en su índice, lo que permitirá que el agrupamiento suceda de manera eficiente.
Los quadtiles son un ejemplo de códigos de morton , y hay un python vinculado desde ese artículo de Wikipedia que puede ayudar.
Miré varias bibliotecas y las encontré tan complejo, no podía entender una palabra, así que decidí hacer mi propio algoritmo de agrupamiento.
Aquí va mi código en 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);
}
// Esto calcula la distancia de píxeles entre los puntos largos de remolque en un nivel de zoom particular
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);
}
// La función principal que realmente calcula los clústeres 1. La lista de arayos de los puntos Lat largos está iterada a la longitud. 2. Bucle interno Una copia de la misma lista de arancelistas se itera a partir de la posición I + 1, es decir, dejando el índice de la bucle superior 3. El elemento 0 se toma como el centro de centroide y todos los demás puntos se comparan si su distancia de píxeles es muy menos. Cluster 4. Retire todos los elementos de la lista de array superior y la Lista de Array de copia que haya formado el clúster 5 Reinicie el proceso reinicializando el índice de 0; 6 Si el centroide seleccionado no tiene clústeres, entonces ese elemento no se elimina
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