Algoritmo de agrupamiento para aplicaciones de mapeo

Question

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

Más específicamente, tengo una serie de coordenadas de latitud/longitud y una ventana gráfica de mapa.Estoy tratando de agrupar los puntos que están muy juntos para eliminar el desorden.

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

Answer 1

Para una aplicación de Tierra virtual, he utilizado la agrupación descrita.aquí.Es increíblemente rápido y fácilmente extensible.

Answer 2

Trucos de Google Maps tiene un truco, "Hackear 69.Marcadores de grupo en niveles de zoom altos", en ese.

Ver también Wikipedia sobre algoritmos de agrupamiento.

Answer 3

Podrías considerar indexar todos tus puntos usando un Cuádruple esquema, y ​​luego, según la escala, cuanto más abajo vayas en las divisiones cuádruples.Todos los puntos ubicados de manera similar estarán entonces cerca unos de otros en su índice, lo que permitirá que la agrupación se realice de manera eficiente.

QuadTiles son un ejemplo de Códigos Morton, y hay un ejemplo de Python vinculado desde ese artículo de Wikipedia que puede ayudar.

Answer 4

Miré varias bibliotecas y las encontré tan complejas que no podía entender una palabra, así que decidí crear mi propio algoritmo de agrupación.

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 en 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 grupos 1.ArrayList de puntos lat long se itera hasta length .2.bucle interno Una copia de la misma ArrayList se itera desde la posición i+1, es decir, dejando el índice 3 de la bucle superior.El elemento 0 se toma como el centro del centroide y todos los demás puntos se comparan si su distancia de píxeles es muy infórmala al clúster 4.Elimine todos los elementos de Top ArrayList y Copy ArrayList que hayan formado el clúster 5 reinicie el proceso reinicializando el índice de 0;6 si el centroide seleccionado no tiene grupos, 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