<p>I'm looking into clustering points on a map (latitude/longitude). Are there any recommendations as to a suitable algorithm that is fast and scalable?</p>

<p>More specifically, I have a series of latitude/longitude coordinates and a map viewport. I'm trying to cluster the points that are close together in order to remove clutter.</p>

<p>I already have a solution to the problem (<a href="http://bouldr.net" rel="noreferrer">see here</a>), only I am wondering if there is any formal algorithm that solves the problem efficiently.</p>

[{'answer_id': 73998, 'author': 'Paul Reiners', 'author_id': 7648, 'author_profile': 'https://Stackoverflow.com/users/7648', 'pm_score': 3, 'selected': False, 'text': '<p><em>Google Maps Hacks</em> has a hack, <a href="https://flylib.com/books/en/2.367.1/hack_69_cluster_markers_at_high_zoom_levels.html" rel="nofollow noreferrer">&quot;Hack 69. Cluster Markers at High Zoom Levels&quot;</a>, on that.</p>\n<p>Also, see <a href="http://en.wikipedia.org/wiki/Data_clustering" rel="nofollow noreferrer">Wikipedia on clustering algorithms</a>.</p>\n'}, {'answer_id': 125455, 'author': 'Geri Langlois', 'author_id': 4888, 'author_profile': 'https://Stackoverflow.com/users/4888', 'pm_score': 4, 'selected': True, 'text': '<p>For a virtual earth application I\'ve used the clustering described \n<a href="https://web.archive.org/web/20130410092213/http://www.soulsolutions.com.au/Articles/ClusteringVirtualEarthPart1.aspx" rel="nofollow noreferrer">here</a>. It\'s lightning fast and easily extensible.</p>\n'}, {'answer_id': 561344, 'author': 'David Dean', 'author_id': 67829, 'author_profile': 'https://Stackoverflow.com/users/67829', 'pm_score': 2, 'selected': False, 'text': '<p>You could look at indexing all your points using a <a href="http://wiki.openstreetmap.org/wiki/QuadTiles" rel="nofollow noreferrer">QuadTile</a> scheme, and then based upon the scale the further down the quad-splits you go. All similarly located points will then be near each other in your index, allowing the clustering to happen efficiently.</p>\n\n<p>QuadTiles are an example of <a href="http://en.wikipedia.org/wiki/Morton_number_(number_theory)" rel="nofollow noreferrer">Morton Codes</a>, and there is a python example linked from that wikipedia article that may help.</p>\n'}, {'answer_id': 18633159, 'author': 'user1530779', 'author_id': 1530779, 'author_profile': 'https://Stackoverflow.com/users/1530779', 'pm_score': 1, 'selected': False, 'text': '<p>I looked at various libraries and found them so complex couldn\'t understand a word so I decided to make my own clustering algorithm</p>\n\n<p>Here goes my code in Java</p>\n\n<pre><code>static int OFFSET = 268435456;\n    static double RADIUS = 85445659.4471;\n    static double pi = 3.1444;\n\npublic static double lonToX(double lon) {\n        return Math.round(OFFSET + RADIUS * lon * pi / 180);\n    }\n\n    public static double latToY(double lat) {\n        return Math.round(OFFSET\n                - RADIUS\n                * Math.log((1 + Math.sin(lat * pi / 180))\n                        / (1 - Math.sin(lat * pi / 180))) / 2);\n    }\n</code></pre>\n\n<p>// This calculates the pixel distance between tow lat long points at a particular zoom level </p>\n\n<pre><code>    public static int pixelDistance(double lat1, double lon1, double lat2,\n            double lon2, int zoom) {\n        double x1 = lonToX(lon1);\n        double y1 = latToY(lat1);\n\n        double x2 = lonToX(lon2);\n        double y2 = latToY(lat2);\n\n        return (int) (Math\n                .sqrt(Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2))) &gt;&gt; (21 - zoom);\n    }\n</code></pre>\n\n<p>// The main function which actually calculates the clusters\n1. ArrayList of lat long points is iterated to length .\n2. inner loop a copy of the same arraylist is iterated from i+1 position ie leaving the top loop\'s index\n3. 0th element is taken as the centre of centroid and all other points are compared if their pixel distance is very less add it into cluster\n4. remove all  elements from top arraylist and copy arraylist which have formed cluster\n5 restart the process by reinitializing the index from 0;\n6 if the centroid selected has no clusters then that element is not deleted</p>\n\n<pre><code>static ArrayList&lt;Cluster&gt; cluster(ArrayList&lt;Marker&gt; markers, int zoom) {\n\n        ArrayList&lt;Cluster&gt; clusterList = new ArrayList&lt;Cluster&gt;();\n\n        ArrayList&lt;Marker&gt; originalListCopy = new ArrayList&lt;Marker&gt;();\n\n        for (Marker marker : markers) {\n            originalListCopy.add(marker);\n        }\n\n        /* Loop until all markers have been compared. */\n        for (int i = 0; i &lt; originalListCopy.size();) {\n\n            /* Compare against all markers which are left. */\n\n            ArrayList&lt;Marker&gt; markerList = new ArrayList&lt;Marker&gt;();\n            for (int j = i + 1; j &lt; markers.size();) {\n                int pixelDistance = pixelDistance(markers.get(i).getLatitude(),\n                        markers.get(i).getLongitude(), markers.get(j)\n                                .getLatitude(), markers.get(j).getLongitude(),\n                        zoom);\n\n                if (pixelDistance &lt; 40) {\n\n                    markerList.add(markers.get(i));\n                    markerList.add(markers.get(j));\n\n                    markers.remove(j);\n\n                    originalListCopy.remove(j);\n                    j = i + 1;\n                } else {\n                    j++;\n                }\n\n            }\n\n            if (markerList.size() &gt; 0) {\n                Cluster cluster = new Cluster(clusterList.size(), markerList,\n                        markerList.size() + 1, originalListCopy.get(i)\n                                .getLatitude(), originalListCopy.get(i)\n                                .getLongitude());\n                clusterList.add(cluster);\n                originalListCopy.remove(i);\n                markers.remove(i);\n                i = 0;\n\n            } else {\n                i++;\n            }\n\n            /* If a marker has been added to cluster, add also the one */\n            /* we were comparing to and remove the original from array. */\n\n        }\n        return clusterList;\n    }\n\nJust pass in your array list here containing latitude and longitude\n\nthen to display clusters\nhere goes the function\n\n\n@Override\n    public void onTaskCompleted(ArrayList&lt;FlatDetails&gt; flatDetailsList) {\n\n        LatLngBounds.Builder builder = new LatLngBounds.Builder();\n\n        originalListCopy = new ArrayList&lt;FlatDetails&gt;();\n        ArrayList&lt;Marker&gt; markersList = new ArrayList&lt;Marker&gt;();\n        for (FlatDetails detailList : flatDetailsList) {\n\n            markersList.add(new Marker(detailList.getLatitude(), detailList\n                    .getLongitude(), detailList.getApartmentTypeString()));\n\n            originalListCopy.add(detailList);\n\n            builder.include(new LatLng(detailList.getLatitude(), detailList\n                    .getLongitude()));\n\n        }\n\n        LatLngBounds bounds = builder.build();\n        int padding = 0; // offset from edges of the map in pixels\n        CameraUpdate cu = CameraUpdateFactory.newLatLngBounds(bounds, padding);\n\n        googleMap.moveCamera(cu);\n\n        ArrayList&lt;Cluster&gt; clusterList = Utils.cluster(markersList,\n                (int) googleMap.getCameraPosition().zoom);\n\n        // Removes all markers, overlays, and polylines from the map.\n        googleMap.clear();\n\n        // Zoom in, animating the camera.\n        googleMap.animateCamera(CameraUpdateFactory.zoomTo(previousZoomLevel),\n                2000, null);\n\n        CircleOptions circleOptions = new CircleOptions().center(point) //\n                // setcenter\n                .radius(3000) // set radius in meters\n                .fillColor(Color.TRANSPARENT) // default\n                .strokeColor(Color.BLUE).strokeWidth(5);\n\n        googleMap.addCircle(circleOptions);\n\n        for (Marker detail : markersList) {\n\n            if (detail.getBhkTypeString().equalsIgnoreCase("1 BHK")) {\n                googleMap.addMarker(new MarkerOptions()\n                        .position(\n                                new LatLng(detail.getLatitude(), detail\n                                        .getLongitude()))\n                        .snippet(String.valueOf(""))\n                        .title("Flat" + flatDetailsList.indexOf(detail))\n                        .icon(BitmapDescriptorFactory\n                                .fromResource(R.drawable.bhk1)));\n            } else if (detail.getBhkTypeString().equalsIgnoreCase("2 BHK")) {\n                googleMap.addMarker(new MarkerOptions()\n                        .position(\n                                new LatLng(detail.getLatitude(), detail\n                                        .getLongitude()))\n                        .snippet(String.valueOf(""))\n                        .title("Flat" + flatDetailsList.indexOf(detail))\n                        .icon(BitmapDescriptorFactory\n                                .fromResource(R.drawable.bhk_2)));\n\n            }\n\n            else if (detail.getBhkTypeString().equalsIgnoreCase("3 BHK")) {\n                googleMap.addMarker(new MarkerOptions()\n                        .position(\n                                new LatLng(detail.getLatitude(), detail\n                                        .getLongitude()))\n                        .snippet(String.valueOf(""))\n                        .title("Flat" + flatDetailsList.indexOf(detail))\n                        .icon(BitmapDescriptorFactory\n                                .fromResource(R.drawable.bhk_3)));\n\n            } else if (detail.getBhkTypeString().equalsIgnoreCase("2.5 BHK")) {\n                googleMap.addMarker(new MarkerOptions()\n                        .position(\n                                new LatLng(detail.getLatitude(), detail\n                                        .getLongitude()))\n                        .snippet(String.valueOf(""))\n                        .title("Flat" + flatDetailsList.indexOf(detail))\n                        .icon(BitmapDescriptorFactory\n                                .fromResource(R.drawable.bhk2)));\n\n            } else if (detail.getBhkTypeString().equalsIgnoreCase("4 BHK")) {\n                googleMap.addMarker(new MarkerOptions()\n                        .position(\n                                new LatLng(detail.getLatitude(), detail\n                                        .getLongitude()))\n                        .snippet(String.valueOf(""))\n                        .title("Flat" + flatDetailsList.indexOf(detail))\n                        .icon(BitmapDescriptorFactory\n                                .fromResource(R.drawable.bhk_4)));\n\n            } else if (detail.getBhkTypeString().equalsIgnoreCase("5 BHK")) {\n                googleMap.addMarker(new MarkerOptions()\n                        .position(\n                                new LatLng(detail.getLatitude(), detail\n                                        .getLongitude()))\n                        .snippet(String.valueOf(""))\n                        .title("Flat" + flatDetailsList.indexOf(detail))\n                        .icon(BitmapDescriptorFactory\n                                .fromResource(R.drawable.bhk5)));\n\n            } else if (detail.getBhkTypeString().equalsIgnoreCase("5+ BHK")) {\n                googleMap.addMarker(new MarkerOptions()\n                        .position(\n                                new LatLng(detail.getLatitude(), detail\n                                        .getLongitude()))\n                        .snippet(String.valueOf(""))\n                        .title("Flat" + flatDetailsList.indexOf(detail))\n                        .icon(BitmapDescriptorFactory\n                                .fromResource(R.drawable.bhk_5)));\n\n            }\n\n            else if (detail.getBhkTypeString().equalsIgnoreCase("2 BHK")) {\n                googleMap.addMarker(new MarkerOptions()\n                        .position(\n                                new LatLng(detail.getLatitude(), detail\n                                        .getLongitude()))\n                        .snippet(String.valueOf(""))\n                        .title("Flat" + flatDetailsList.indexOf(detail))\n                        .icon(BitmapDescriptorFactory\n                                .fromResource(R.drawable.bhk_2)));\n\n            }\n        }\n\n        for (Cluster cluster : clusterList) {\n\n            BitmapFactory.Options options = new BitmapFactory.Options();\n            options.inMutable = true;\n            options.inPurgeable = true;\n            Bitmap bitmap = BitmapFactory.decodeResource(getResources(),\n                    R.drawable.cluster_marker, options);\n\n            Canvas canvas = new Canvas(bitmap);\n\n            Paint paint = new Paint();\n            paint.setColor(getResources().getColor(R.color.white));\n            paint.setTextSize(30);\n\n            canvas.drawText(String.valueOf(cluster.getMarkerList().size()), 10,\n                    40, paint);\n\n            googleMap.addMarker(new MarkerOptions()\n                    .position(\n                            new LatLng(cluster.getClusterLatitude(), cluster\n                                    .getClusterLongitude()))\n                    .snippet(String.valueOf(cluster.getMarkerList().size()))\n                    .title("Cluster")\n                    .icon(BitmapDescriptorFactory.fromBitmap(bitmap)));\n\n        }\n\n    }\n\n\n\n\nANY QUESTIONS OR DOUBTS PLEASE ASK WILL CLEAR THEM ALL ...........THANKS\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/73927', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/12037/']