algorithm - mineria - Algoritmo de agrupamiento para la aplicación de mapeo

ejemplo algoritmo cure

Question

Estoy buscando puntos de agrupación en un mapa (lat / longs). ¿Hay alguna recomendación sobre un algoritmo adecuado que sea rápido y escalable?

@Gilligan: Sí, tengo una serie de lat / lngs y una ventana gráfica del mapa. Estoy tratando de agrupar los puntos que están muy juntos para eliminar el desorden.

Ya tengo una solución al problema ( ver aquí ), solo me pregunto si existe algún algoritmo formal que resuelva el problema de manera eficiente.

Answer 1

Google Maps Hacks tiene un truco, "Hack 69. Cluster Markers at High Zoom Levels" , sobre eso.

Además, vea Wikipedia sobre algoritmos de agrupamiento .

Answer 2

Podrías mirar la indexación de todos tus puntos usando un esquema QuadTile , y luego basándote en la escala más abajo en los cuádruples splits que vayas. Todos los puntos ubicados de forma similar estarán cerca el uno del otro en su índice, permitiendo que la agrupación se realice de manera eficiente.

QuadTiles es un ejemplo de Morton Codes , y hay un ejemplo de pitón vinculado a ese artículo de wikipedia que puede ayudar.

Answer 3

Miré varias bibliotecas y las encontré tan complejas que no pude entender una palabra, así que decidí crear 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íxel entre los puntos largos del cable de remolque a 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 clusters 1. ArrayList of lat long points se itera a la longitud. 2. bucle interno una copia del mismo arraylist se itera desde la posición i + 1, es decir, dejando el índice del bucle superior 3. El 0 ° elemento se toma como el centro del centroide y todos los demás puntos se comparan si su distancia de píxeles es muy baja. clúster 4. elimine todos los elementos de la lista de matrices superior y copie la lista de matrices que ha formado la agrupación 5 reinicie el proceso reiniciando el índice desde 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

Answer 4

Para una aplicación de tierra virtual, he usado la agrupación descrita aquí . Es rapidísimo y fácilmente extensible.