summaryrefslogtreecommitdiffstats
path: root/src/com/android/gallery3d/data/LocationClustering.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/com/android/gallery3d/data/LocationClustering.java')
-rw-r--r--src/com/android/gallery3d/data/LocationClustering.java304
1 files changed, 304 insertions, 0 deletions
diff --git a/src/com/android/gallery3d/data/LocationClustering.java b/src/com/android/gallery3d/data/LocationClustering.java
new file mode 100644
index 000000000..3cb1399e5
--- /dev/null
+++ b/src/com/android/gallery3d/data/LocationClustering.java
@@ -0,0 +1,304 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.gallery3d.data;
+
+import com.android.gallery3d.R;
+import com.android.gallery3d.util.ReverseGeocoder;
+import com.android.gallery3d.util.GalleryUtils;
+
+import android.content.Context;
+import android.widget.Toast;
+
+import java.util.ArrayList;
+
+class LocationClustering extends Clustering {
+ private static final String TAG = "LocationClustering";
+
+ private static final int MIN_GROUPS = 1;
+ private static final int MAX_GROUPS = 20;
+ private static final int MAX_ITERATIONS = 30;
+
+ // If the total distance change is less than this ratio, stop iterating.
+ private static final float STOP_CHANGE_RATIO = 0.01f;
+ private Context mContext;
+ private ArrayList<ArrayList<SmallItem>> mClusters;
+ private ArrayList<String> mNames;
+ private String mNoLocationString;
+
+ private static class Point {
+ public Point(double lat, double lng) {
+ latRad = Math.toRadians(lat);
+ lngRad = Math.toRadians(lng);
+ }
+ public Point() {}
+ public double latRad, lngRad;
+ }
+
+ private static class SmallItem {
+ Path path;
+ double lat, lng;
+ }
+
+ public LocationClustering(Context context) {
+ mContext = context;
+ mNoLocationString = mContext.getResources().getString(R.string.no_location);
+ }
+
+ @Override
+ public void run(MediaSet baseSet) {
+ final int total = baseSet.getTotalMediaItemCount();
+ final SmallItem[] buf = new SmallItem[total];
+ // Separate items to two sets: with or without lat-long.
+ final double[] latLong = new double[2];
+ baseSet.enumerateTotalMediaItems(new MediaSet.ItemConsumer() {
+ public void consume(int index, MediaItem item) {
+ if (index < 0 || index >= total) return;
+ SmallItem s = new SmallItem();
+ s.path = item.getPath();
+ item.getLatLong(latLong);
+ s.lat = latLong[0];
+ s.lng = latLong[1];
+ buf[index] = s;
+ }
+ });
+
+ final ArrayList<SmallItem> withLatLong = new ArrayList<SmallItem>();
+ final ArrayList<SmallItem> withoutLatLong = new ArrayList<SmallItem>();
+ final ArrayList<Point> points = new ArrayList<Point>();
+ for (int i = 0; i < total; i++) {
+ SmallItem s = buf[i];
+ if (s == null) continue;
+ if (GalleryUtils.isValidLocation(s.lat, s.lng)) {
+ withLatLong.add(s);
+ points.add(new Point(s.lat, s.lng));
+ } else {
+ withoutLatLong.add(s);
+ }
+ }
+
+ ArrayList<ArrayList<SmallItem>> clusters = new ArrayList<ArrayList<SmallItem>>();
+
+ int m = withLatLong.size();
+ if (m > 0) {
+ // cluster the items with lat-long
+ Point[] pointsArray = new Point[m];
+ pointsArray = points.toArray(pointsArray);
+ int[] bestK = new int[1];
+ int[] index = kMeans(pointsArray, bestK);
+
+ for (int i = 0; i < bestK[0]; i++) {
+ clusters.add(new ArrayList<SmallItem>());
+ }
+
+ for (int i = 0; i < m; i++) {
+ clusters.get(index[i]).add(withLatLong.get(i));
+ }
+ }
+
+ ReverseGeocoder geocoder = new ReverseGeocoder(mContext);
+ mNames = new ArrayList<String>();
+ boolean hasUnresolvedAddress = false;
+ mClusters = new ArrayList<ArrayList<SmallItem>>();
+ for (ArrayList<SmallItem> cluster : clusters) {
+ String name = generateName(cluster, geocoder);
+ if (name != null) {
+ mNames.add(name);
+ mClusters.add(cluster);
+ } else {
+ // move cluster-i to no location cluster
+ withoutLatLong.addAll(cluster);
+ hasUnresolvedAddress = true;
+ }
+ }
+
+ if (withoutLatLong.size() > 0) {
+ mNames.add(mNoLocationString);
+ mClusters.add(withoutLatLong);
+ }
+
+ if (hasUnresolvedAddress) {
+ Toast.makeText(mContext, R.string.no_connectivity,
+ Toast.LENGTH_LONG).show();
+ }
+ }
+
+ private static String generateName(ArrayList<SmallItem> items,
+ ReverseGeocoder geocoder) {
+ ReverseGeocoder.SetLatLong set = new ReverseGeocoder.SetLatLong();
+
+ int n = items.size();
+ for (int i = 0; i < n; i++) {
+ SmallItem item = items.get(i);
+ double itemLatitude = item.lat;
+ double itemLongitude = item.lng;
+
+ if (set.mMinLatLatitude > itemLatitude) {
+ set.mMinLatLatitude = itemLatitude;
+ set.mMinLatLongitude = itemLongitude;
+ }
+ if (set.mMaxLatLatitude < itemLatitude) {
+ set.mMaxLatLatitude = itemLatitude;
+ set.mMaxLatLongitude = itemLongitude;
+ }
+ if (set.mMinLonLongitude > itemLongitude) {
+ set.mMinLonLatitude = itemLatitude;
+ set.mMinLonLongitude = itemLongitude;
+ }
+ if (set.mMaxLonLongitude < itemLongitude) {
+ set.mMaxLonLatitude = itemLatitude;
+ set.mMaxLonLongitude = itemLongitude;
+ }
+ }
+
+ return geocoder.computeAddress(set);
+ }
+
+ @Override
+ public int getNumberOfClusters() {
+ return mClusters.size();
+ }
+
+ @Override
+ public ArrayList<Path> getCluster(int index) {
+ ArrayList<SmallItem> items = mClusters.get(index);
+ ArrayList<Path> result = new ArrayList<Path>(items.size());
+ for (int i = 0, n = items.size(); i < n; i++) {
+ result.add(items.get(i).path);
+ }
+ return result;
+ }
+
+ @Override
+ public String getClusterName(int index) {
+ return mNames.get(index);
+ }
+
+ // Input: n points
+ // Output: the best k is stored in bestK[0], and the return value is the
+ // an array which specifies the group that each point belongs (0 to k - 1).
+ private static int[] kMeans(Point points[], int[] bestK) {
+ int n = points.length;
+
+ // min and max number of groups wanted
+ int minK = Math.min(n, MIN_GROUPS);
+ int maxK = Math.min(n, MAX_GROUPS);
+
+ Point[] center = new Point[maxK]; // center of each group.
+ Point[] groupSum = new Point[maxK]; // sum of points in each group.
+ int[] groupCount = new int[maxK]; // number of points in each group.
+ int[] grouping = new int[n]; // The group assignment for each point.
+
+ for (int i = 0; i < maxK; i++) {
+ center[i] = new Point();
+ groupSum[i] = new Point();
+ }
+
+ // The score we want to minimize is:
+ // (sum of distance from each point to its group center) * sqrt(k).
+ float bestScore = Float.MAX_VALUE;
+ // The best group assignment up to now.
+ int[] bestGrouping = new int[n];
+ // The best K up to now.
+ bestK[0] = 1;
+
+ float lastDistance = 0;
+ float totalDistance = 0;
+
+ for (int k = minK; k <= maxK; k++) {
+ // step 1: (arbitrarily) pick k points as the initial centers.
+ int delta = n / k;
+ for (int i = 0; i < k; i++) {
+ Point p = points[i * delta];
+ center[i].latRad = p.latRad;
+ center[i].lngRad = p.lngRad;
+ }
+
+ for (int iter = 0; iter < MAX_ITERATIONS; iter++) {
+ // step 2: assign each point to the nearest center.
+ for (int i = 0; i < k; i++) {
+ groupSum[i].latRad = 0;
+ groupSum[i].lngRad = 0;
+ groupCount[i] = 0;
+ }
+ totalDistance = 0;
+
+ for (int i = 0; i < n; i++) {
+ Point p = points[i];
+ float bestDistance = Float.MAX_VALUE;
+ int bestIndex = 0;
+ for (int j = 0; j < k; j++) {
+ float distance = (float) GalleryUtils.fastDistanceMeters(
+ p.latRad, p.lngRad, center[j].latRad, center[j].lngRad);
+ // We may have small non-zero distance introduced by
+ // floating point calculation, so zero out small
+ // distances less than 1 meter.
+ if (distance < 1) {
+ distance = 0;
+ }
+ if (distance < bestDistance) {
+ bestDistance = distance;
+ bestIndex = j;
+ }
+ }
+ grouping[i] = bestIndex;
+ groupCount[bestIndex]++;
+ groupSum[bestIndex].latRad += p.latRad;
+ groupSum[bestIndex].lngRad += p.lngRad;
+ totalDistance += bestDistance;
+ }
+
+ // step 3: calculate new centers
+ for (int i = 0; i < k; i++) {
+ if (groupCount[i] > 0) {
+ center[i].latRad = groupSum[i].latRad / groupCount[i];
+ center[i].lngRad = groupSum[i].lngRad / groupCount[i];
+ }
+ }
+
+ if (totalDistance == 0 || (Math.abs(lastDistance - totalDistance)
+ / totalDistance) < STOP_CHANGE_RATIO) {
+ break;
+ }
+ lastDistance = totalDistance;
+ }
+
+ // step 4: remove empty groups and reassign group number
+ int reassign[] = new int[k];
+ int realK = 0;
+ for (int i = 0; i < k; i++) {
+ if (groupCount[i] > 0) {
+ reassign[i] = realK++;
+ }
+ }
+
+ // step 5: calculate the final score
+ float score = totalDistance * (float) Math.sqrt(realK);
+
+ if (score < bestScore) {
+ bestScore = score;
+ bestK[0] = realK;
+ for (int i = 0; i < n; i++) {
+ bestGrouping[i] = reassign[grouping[i]];
+ }
+ if (score == 0) {
+ break;
+ }
+ }
+ }
+ return bestGrouping;
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-25 17:22:38 +0000