511 lines
17 KiB
Java
511 lines
17 KiB
Java
![]() |
/*
|
||
|
* 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 android.telephony;
|
||
|
|
||
|
import android.annotation.NonNull;
|
||
|
import android.annotation.SystemApi;
|
||
|
import android.text.TextUtils;
|
||
|
|
||
|
import com.android.internal.telephony.util.TelephonyUtils;
|
||
|
import com.android.telephony.Rlog;
|
||
|
|
||
|
import java.util.ArrayList;
|
||
|
import java.util.List;
|
||
|
import java.util.stream.Collectors;
|
||
|
|
||
|
/**
|
||
|
* This utils class is used for geo-fencing of CellBroadcast messages and is used by the cell
|
||
|
* broadcast module.
|
||
|
*
|
||
|
* 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.
|
||
|
*
|
||
|
* More information regarding cell broadcast geo-fencing logic is laid out in 3GPP TS 23.041 and
|
||
|
* ATIS-0700041.
|
||
|
* @hide
|
||
|
*/
|
||
|
@SystemApi
|
||
|
public class CbGeoUtils {
|
||
|
|
||
|
/**
|
||
|
* This class is never instantiated
|
||
|
* @hide
|
||
|
*/
|
||
|
private 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(@NonNull 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.
|
||
|
* @hide
|
||
|
*/
|
||
|
public static final double EPS = 1e-7;
|
||
|
|
||
|
/**
|
||
|
* The radius of earth.
|
||
|
* @hide
|
||
|
*/
|
||
|
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.
|
||
|
/** @hide */
|
||
|
public static final int GEO_FENCING_MAXIMUM_WAIT_TIME = 0x01;
|
||
|
/** @hide */
|
||
|
public static final int GEOMETRY_TYPE_POLYGON = 0x02;
|
||
|
/** @hide */
|
||
|
public static final int GEOMETRY_TYPE_CIRCLE = 0x03;
|
||
|
|
||
|
// The identifier of geometry in the encoded string.
|
||
|
/** @hide */
|
||
|
private static final String CIRCLE_SYMBOL = "circle";
|
||
|
/** @hide */
|
||
|
private static final String POLYGON_SYMBOL = "polygon";
|
||
|
|
||
|
/** A point represented 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 to subtract
|
||
|
* @return the result of the subtraction
|
||
|
*/
|
||
|
@NonNull
|
||
|
public LatLng subtract(@NonNull LatLng p) {
|
||
|
return new LatLng(lat - p.lat, lng - p.lng);
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* Calculate the distance in meters between this point and the given point {@code p}.
|
||
|
* @param p the point used to calculate the distance.
|
||
|
* @return the distance in meters.
|
||
|
*/
|
||
|
public double distance(@NonNull 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 + ")";
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* @hide
|
||
|
*/
|
||
|
@Override
|
||
|
public boolean equals(Object o) {
|
||
|
if (o == this) {
|
||
|
return true;
|
||
|
}
|
||
|
|
||
|
if (!(o instanceof LatLng)) {
|
||
|
return false;
|
||
|
}
|
||
|
|
||
|
LatLng l = (LatLng) o;
|
||
|
return lat == l.lat && lng == l.lng;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* A class representing a simple polygon with at least 3 points. This is used for geo-fencing
|
||
|
* logic with cell broadcasts. More information regarding cell broadcast geo-fencing logic is
|
||
|
* laid out in 3GPP TS 23.041 and ATIS-0700041.
|
||
|
*/
|
||
|
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 degrees.
|
||
|
*/
|
||
|
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());
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* Return the list of vertices which compose the polygon.
|
||
|
*/
|
||
|
public @NonNull List<LatLng> getVertices() {
|
||
|
return mVertices;
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* Check if the given LatLng is inside the polygon.
|
||
|
*
|
||
|
* If a LatLng is on the edge of the polygon, it is also considered to be inside the
|
||
|
* polygon.
|
||
|
*/
|
||
|
@Override
|
||
|
public boolean contains(@NonNull LatLng latLng) {
|
||
|
// 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.
|
||
|
|
||
|
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;
|
||
|
}
|
||
|
|
||
|
/** @hide */
|
||
|
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);
|
||
|
}
|
||
|
}
|
||
|
|
||
|
@Override
|
||
|
public String toString() {
|
||
|
String str = "Polygon: ";
|
||
|
if (TelephonyUtils.IS_DEBUGGABLE) {
|
||
|
str += mVertices;
|
||
|
}
|
||
|
return str;
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* @hide
|
||
|
*/
|
||
|
@Override
|
||
|
public boolean equals(Object o) {
|
||
|
if (o == this) {
|
||
|
return true;
|
||
|
}
|
||
|
|
||
|
if (!(o instanceof Polygon)) {
|
||
|
return false;
|
||
|
}
|
||
|
|
||
|
Polygon p = (Polygon) o;
|
||
|
if (mVertices.size() != p.mVertices.size()) {
|
||
|
return false;
|
||
|
}
|
||
|
for (int i = 0; i < mVertices.size(); i++) {
|
||
|
if (!mVertices.get(i).equals(p.mVertices.get(i))) {
|
||
|
return false;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
return true;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* A class represents a {@link Geometry} in the shape of a Circle. This is used for handling
|
||
|
* geo-fenced cell broadcasts. More information regarding cell broadcast geo-fencing logic is
|
||
|
* laid out in 3GPP TS 23.041 and ATIS-0700041.
|
||
|
*/
|
||
|
public static class Circle implements Geometry {
|
||
|
private final LatLng mCenter;
|
||
|
private final double mRadiusMeter;
|
||
|
|
||
|
/**
|
||
|
* Construct a Circle given a center point and a radius in meters.
|
||
|
*
|
||
|
* @param center the latitude and longitude of the center of the circle
|
||
|
* @param radiusInMeters the radius of the circle in meters
|
||
|
*/
|
||
|
public Circle(@NonNull LatLng center, double radiusInMeters) {
|
||
|
this.mCenter = center;
|
||
|
this.mRadiusMeter = radiusInMeters;
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* Return the latitude and longitude of the center of the circle;
|
||
|
*/
|
||
|
public @NonNull LatLng getCenter() {
|
||
|
return mCenter;
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* Return the radius of the circle in meters.
|
||
|
*/
|
||
|
public double getRadius() {
|
||
|
return mRadiusMeter;
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* Check if the given LatLng is inside the circle.
|
||
|
*
|
||
|
* If a LatLng is on the edge of the circle, it is also considered to be inside the circle.
|
||
|
*/
|
||
|
@Override
|
||
|
public boolean contains(@NonNull LatLng latLng) {
|
||
|
return mCenter.distance(latLng) <= mRadiusMeter;
|
||
|
}
|
||
|
|
||
|
@Override
|
||
|
public String toString() {
|
||
|
String str = "Circle: ";
|
||
|
if (TelephonyUtils.IS_DEBUGGABLE) {
|
||
|
str += mCenter + ", radius = " + mRadiusMeter;
|
||
|
}
|
||
|
|
||
|
return str;
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* @hide
|
||
|
*/
|
||
|
@Override
|
||
|
public boolean equals(Object o) {
|
||
|
if (o == this) {
|
||
|
return true;
|
||
|
}
|
||
|
|
||
|
if (!(o instanceof Circle)) {
|
||
|
return false;
|
||
|
}
|
||
|
|
||
|
Circle c = (Circle) o;
|
||
|
return mCenter.equals(c.mCenter)
|
||
|
&& Double.compare(mRadiusMeter, c.mRadiusMeter) == 0;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* Parse the geometries from the encoded string {@code str}. The string must follow the
|
||
|
* geometry encoding specified by {@link android.provider.Telephony.CellBroadcasts#GEOMETRIES}.
|
||
|
* @hide
|
||
|
*/
|
||
|
@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.
|
||
|
* @hide
|
||
|
*/
|
||
|
@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.
|
||
|
* @hide
|
||
|
*/
|
||
|
@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.
|
||
|
* @hide
|
||
|
*/
|
||
|
@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.
|
||
|
* @hide
|
||
|
*/
|
||
|
public static int sign(double value) {
|
||
|
if (value > EPS) return 1;
|
||
|
if (value < -EPS) return -1;
|
||
|
return 0;
|
||
|
}
|
||
|
}
|