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