| /* |
| * 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 TLV tags of WAC, defined in ATIS-0700041 5.2.3 WAC tag coding. */ |
| public static final int GEO_FENCING_MAXIMUM_WAIT_TIME = 0x01; |
| public static final int GEOMETRY_TYPE_POLYGON = 0x02; |
| public static final int GEOMETRY_TYPE_CIRCLE = 0x03; |
| |
| /** 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; |
| } |
| |
| @Override |
| public String toString() { |
| return "(" + lat + "," + lng + ")"; |
| } |
| } |
| |
| /** |
| * 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<LatLng> mVertices; |
| private final List<Point> 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<LatLng> 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<LatLng> 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<Geometry> parseGeometriesFromString(@NonNull String str) { |
| List<Geometry> 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<LatLng> 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(List<Geometry> geometries) { |
| if (geometries == null || geometries.isEmpty()) return ""; |
| 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; |
| } |
| } |