1f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin/* 2f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * Copyright (C) 2010 The Android Open Source Project 3f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * 4f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * Licensed under the Apache License, Version 2.0 (the "License"); 5f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * you may not use this file except in compliance with the License. 6f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * You may obtain a copy of the License at 7f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * 8f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * http://www.apache.org/licenses/LICENSE-2.0 9f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * 10f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * Unless required by applicable law or agreed to in writing, software 11f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * distributed under the License is distributed on an "AS IS" BASIS, 12f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * See the License for the specific language governing permissions and 14f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * limitations under the License. 15f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin */ 16f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 17f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linpackage com.android.gallery3d.data; 18f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 19f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport android.content.Context; 20598e242e3cb97f61a1eaf71d21459e45a5b2db42Ray Chenimport android.os.Handler; 21598e242e3cb97f61a1eaf71d21459e45a5b2db42Ray Chenimport android.os.Looper; 22f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport android.widget.Toast; 23f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 242b3ee0ea07246b859a5b75d8a6102a7cce7ec838Owen Linimport com.android.gallery3d.R; 252b3ee0ea07246b859a5b75d8a6102a7cce7ec838Owen Linimport com.android.gallery3d.util.GalleryUtils; 262b3ee0ea07246b859a5b75d8a6102a7cce7ec838Owen Linimport com.android.gallery3d.util.ReverseGeocoder; 272b3ee0ea07246b859a5b75d8a6102a7cce7ec838Owen Lin 28f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport java.util.ArrayList; 29f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 30f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linclass LocationClustering extends Clustering { 317817979db0c52ffeacb951625b1e821eba303285Ahbong Chang @SuppressWarnings("unused") 32f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final String TAG = "LocationClustering"; 33f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 34f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int MIN_GROUPS = 1; 35f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int MAX_GROUPS = 20; 36f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int MAX_ITERATIONS = 30; 37f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 38f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // If the total distance change is less than this ratio, stop iterating. 39f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final float STOP_CHANGE_RATIO = 0.01f; 40f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private Context mContext; 41f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private ArrayList<ArrayList<SmallItem>> mClusters; 42f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private ArrayList<String> mNames; 43f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private String mNoLocationString; 44598e242e3cb97f61a1eaf71d21459e45a5b2db42Ray Chen private Handler mHandler; 45f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 46f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static class Point { 47f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public Point(double lat, double lng) { 48f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin latRad = Math.toRadians(lat); 49f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin lngRad = Math.toRadians(lng); 50f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 51f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public Point() {} 52f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public double latRad, lngRad; 53f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 54f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 55f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static class SmallItem { 56f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Path path; 57f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin double lat, lng; 58f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 59f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 60f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public LocationClustering(Context context) { 61f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mContext = context; 62f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mNoLocationString = mContext.getResources().getString(R.string.no_location); 63598e242e3cb97f61a1eaf71d21459e45a5b2db42Ray Chen mHandler = new Handler(Looper.getMainLooper()); 64f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 65f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 66f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin @Override 67f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public void run(MediaSet baseSet) { 68f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin final int total = baseSet.getTotalMediaItemCount(); 69f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin final SmallItem[] buf = new SmallItem[total]; 70f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Separate items to two sets: with or without lat-long. 71f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin final double[] latLong = new double[2]; 72f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin baseSet.enumerateTotalMediaItems(new MediaSet.ItemConsumer() { 737817979db0c52ffeacb951625b1e821eba303285Ahbong Chang @Override 74f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public void consume(int index, MediaItem item) { 75f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (index < 0 || index >= total) return; 76f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin SmallItem s = new SmallItem(); 77f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin s.path = item.getPath(); 78f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin item.getLatLong(latLong); 79f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin s.lat = latLong[0]; 80f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin s.lng = latLong[1]; 81f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin buf[index] = s; 82f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 83f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin }); 84f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 85f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin final ArrayList<SmallItem> withLatLong = new ArrayList<SmallItem>(); 86f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin final ArrayList<SmallItem> withoutLatLong = new ArrayList<SmallItem>(); 87f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin final ArrayList<Point> points = new ArrayList<Point>(); 88f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < total; i++) { 89f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin SmallItem s = buf[i]; 90f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (s == null) continue; 91f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (GalleryUtils.isValidLocation(s.lat, s.lng)) { 92f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin withLatLong.add(s); 93f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin points.add(new Point(s.lat, s.lng)); 94f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } else { 95f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin withoutLatLong.add(s); 96f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 97f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 98f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 99f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin ArrayList<ArrayList<SmallItem>> clusters = new ArrayList<ArrayList<SmallItem>>(); 100f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 101f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int m = withLatLong.size(); 102f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (m > 0) { 103f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // cluster the items with lat-long 104f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Point[] pointsArray = new Point[m]; 105f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin pointsArray = points.toArray(pointsArray); 106f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int[] bestK = new int[1]; 107f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int[] index = kMeans(pointsArray, bestK); 108f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 109f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < bestK[0]; i++) { 110f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin clusters.add(new ArrayList<SmallItem>()); 111f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 112f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 113f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < m; i++) { 114f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin clusters.get(index[i]).add(withLatLong.get(i)); 115f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 116f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 117f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 118f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin ReverseGeocoder geocoder = new ReverseGeocoder(mContext); 119f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mNames = new ArrayList<String>(); 120f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin boolean hasUnresolvedAddress = false; 121f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mClusters = new ArrayList<ArrayList<SmallItem>>(); 122f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (ArrayList<SmallItem> cluster : clusters) { 123f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin String name = generateName(cluster, geocoder); 124f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (name != null) { 125f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mNames.add(name); 126f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mClusters.add(cluster); 127f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } else { 128f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // move cluster-i to no location cluster 129f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin withoutLatLong.addAll(cluster); 130f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin hasUnresolvedAddress = true; 131f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 132f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 133f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 134f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (withoutLatLong.size() > 0) { 135f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mNames.add(mNoLocationString); 136f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mClusters.add(withoutLatLong); 137f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 138f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 139f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (hasUnresolvedAddress) { 140598e242e3cb97f61a1eaf71d21459e45a5b2db42Ray Chen mHandler.post(new Runnable() { 1417817979db0c52ffeacb951625b1e821eba303285Ahbong Chang @Override 142598e242e3cb97f61a1eaf71d21459e45a5b2db42Ray Chen public void run() { 143598e242e3cb97f61a1eaf71d21459e45a5b2db42Ray Chen Toast.makeText(mContext, R.string.no_connectivity, 144598e242e3cb97f61a1eaf71d21459e45a5b2db42Ray Chen Toast.LENGTH_LONG).show(); 145598e242e3cb97f61a1eaf71d21459e45a5b2db42Ray Chen } 146598e242e3cb97f61a1eaf71d21459e45a5b2db42Ray Chen }); 147f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 148f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 149f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 150f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static String generateName(ArrayList<SmallItem> items, 151f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin ReverseGeocoder geocoder) { 152f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin ReverseGeocoder.SetLatLong set = new ReverseGeocoder.SetLatLong(); 153f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 154f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int n = items.size(); 155f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < n; i++) { 156f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin SmallItem item = items.get(i); 157f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin double itemLatitude = item.lat; 158f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin double itemLongitude = item.lng; 159f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 160f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (set.mMinLatLatitude > itemLatitude) { 161f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin set.mMinLatLatitude = itemLatitude; 162f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin set.mMinLatLongitude = itemLongitude; 163f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 164f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (set.mMaxLatLatitude < itemLatitude) { 165f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin set.mMaxLatLatitude = itemLatitude; 166f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin set.mMaxLatLongitude = itemLongitude; 167f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 168f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (set.mMinLonLongitude > itemLongitude) { 169f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin set.mMinLonLatitude = itemLatitude; 170f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin set.mMinLonLongitude = itemLongitude; 171f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 172f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (set.mMaxLonLongitude < itemLongitude) { 173f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin set.mMaxLonLatitude = itemLatitude; 174f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin set.mMaxLonLongitude = itemLongitude; 175f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 176f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 177f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 178f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return geocoder.computeAddress(set); 179f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 180f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 181f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin @Override 182f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public int getNumberOfClusters() { 183f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return mClusters.size(); 184f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 185f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 186f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin @Override 187f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public ArrayList<Path> getCluster(int index) { 188f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin ArrayList<SmallItem> items = mClusters.get(index); 189f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin ArrayList<Path> result = new ArrayList<Path>(items.size()); 190f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0, n = items.size(); i < n; i++) { 191f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin result.add(items.get(i).path); 192f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 193f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return result; 194f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 195f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 196f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin @Override 197f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public String getClusterName(int index) { 198f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return mNames.get(index); 199f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 200f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 201f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Input: n points 202f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Output: the best k is stored in bestK[0], and the return value is the 203f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // an array which specifies the group that each point belongs (0 to k - 1). 204f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static int[] kMeans(Point points[], int[] bestK) { 205f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int n = points.length; 206f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 207f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // min and max number of groups wanted 208f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int minK = Math.min(n, MIN_GROUPS); 209f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int maxK = Math.min(n, MAX_GROUPS); 210f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 211f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Point[] center = new Point[maxK]; // center of each group. 212f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Point[] groupSum = new Point[maxK]; // sum of points in each group. 213f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int[] groupCount = new int[maxK]; // number of points in each group. 214f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int[] grouping = new int[n]; // The group assignment for each point. 215f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 216f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < maxK; i++) { 217f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin center[i] = new Point(); 218f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin groupSum[i] = new Point(); 219f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 220f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 221f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // The score we want to minimize is: 222f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // (sum of distance from each point to its group center) * sqrt(k). 223f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin float bestScore = Float.MAX_VALUE; 224f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // The best group assignment up to now. 225f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int[] bestGrouping = new int[n]; 226f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // The best K up to now. 227f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin bestK[0] = 1; 228f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 229f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin float lastDistance = 0; 230f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin float totalDistance = 0; 231f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 232f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int k = minK; k <= maxK; k++) { 233f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // step 1: (arbitrarily) pick k points as the initial centers. 234f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int delta = n / k; 235f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < k; i++) { 236f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Point p = points[i * delta]; 237f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin center[i].latRad = p.latRad; 238f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin center[i].lngRad = p.lngRad; 239f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 240f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 241f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int iter = 0; iter < MAX_ITERATIONS; iter++) { 242f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // step 2: assign each point to the nearest center. 243f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < k; i++) { 244f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin groupSum[i].latRad = 0; 245f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin groupSum[i].lngRad = 0; 246f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin groupCount[i] = 0; 247f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 248f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin totalDistance = 0; 249f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 250f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < n; i++) { 251f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Point p = points[i]; 252f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin float bestDistance = Float.MAX_VALUE; 253f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int bestIndex = 0; 254f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int j = 0; j < k; j++) { 255f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin float distance = (float) GalleryUtils.fastDistanceMeters( 256f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin p.latRad, p.lngRad, center[j].latRad, center[j].lngRad); 257f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // We may have small non-zero distance introduced by 258f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // floating point calculation, so zero out small 259f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // distances less than 1 meter. 260f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (distance < 1) { 261f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin distance = 0; 262f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 263f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (distance < bestDistance) { 264f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin bestDistance = distance; 265f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin bestIndex = j; 266f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 267f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 268f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin grouping[i] = bestIndex; 269f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin groupCount[bestIndex]++; 270f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin groupSum[bestIndex].latRad += p.latRad; 271f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin groupSum[bestIndex].lngRad += p.lngRad; 272f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin totalDistance += bestDistance; 273f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 274f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 275f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // step 3: calculate new centers 276f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < k; i++) { 277f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (groupCount[i] > 0) { 278f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin center[i].latRad = groupSum[i].latRad / groupCount[i]; 279f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin center[i].lngRad = groupSum[i].lngRad / groupCount[i]; 280f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 281f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 282f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 283f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (totalDistance == 0 || (Math.abs(lastDistance - totalDistance) 284f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin / totalDistance) < STOP_CHANGE_RATIO) { 285f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin break; 286f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 287f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin lastDistance = totalDistance; 288f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 289f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 290f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // step 4: remove empty groups and reassign group number 291f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int reassign[] = new int[k]; 292f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int realK = 0; 293f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < k; i++) { 294f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (groupCount[i] > 0) { 295f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin reassign[i] = realK++; 296f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 297f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 298f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 299f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // step 5: calculate the final score 3008a55d3ae7486b798e4c26eeb91993916145f3cefNeil Fuller float score = totalDistance * (float) Math.sqrt(realK); 301f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 302f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (score < bestScore) { 303f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin bestScore = score; 304f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin bestK[0] = realK; 305f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < n; i++) { 306f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin bestGrouping[i] = reassign[grouping[i]]; 307f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 308f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (score == 0) { 309f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin break; 310f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 311f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 312f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 313f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return bestGrouping; 314f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 315f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin} 316