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