From 542967613125640c0b476572f86b4ac2cff4ba7c Mon Sep 17 00:00:00 2001 From: Pengquan Meng Date: Wed, 14 Aug 2019 17:57:33 -0700 Subject: [PATCH] Add geo targeting implementation This CL adds support for geo targeting, including determining whether a point is inside a simple polygon and circle. For the judgment of the point in the polygon, the algorithm implemented here simply considers the spherical polygon as a 2d plane polygon, which may be not precisely. However, according to the test of real geographical coordinates data i.e state/city/stree boundary data, this error is less than 10 meters that within 160 meters requires by the spec. Bug: 123096618 Test: atest GeoUtils Merged-In: I51e1fad3b48c1a58fa0510f97d9f5f9335779c30 Change-Id: I51e1fad3b48c1a58fa0510f97d9f5f9335779c30 (cherry picked from commit 7fbc74b66b58dd57deedb7336c5c1e2f0f9e2064) --- .../com/android/internal/telephony/CbGeoUtils.java | 359 +++++++++++++++++++++ 1 file changed, 359 insertions(+) create mode 100644 telephony/java/com/android/internal/telephony/CbGeoUtils.java diff --git a/telephony/java/com/android/internal/telephony/CbGeoUtils.java b/telephony/java/com/android/internal/telephony/CbGeoUtils.java new file mode 100644 index 000000000000..c973b672ae40 --- /dev/null +++ b/telephony/java/com/android/internal/telephony/CbGeoUtils.java @@ -0,0 +1,359 @@ +/* + * Copyright (C) 2019 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.internal.telephony; + +import android.annotation.NonNull; +import android.telephony.Rlog; +import android.text.TextUtils; + +import java.util.ArrayList; +import java.util.List; +import java.util.stream.Collectors; + + +/** + * This utils class is specifically used for geo-targeting of CellBroadcast messages. + * The coordinates used by this utils class are latitude and longitude, but some algorithms in this + * class only use them as coordinates on plane, so the calculation will be inaccurate. So don't use + * this class for anything other then geo-targeting of cellbroadcast messages. + */ +public class CbGeoUtils { + /** Geometric interface. */ + public interface Geometry { + /** + * Determines if the given point {@code p} is inside the geometry. + * @param p point in latitude, longitude format. + * @return {@code True} if the given point is inside the geometry. + */ + boolean contains(LatLng p); + } + + /** + * Tolerance for determining if the value is 0. If the absolute value of a value is less than + * this tolerance, it will be treated as 0. + */ + public static final double EPS = 1e-7; + + /** The radius of earth. */ + public static final int EARTH_RADIUS_METER = 6371 * 1000; + + private static final String TAG = "CbGeoUtils"; + + /** The identifier of geometry in the encoded string. */ + private static final String CIRCLE_SYMBOL = "circle"; + private static final String POLYGON_SYMBOL = "polygon"; + + /** Point represent by (latitude, longitude). */ + public static class LatLng { + public final double lat; + public final double lng; + + /** + * Constructor. + * @param lat latitude, range [-90, 90] + * @param lng longitude, range [-180, 180] + */ + public LatLng(double lat, double lng) { + this.lat = lat; + this.lng = lng; + } + + /** + * @param p the point use to calculate the subtraction result. + * @return the result of this point subtract the given point {@code p}. + */ + public LatLng subtract(LatLng p) { + return new LatLng(lat - p.lat, lng - p.lng); + } + + /** + * Calculate the distance in meter between this point and the given point {@code p}. + * @param p the point use to calculate the distance. + * @return the distance in meter. + */ + public double distance(LatLng p) { + double dlat = Math.sin(0.5 * Math.toRadians(lat - p.lat)); + double dlng = Math.sin(0.5 * Math.toRadians(lng - p.lng)); + double x = dlat * dlat + + dlng * dlng * Math.cos(Math.toRadians(lat)) * Math.cos(Math.toRadians(p.lat)); + return 2 * Math.atan2(Math.sqrt(x), Math.sqrt(1 - x)) * EARTH_RADIUS_METER; + } + } + + /** + * The class represents a simple polygon with at least 3 points. + */ + public static class Polygon implements Geometry { + /** + * In order to reduce the loss of precision in floating point calculations, all vertices + * of the polygon are scaled. Set the value of scale to 1000 can take into account the + * actual distance accuracy of 1 meter if the EPS is 1e-7 during the calculation. + */ + private static final double SCALE = 1000.0; + + private final List mVertices; + private final List mScaledVertices; + private final LatLng mOrigin; + + /** + * Constructs a simple polygon from the given vertices. The adjacent two vertices are + * connected to form an edge of the polygon. The polygon has at least 3 vertices, and the + * last vertices and the first vertices must be adjacent. + * + * The longitude difference in the vertices should be less than 180 degree. + */ + public Polygon(@NonNull List vertices) { + mVertices = vertices; + + // Find the point with smallest longitude as the mOrigin point. + int idx = 0; + for (int i = 1; i < vertices.size(); i++) { + if (vertices.get(i).lng < vertices.get(idx).lng) { + idx = i; + } + } + mOrigin = vertices.get(idx); + + mScaledVertices = vertices.stream() + .map(latLng -> convertAndScaleLatLng(latLng)) + .collect(Collectors.toList()); + } + + public List getVertices() { + return mVertices; + } + + /** + * Check if the given point {@code p} is inside the polygon. This method counts the number + * of times the polygon winds around the point P, A.K.A "winding number". The point is + * outside only when this "winding number" is 0. + * + * If a point is on the edge of the polygon, it is also considered to be inside the polygon. + */ + @Override + public boolean contains(LatLng latLng) { + Point p = convertAndScaleLatLng(latLng); + + int n = mScaledVertices.size(); + int windingNumber = 0; + for (int i = 0; i < n; i++) { + Point a = mScaledVertices.get(i); + Point b = mScaledVertices.get((i + 1) % n); + + // CCW is counterclockwise + // CCW = ab x ap + // CCW > 0 -> ap is on the left side of ab + // CCW == 0 -> ap is on the same line of ab + // CCW < 0 -> ap is on the right side of ab + int ccw = sign(crossProduct(b.subtract(a), p.subtract(a))); + + if (ccw == 0) { + if (Math.min(a.x, b.x) <= p.x && p.x <= Math.max(a.x, b.x) + && Math.min(a.y, b.y) <= p.y && p.y <= Math.max(a.y, b.y)) { + return true; + } + } else { + if (sign(a.y - p.y) <= 0) { + // upward crossing + if (ccw > 0 && sign(b.y - p.y) > 0) { + ++windingNumber; + } + } else { + // downward crossing + if (ccw < 0 && sign(b.y - p.y) <= 0) { + --windingNumber; + } + } + } + } + return windingNumber != 0; + } + + /** + * Move the given point {@code latLng} to the coordinate system with {@code mOrigin} as the + * origin and scale it. {@code mOrigin} is selected from the vertices of a polygon, it has + * the smallest longitude value among all of the polygon vertices. + * + * @param latLng the point need to be converted and scaled. + * @Return a {@link Point} object. + */ + private Point convertAndScaleLatLng(LatLng latLng) { + double x = latLng.lat - mOrigin.lat; + double y = latLng.lng - mOrigin.lng; + + // If the point is in different hemispheres(western/eastern) than the mOrigin, and the + // edge between them cross the 180th meridian, then its relative coordinates will be + // extended. + // For example, suppose the longitude of the mOrigin is -178, and the longitude of the + // point to be converted is 175, then the longitude after the conversion is -8. + // calculation: (-178 - 8) - (-178). + if (sign(mOrigin.lng) != 0 && sign(mOrigin.lng) != sign(latLng.lng)) { + double distCross0thMeridian = Math.abs(mOrigin.lng) + Math.abs(latLng.lng); + if (sign(distCross0thMeridian * 2 - 360) > 0) { + y = sign(mOrigin.lng) * (360 - distCross0thMeridian); + } + } + return new Point(x * SCALE, y * SCALE); + } + + private static double crossProduct(Point a, Point b) { + return a.x * b.y - a.y * b.x; + } + + static final class Point { + public final double x; + public final double y; + + Point(double x, double y) { + this.x = x; + this.y = y; + } + + public Point subtract(Point p) { + return new Point(x - p.x, y - p.y); + } + } + } + + /** The class represents a circle. */ + public static class Circle implements Geometry { + private final LatLng mCenter; + private final double mRadiusMeter; + + public Circle(LatLng center, double radiusMeter) { + this.mCenter = center; + this.mRadiusMeter = radiusMeter; + } + + public LatLng getCenter() { + return mCenter; + } + + public double getRadius() { + return mRadiusMeter; + } + + @Override + public boolean contains(LatLng p) { + return mCenter.distance(p) <= mRadiusMeter; + } + } + + /** + * Parse the geometries from the encoded string {@code str}. The string must follow the + * geometry encoding specified by {@link android.provider.Telephony.CellBroadcasts#GEOMETRIES}. + */ + @NonNull + public static List parseGeometriesFromString(@NonNull String str) { + List geometries = new ArrayList<>(); + for (String geometryStr : str.split("\\s*;\\s*")) { + String[] geoParameters = geometryStr.split("\\s*\\|\\s*"); + switch (geoParameters[0]) { + case CIRCLE_SYMBOL: + geometries.add(new Circle(parseLatLngFromString(geoParameters[1]), + Double.parseDouble(geoParameters[2]))); + break; + case POLYGON_SYMBOL: + List vertices = new ArrayList<>(geoParameters.length - 1); + for (int i = 1; i < geoParameters.length; i++) { + vertices.add(parseLatLngFromString(geoParameters[i])); + } + geometries.add(new Polygon(vertices)); + break; + default: + Rlog.e(TAG, "Invalid geometry format " + geometryStr); + } + } + return geometries; + } + + /** + * Encode a list of geometry objects to string. The encoding format is specified by + * {@link android.provider.Telephony.CellBroadcasts#GEOMETRIES}. + * + * @param geometries the list of geometry objects need to be encoded. + * @return the encoded string. + */ + @NonNull + public static String encodeGeometriesToString(@NonNull List geometries) { + return geometries.stream() + .map(geometry -> encodeGeometryToString(geometry)) + .filter(encodedStr -> !TextUtils.isEmpty(encodedStr)) + .collect(Collectors.joining(";")); + } + + + /** + * Encode the geometry object to string. The encoding format is specified by + * {@link android.provider.Telephony.CellBroadcasts#GEOMETRIES}. + * @param geometry the geometry object need to be encoded. + * @return the encoded string. + */ + @NonNull + private static String encodeGeometryToString(@NonNull Geometry geometry) { + StringBuilder sb = new StringBuilder(); + if (geometry instanceof Polygon) { + sb.append(POLYGON_SYMBOL); + for (LatLng latLng : ((Polygon) geometry).getVertices()) { + sb.append("|"); + sb.append(latLng.lat); + sb.append(","); + sb.append(latLng.lng); + } + } else if (geometry instanceof Circle) { + sb.append(CIRCLE_SYMBOL); + Circle circle = (Circle) geometry; + + // Center + sb.append("|"); + sb.append(circle.getCenter().lat); + sb.append(","); + sb.append(circle.getCenter().lng); + + // Radius + sb.append("|"); + sb.append(circle.getRadius()); + } else { + Rlog.e(TAG, "Unsupported geometry object " + geometry); + return null; + } + return sb.toString(); + } + + /** + * Parse {@link LatLng} from {@link String}. Latitude and longitude are separated by ",". + * Example: "13.56,-55.447". + * + * @param str encoded lat/lng string. + * @Return {@link LatLng} object. + */ + @NonNull + public static LatLng parseLatLngFromString(@NonNull String str) { + String[] latLng = str.split("\\s*,\\s*"); + return new LatLng(Double.parseDouble(latLng[0]), Double.parseDouble(latLng[1])); + } + + /** + * @Return the sign of the given value {@code value} with the specified tolerance. Return 1 + * means the sign is positive, -1 means negative, 0 means the value will be treated as 0. + */ + public static int sign(double value) { + if (value > EPS) return 1; + if (value < -EPS) return -1; + return 0; + } +} -- 2.11.0