gallery3d/data/LocationClustering.java

/*
 * 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;
    }
}