У меня есть несколько координат долготы и широты, которые составляют многоугольную зону. У меня также есть координата долготы и широты, чтобы определить положение транспортного средства. Как проверить, что транспортное средство находится внутри полигональной зоны?
Это по существу проблема Точки в многоугольнике на сфере. Вы можете изменить алгоритм преобразования лучей так, чтобы он использовал дуги больших кругов вместо сегментов линии.
В качестве альтернативы, если координаты и транспортное средство находятся достаточно близко друг к другу, а не где-нибудь рядом с полюсами или международной линией даты, вы можете притворяться, что земля плоская, и использовать долготу и ширину как простые координаты x и y. Таким образом, вы можете использовать алгоритм литья лучей с простыми сегментами линии. Это предпочтительнее, если вам не нравится геометрия без евклидова, но у вас будут некоторые искажения вокруг границ ваших полигонов, поскольку дуги будут искажены.
EDIT: Немного больше о геометрии на сфере.
Большой круг может быть идентифицирован вектором, лежащим перпендикулярно плоскости, на которой лежит круг (AKA, нормальный вектор )
class Vector{ double x; double y; double z; }; class GreatCircle{ Vector normal; } Любые две координаты долготы и долготы, которые не являются антиподами, разделяют ровно один большой круг. Чтобы найти этот большой круг, преобразуйте координаты в линии, проходящие через центр земли. Перекрестное произведение этих двух линий является нормальным вектором большого круга координат.
//arbitrarily defining the north pole as (0,1,0) and (0'N, 0'E) as (1,0,0) //lattidues should be in [-90, 90] and longitudes in [-180, 180] //You'll have to convert South lattitudes and East longitudes into their negative North and West counterparts. Vector lineFromCoordinate(Coordinate c){ Vector ret = new Vector(); //given: //tan(lat) == y/x //tan(long) == z/x //the Vector has magnitude 1, so sqrt(x^2 + y^2 + z^2) == 1 //rearrange some symbols, solving for x first... ret.x = 1.0 / math.sqrt(tan(c.lattitude)^2 + tan(c.longitude)^2 + 1); //then for y and z ret.y = ret.x * tan(c.lattitude); ret.z = ret.x * tan(c.longitude); return ret; } Vector Vector::CrossProduct(Vector other){ Vector ret = new Vector(); ret.x = this.y * other.z - this.z * other.y; ret.y = this.z * other.x - this.x * other.z; ret.z = this.x * other.y - this.y * other.x; return ret; } GreatCircle circleFromCoordinates(Coordinate a, Coordinate b){ Vector a = lineFromCoordinate(a); Vector b = lineFromCoordinate(b); GreatCircle ret = new GreatCircle(); ret.normal = a.CrossProdct(b); return ret; }
Два больших круга пересекаются в двух точках на сфере. Перекрестное произведение кругов образует вектор, проходящий через одну из этих точек. Антипод этого вектора проходит через другую точку.
Vector intersection(GreatCircle a, GreatCircle b){ return a.normal.CrossProduct(b.normal); } Vector antipode(Vector v){ Vector ret = new Vector(); ret.x = -vx; ret.y = -vy; ret.z = -vz; return ret; }
Сегмент большого круга может быть представлен векторами, проходящими через начальную и конечную точки сегмента.
class GreatCircleSegment{ Vector start; Vector end; Vector getNormal(){return start.CrossProduct(end);} GreatCircle getWhole(){return new GreatCircle(this.getNormal());} }; GreatCircleSegment segmentFromCoordinates(Coordinate a, Coordinate b){ GreatCircleSegment ret = new GreatCircleSegment(); ret.start = lineFromCoordinate(a); ret.end = lineFromCoordinate(b); return ret; }
Вы можете измерить размер дуги большого сегмента круга или угол между любыми двумя векторами, используя точечный продукт .
double Vector::DotProduct(Vector other){ return this.x*other.x + this.y*other.y + this.z*other.z; } double Vector::Magnitude(){ return math.sqrt(pow(this.x, 2) + pow(this.y, 2) + pow(this.z, 2)); } //for any two vectors `a` and `b`, //a.DotProduct(b) = a.magnitude() * b.magnitude() * cos(theta) //where theta is the angle between them. double angleBetween(Vector a, Vector b){ return math.arccos(a.DotProduct(b) / (a.Magnitude() * b.Magnitude())); }
Вы можете проверить, если сегмент большого круга a пересекает большой круг b :
c , пересечение целого большого круга и b . d , антипод c . c лежит между a.start и a.end , или d лежит между a.start и a.end , то a пересекается с b . //returns true if Vector x lies between Vectors a and b. //note that this function only gives sensical results if the three vectors are coplanar. boolean liesBetween(Vector x, Vector a, Vector b){ return angleBetween(a,x) + angleBetween(x,b) == angleBetween(a,b); } bool GreatCircleSegment::Intersects(GreatCircle b){ Vector c = intersection(this.getWhole(), b); Vector d = antipode(c); return liesBetween(c, this.start, this.end) or liesBetween(d, this.start, this.end); }
Два больших сегмента круга a и b пересекаются, если:
a пересекается с целым большим кругом b b пересекается с целым большим кругом bool GreatCircleSegment::Intersects(GreatCircleSegment b){ return this.Intersects(b.getWhole()) and b.Intersects(this.getWhole()); }
Теперь вы можете построить свой многоугольник и подсчитать, сколько раз ваша эталонная линия проходит над ним.
bool liesWithin(Array<Coordinate> polygon, Coordinate pointNotLyingInsidePolygon, Coordinate vehiclePosition){ GreatCircleSegment referenceLine = segmentFromCoordinates(pointNotLyingInsidePolygon, vehiclePosition); int intersections = 0; //iterate through all adjacent polygon vertex pairs //we iterate i one farther than the size of the array, because we need to test the segment formed by the first and last coordinates in the array for(int i = 0; i < polygon.size + 1; i++){ int j = (i+1) % polygon.size; GreatCircleSegment polygonEdge = segmentFromCoordinates(polygon[i], polygon[j]); if (referenceLine.Intersects(polygonEdge)){ intersections++; } } return intersections % 2 == 1; }