1 /* 2 * Copyright (C) 2012 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 package android.bordeaux.services; 17 import android.location.Location; 18 import android.text.format.Time; 19 import android.util.Log; 20 21 import java.lang.Math; 22 import java.util.ArrayList; 23 import java.util.HashMap; 24 import java.util.Map; 25 26 public class BaseCluster { 27 28 public static String TAG = "BaseCluster"; 29 30 public double[] mCenter; 31 // protected double[] mCenter; 32 33 protected static final int VECTOR_LENGTH = 3; 34 35 private static final long FORGETTING_ENUMERATOR = 95; 36 private static final long FORGETTING_DENOMINATOR = 100; 37 38 // Histogram illustrates the pattern of visit during time of day, 39 protected HashMap<String, Long> mHistogram = new HashMap<String, Long>(); 40 41 protected long mDuration; 42 43 protected String mSemanticId; 44 45 protected static final double EARTH_RADIUS = 6378100f; 46 47 public BaseCluster(Location location) { 48 mCenter = getLocationVector(location); 49 mDuration = 0; 50 } 51 52 public BaseCluster(String semanticId, double longitude, double latitude, 53 long duration) { 54 mSemanticId = semanticId; 55 mCenter = getLocationVector(longitude, latitude); 56 mDuration = duration; 57 } 58 59 public String getSemanticId() { 60 return mSemanticId; 61 } 62 63 public void generateSemanticId(long index) { 64 mSemanticId = "cluser: " + String.valueOf(index); 65 } 66 67 public long getDuration() { 68 return mDuration; 69 } 70 71 public boolean hasSemanticId() { 72 return mSemanticId != null; 73 } 74 75 protected double[] getLocationVector(Location location) { 76 return getLocationVector(location.getLongitude(), location.getLatitude()); 77 } 78 79 protected double[] getLocationVector(double longitude, double latitude) { 80 double vector[] = new double[VECTOR_LENGTH]; 81 double lambda = Math.toRadians(longitude); 82 double phi = Math.toRadians(latitude); 83 84 vector[0] = Math.cos(lambda) * Math.cos(phi); 85 vector[1] = Math.sin(lambda) * Math.cos(phi); 86 vector[2] = Math.sin(phi); 87 return vector; 88 } 89 90 protected double getCenterLongitude() { 91 // Because latitude ranges from -90 to 90 degrees, cosPhi >= 0. 92 double cosPhi = Math.cos(Math.asin(mCenter[2])); 93 double longitude = Math.toDegrees(Math.asin(mCenter[1] / cosPhi)); 94 if (mCenter[0] < 0) { 95 longitude = (longitude > 0) ? 180f - longitude : -180 - longitude; 96 } 97 return longitude; 98 } 99 100 protected double getCenterLatitude() { 101 return Math.toDegrees(Math.asin(mCenter[2])); 102 } 103 104 private double computeDistance(double[] vector1, double[] vector2) { 105 double product = 0f; 106 for (int i = 0; i < VECTOR_LENGTH; ++i) { 107 product += vector1[i] * vector2[i]; 108 } 109 double radian = Math.acos(Math.min(product, 1f)); 110 return radian * EARTH_RADIUS; 111 } 112 113 /* 114 * This computes the distance from loation to the cluster center in meter. 115 */ 116 public float distanceToCenter(Location location) { 117 return (float) computeDistance(mCenter, getLocationVector(location)); 118 } 119 120 public float distanceToCluster(BaseCluster cluster) { 121 return (float) computeDistance(mCenter, cluster.mCenter); 122 } 123 124 public void absorbCluster(BaseCluster cluster) { 125 averageCenter(cluster.mCenter, cluster.mDuration); 126 absorbHistogram(cluster); 127 } 128 129 public void setCluster(BaseCluster cluster) { 130 for (int i = 0; i < VECTOR_LENGTH; ++i) { 131 mCenter[i] = cluster.mCenter[i]; 132 } 133 mHistogram.clear(); 134 mHistogram.putAll(cluster.mHistogram); 135 mDuration = cluster.mDuration; 136 } 137 138 private void absorbHistogram(BaseCluster cluster) { 139 for (Map.Entry<String, Long> entry : cluster.mHistogram.entrySet()) { 140 String timeLabel = entry.getKey(); 141 long duration = entry.getValue(); 142 143 if (mHistogram.containsKey(timeLabel)) { 144 duration += mHistogram.get(timeLabel); 145 } 146 mHistogram.put(timeLabel, duration); 147 } 148 mDuration += cluster.mDuration; 149 } 150 151 public boolean passThreshold(long durationThreshold) { 152 // TODO: might want to keep semantic cluster 153 return mDuration > durationThreshold; 154 } 155 156 public final HashMap<String, Long> getHistogram() { 157 return mHistogram; 158 } 159 160 public void setHistogram(Map<String, Long> histogram) { 161 mHistogram.clear(); 162 mHistogram.putAll(histogram); 163 164 mDuration = 0; 165 if (mHistogram.containsKey(TimeStatsAggregator.WEEKEND)) { 166 mDuration += mHistogram.get(TimeStatsAggregator.WEEKEND); 167 } 168 if (mHistogram.containsKey(TimeStatsAggregator.WEEKDAY)) { 169 mDuration += mHistogram.get(TimeStatsAggregator.WEEKDAY); 170 } 171 } 172 173 public void forgetPastHistory() { 174 mDuration *= FORGETTING_ENUMERATOR; 175 mDuration /= FORGETTING_DENOMINATOR; 176 177 for (Map.Entry<String, Long> entry : mHistogram.entrySet()) { 178 String key = entry.getKey(); 179 long value = entry.getValue(); 180 181 value *= FORGETTING_ENUMERATOR; 182 value /= FORGETTING_DENOMINATOR; 183 184 mHistogram.put(key, value); 185 } 186 } 187 188 protected void normalizeCenter() { 189 double norm = 0; 190 for (int i = 0; i < VECTOR_LENGTH; ++i) { 191 norm += mCenter[i] * mCenter[i]; 192 } 193 norm = Math.sqrt(norm); 194 for (int i = 0; i < VECTOR_LENGTH; ++i) { 195 mCenter[i] /= norm; 196 } 197 } 198 199 protected void averageCenter(double[] newCenter, long newDuration) { 200 double weight = ((double) mDuration) / (mDuration + newDuration); 201 double newWeight = 1f - weight; 202 203 double norm = 0; 204 for (int i = 0; i < VECTOR_LENGTH; ++i) { 205 mCenter[i] = weight * mCenter[i] + newWeight * newCenter[i]; 206 norm += mCenter[i] * mCenter[i]; 207 } 208 norm = Math.sqrt(norm); 209 for (int i = 0; i < VECTOR_LENGTH; ++i) { 210 mCenter[i] /= norm; 211 } 212 } 213 } 214
