blob: 788060cf06a6da5511045766f283823e903b2e88 [file] [log] [blame]
/*
* 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.os.Handler;
import android.os.Looper;
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 Handler mHandler;
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);
mHandler = new Handler(Looper.getMainLooper());
}
@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) {
mHandler.post(new Runnable() {
public void run() {
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;
}
}