Jordan Liu | dfcbfaf | 2019-10-11 11:42:03 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2019 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.cellbroadcastservice; |
| 18 | |
| 19 | import android.annotation.NonNull; |
Jordan Liu | 8d7d0a1 | 2019-10-21 12:30:56 -0700 | [diff] [blame] | 20 | import android.telephony.CbGeoUtils.Geometry; |
| 21 | import android.telephony.CbGeoUtils.LatLng; |
Jordan Liu | dfcbfaf | 2019-10-11 11:42:03 -0700 | [diff] [blame] | 22 | import android.text.TextUtils; |
Jordan Liu | e532d23 | 2019-12-16 15:35:27 -0800 | [diff] [blame] | 23 | import android.util.Log; |
Jordan Liu | dfcbfaf | 2019-10-11 11:42:03 -0700 | [diff] [blame] | 24 | |
| 25 | import java.util.ArrayList; |
| 26 | import java.util.List; |
| 27 | import java.util.stream.Collectors; |
| 28 | |
| 29 | /** |
| 30 | * This utils class is specifically used for geo-targeting of CellBroadcast messages. |
| 31 | * The coordinates used by this utils class are latitude and longitude, but some algorithms in this |
| 32 | * class only use them as coordinates on plane, so the calculation will be inaccurate. So don't use |
| 33 | * this class for anything other then geo-targeting of cellbroadcast messages. |
| 34 | */ |
| 35 | public class CbGeoUtils { |
| 36 | /** |
| 37 | * Tolerance for determining if the value is 0. If the absolute value of a value is less than |
| 38 | * this tolerance, it will be treated as 0. |
| 39 | */ |
| 40 | public static final double EPS = 1e-7; |
| 41 | |
| 42 | private static final String TAG = "CbGeoUtils"; |
| 43 | |
| 44 | /** The TLV tags of WAC, defined in ATIS-0700041 5.2.3 WAC tag coding. */ |
| 45 | public static final int GEO_FENCING_MAXIMUM_WAIT_TIME = 0x01; |
| 46 | public static final int GEOMETRY_TYPE_POLYGON = 0x02; |
| 47 | public static final int GEOMETRY_TYPE_CIRCLE = 0x03; |
| 48 | |
| 49 | /** The identifier of geometry in the encoded string. */ |
| 50 | private static final String CIRCLE_SYMBOL = "circle"; |
| 51 | private static final String POLYGON_SYMBOL = "polygon"; |
| 52 | |
| 53 | /** |
| 54 | * The class represents a simple polygon with at least 3 points. |
| 55 | */ |
Jordan Liu | 8d7d0a1 | 2019-10-21 12:30:56 -0700 | [diff] [blame] | 56 | public static class Polygon implements Geometry { |
Jordan Liu | dfcbfaf | 2019-10-11 11:42:03 -0700 | [diff] [blame] | 57 | /** |
| 58 | * In order to reduce the loss of precision in floating point calculations, all vertices |
| 59 | * of the polygon are scaled. Set the value of scale to 1000 can take into account the |
| 60 | * actual distance accuracy of 1 meter if the EPS is 1e-7 during the calculation. |
| 61 | */ |
| 62 | private static final double SCALE = 1000.0; |
| 63 | |
| 64 | private final List<LatLng> mVertices; |
| 65 | private final List<Point> mScaledVertices; |
| 66 | private final LatLng mOrigin; |
| 67 | |
| 68 | /** |
| 69 | * Constructs a simple polygon from the given vertices. The adjacent two vertices are |
| 70 | * connected to form an edge of the polygon. The polygon has at least 3 vertices, and the |
| 71 | * last vertices and the first vertices must be adjacent. |
| 72 | * |
| 73 | * The longitude difference in the vertices should be less than 180 degree. |
| 74 | */ |
| 75 | public Polygon(@NonNull List<LatLng> vertices) { |
| 76 | mVertices = vertices; |
| 77 | |
| 78 | // Find the point with smallest longitude as the mOrigin point. |
| 79 | int idx = 0; |
| 80 | for (int i = 1; i < vertices.size(); i++) { |
| 81 | if (vertices.get(i).lng < vertices.get(idx).lng) { |
| 82 | idx = i; |
| 83 | } |
| 84 | } |
| 85 | mOrigin = vertices.get(idx); |
| 86 | |
| 87 | mScaledVertices = vertices.stream() |
| 88 | .map(latLng -> convertAndScaleLatLng(latLng)) |
| 89 | .collect(Collectors.toList()); |
| 90 | } |
| 91 | |
| 92 | public List<LatLng> getVertices() { |
| 93 | return mVertices; |
| 94 | } |
| 95 | |
| 96 | /** |
| 97 | * Check if the given point {@code p} is inside the polygon. This method counts the number |
| 98 | * of times the polygon winds around the point P, A.K.A "winding number". The point is |
| 99 | * outside only when this "winding number" is 0. |
| 100 | * |
| 101 | * If a point is on the edge of the polygon, it is also considered to be inside the polygon. |
| 102 | */ |
| 103 | @Override |
| 104 | public boolean contains(LatLng latLng) { |
| 105 | Point p = convertAndScaleLatLng(latLng); |
| 106 | |
| 107 | int n = mScaledVertices.size(); |
| 108 | int windingNumber = 0; |
| 109 | for (int i = 0; i < n; i++) { |
| 110 | Point a = mScaledVertices.get(i); |
| 111 | Point b = mScaledVertices.get((i + 1) % n); |
| 112 | |
| 113 | // CCW is counterclockwise |
| 114 | // CCW = ab x ap |
| 115 | // CCW > 0 -> ap is on the left side of ab |
| 116 | // CCW == 0 -> ap is on the same line of ab |
| 117 | // CCW < 0 -> ap is on the right side of ab |
| 118 | int ccw = sign(crossProduct(b.subtract(a), p.subtract(a))); |
| 119 | |
| 120 | if (ccw == 0) { |
| 121 | if (Math.min(a.x, b.x) <= p.x && p.x <= Math.max(a.x, b.x) |
| 122 | && Math.min(a.y, b.y) <= p.y && p.y <= Math.max(a.y, b.y)) { |
| 123 | return true; |
| 124 | } |
| 125 | } else { |
| 126 | if (sign(a.y - p.y) <= 0) { |
| 127 | // upward crossing |
| 128 | if (ccw > 0 && sign(b.y - p.y) > 0) { |
| 129 | ++windingNumber; |
| 130 | } |
| 131 | } else { |
| 132 | // downward crossing |
| 133 | if (ccw < 0 && sign(b.y - p.y) <= 0) { |
| 134 | --windingNumber; |
| 135 | } |
| 136 | } |
| 137 | } |
| 138 | } |
| 139 | return windingNumber != 0; |
| 140 | } |
| 141 | |
| 142 | /** |
| 143 | * Move the given point {@code latLng} to the coordinate system with {@code mOrigin} as the |
| 144 | * origin and scale it. {@code mOrigin} is selected from the vertices of a polygon, it has |
| 145 | * the smallest longitude value among all of the polygon vertices. |
| 146 | * |
| 147 | * @param latLng the point need to be converted and scaled. |
| 148 | * @Return a {@link Point} object. |
| 149 | */ |
| 150 | private Point convertAndScaleLatLng(LatLng latLng) { |
| 151 | double x = latLng.lat - mOrigin.lat; |
| 152 | double y = latLng.lng - mOrigin.lng; |
| 153 | |
| 154 | // If the point is in different hemispheres(western/eastern) than the mOrigin, and the |
| 155 | // edge between them cross the 180th meridian, then its relative coordinates will be |
| 156 | // extended. |
| 157 | // For example, suppose the longitude of the mOrigin is -178, and the longitude of the |
| 158 | // point to be converted is 175, then the longitude after the conversion is -8. |
| 159 | // calculation: (-178 - 8) - (-178). |
| 160 | if (sign(mOrigin.lng) != 0 && sign(mOrigin.lng) != sign(latLng.lng)) { |
| 161 | double distCross0thMeridian = Math.abs(mOrigin.lng) + Math.abs(latLng.lng); |
| 162 | if (sign(distCross0thMeridian * 2 - 360) > 0) { |
| 163 | y = sign(mOrigin.lng) * (360 - distCross0thMeridian); |
| 164 | } |
| 165 | } |
| 166 | return new Point(x * SCALE, y * SCALE); |
| 167 | } |
| 168 | |
| 169 | private static double crossProduct(Point a, Point b) { |
| 170 | return a.x * b.y - a.y * b.x; |
| 171 | } |
| 172 | |
| 173 | static final class Point { |
| 174 | public final double x; |
| 175 | public final double y; |
| 176 | |
| 177 | Point(double x, double y) { |
| 178 | this.x = x; |
| 179 | this.y = y; |
| 180 | } |
| 181 | |
| 182 | public Point subtract(Point p) { |
| 183 | return new Point(x - p.x, y - p.y); |
| 184 | } |
| 185 | } |
| 186 | } |
| 187 | |
| 188 | /** The class represents a circle. */ |
| 189 | public static class Circle implements Geometry { |
| 190 | private final LatLng mCenter; |
| 191 | private final double mRadiusMeter; |
| 192 | |
| 193 | public Circle(LatLng center, double radiusMeter) { |
| 194 | this.mCenter = center; |
| 195 | this.mRadiusMeter = radiusMeter; |
| 196 | } |
| 197 | |
| 198 | public LatLng getCenter() { |
| 199 | return mCenter; |
| 200 | } |
| 201 | |
| 202 | public double getRadius() { |
| 203 | return mRadiusMeter; |
| 204 | } |
| 205 | |
| 206 | @Override |
| 207 | public boolean contains(LatLng p) { |
| 208 | return mCenter.distance(p) <= mRadiusMeter; |
| 209 | } |
| 210 | } |
| 211 | |
| 212 | /** |
| 213 | * Parse the geometries from the encoded string {@code str}. The string must follow the |
| 214 | * geometry encoding specified by {@link android.provider.Telephony.CellBroadcasts#GEOMETRIES}. |
| 215 | */ |
| 216 | @NonNull |
| 217 | public static List<Geometry> parseGeometriesFromString(@NonNull String str) { |
| 218 | List<Geometry> geometries = new ArrayList<>(); |
| 219 | for (String geometryStr : str.split("\\s*;\\s*")) { |
| 220 | String[] geoParameters = geometryStr.split("\\s*\\|\\s*"); |
| 221 | switch (geoParameters[0]) { |
| 222 | case CIRCLE_SYMBOL: |
| 223 | geometries.add(new Circle(parseLatLngFromString(geoParameters[1]), |
| 224 | Double.parseDouble(geoParameters[2]))); |
| 225 | break; |
| 226 | case POLYGON_SYMBOL: |
| 227 | List<LatLng> vertices = new ArrayList<>(geoParameters.length - 1); |
| 228 | for (int i = 1; i < geoParameters.length; i++) { |
| 229 | vertices.add(parseLatLngFromString(geoParameters[i])); |
| 230 | } |
| 231 | geometries.add(new Polygon(vertices)); |
| 232 | break; |
| 233 | default: |
Jordan Liu | e532d23 | 2019-12-16 15:35:27 -0800 | [diff] [blame] | 234 | Log.e(TAG, "Invalid geometry format " + geometryStr); |
Jordan Liu | 62e183f | 2019-12-20 15:09:44 -0800 | [diff] [blame] | 235 | CellBroadcastStatsLog.write(CellBroadcastStatsLog.CB_MESSAGE_ERROR, |
| 236 | CellBroadcastStatsLog.CELL_BROADCAST_MESSAGE_ERROR__TYPE__UNEXPECTED_GEOMETRY_FROM_FWK, |
| 237 | geometryStr); |
Jordan Liu | dfcbfaf | 2019-10-11 11:42:03 -0700 | [diff] [blame] | 238 | } |
| 239 | } |
| 240 | return geometries; |
| 241 | } |
| 242 | |
| 243 | /** |
| 244 | * Encode a list of geometry objects to string. The encoding format is specified by |
| 245 | * {@link android.provider.Telephony.CellBroadcasts#GEOMETRIES}. |
| 246 | * |
| 247 | * @param geometries the list of geometry objects need to be encoded. |
| 248 | * @return the encoded string. |
| 249 | */ |
| 250 | @NonNull |
| 251 | public static String encodeGeometriesToString(@NonNull List<Geometry> geometries) { |
| 252 | return geometries.stream() |
| 253 | .map(geometry -> encodeGeometryToString(geometry)) |
| 254 | .filter(encodedStr -> !TextUtils.isEmpty(encodedStr)) |
| 255 | .collect(Collectors.joining(";")); |
| 256 | } |
| 257 | |
| 258 | |
| 259 | /** |
| 260 | * Encode the geometry object to string. The encoding format is specified by |
| 261 | * {@link android.provider.Telephony.CellBroadcasts#GEOMETRIES}. |
| 262 | * @param geometry the geometry object need to be encoded. |
| 263 | * @return the encoded string. |
| 264 | */ |
| 265 | @NonNull |
| 266 | private static String encodeGeometryToString(@NonNull Geometry geometry) { |
| 267 | StringBuilder sb = new StringBuilder(); |
| 268 | if (geometry instanceof Polygon) { |
| 269 | sb.append(POLYGON_SYMBOL); |
| 270 | for (LatLng latLng : ((Polygon) geometry).getVertices()) { |
| 271 | sb.append("|"); |
| 272 | sb.append(latLng.lat); |
| 273 | sb.append(","); |
| 274 | sb.append(latLng.lng); |
| 275 | } |
| 276 | } else if (geometry instanceof Circle) { |
| 277 | sb.append(CIRCLE_SYMBOL); |
| 278 | Circle circle = (Circle) geometry; |
| 279 | |
| 280 | // Center |
| 281 | sb.append("|"); |
| 282 | sb.append(circle.getCenter().lat); |
| 283 | sb.append(","); |
| 284 | sb.append(circle.getCenter().lng); |
| 285 | |
| 286 | // Radius |
| 287 | sb.append("|"); |
| 288 | sb.append(circle.getRadius()); |
| 289 | } else { |
Jordan Liu | e532d23 | 2019-12-16 15:35:27 -0800 | [diff] [blame] | 290 | Log.e(TAG, "Unsupported geometry object " + geometry); |
Jordan Liu | dfcbfaf | 2019-10-11 11:42:03 -0700 | [diff] [blame] | 291 | return null; |
| 292 | } |
| 293 | return sb.toString(); |
| 294 | } |
| 295 | |
| 296 | /** |
| 297 | * Parse {@link LatLng} from {@link String}. Latitude and longitude are separated by ",". |
| 298 | * Example: "13.56,-55.447". |
| 299 | * |
| 300 | * @param str encoded lat/lng string. |
| 301 | * @Return {@link LatLng} object. |
| 302 | */ |
| 303 | @NonNull |
| 304 | public static LatLng parseLatLngFromString(@NonNull String str) { |
| 305 | String[] latLng = str.split("\\s*,\\s*"); |
| 306 | return new LatLng(Double.parseDouble(latLng[0]), Double.parseDouble(latLng[1])); |
| 307 | } |
| 308 | |
| 309 | /** |
| 310 | * @Return the sign of the given value {@code value} with the specified tolerance. Return 1 |
| 311 | * means the sign is positive, -1 means negative, 0 means the value will be treated as 0. |
| 312 | */ |
| 313 | public static int sign(double value) { |
| 314 | if (value > EPS) return 1; |
| 315 | if (value < -EPS) return -1; |
| 316 | return 0; |
| 317 | } |
| 318 | } |