Sau*_*aul 32 math gps geolocation geospatial coordinates
如标题中所述,目标是有一种方法来检测给定的GPS坐标是否落在多边形内.
多边形本身可以是凸面或凹面.它被定义为一组边矢量和该多边形内的已知点.每个边缘矢量进一步由四个坐标定义,这四个坐标是各个尖端点的纬度和经度以及相对于起始点的方位.
StackOverflow上有一些与此类似的问题,但是它们仅以一般术语和2D平面描述解决方案,而我正在寻找支持WGS 84中纬度/经度对定义的多边形的现有实现.
进行此类碰撞测试的API或服务是什么？
Eri*_*ski 38
这是一个java程序,它使用一个函数,如果在由纬度/经度列表定义的多边形内找到纬度/经度,则返回true,并显示佛罗里达州的状态.
我不确定它是否涉及纬度/长度GPS系统不是x/y坐标平面的事实.对于我的用途,我已经证明它有效(我想如果你在边界框中指定了足够的点,它会消除地球是一个球体的效果,并且地球上两点之间的直线不是箭头直线.
首先指定构成多边形角点的点,它可以有凹角和凸角.我在下面使用的坐标追踪佛罗里达州的周长.
方法coordinate_is_inside_polygon利用我不太了解的算法.以下是我得到它的来源的官方解释:
"...由Philippe Reverdy转发的解决方案是计算测试点和构成多边形的每对点之间的角度之和.如果此总和为2pi,则该点为内部点,如果为0则为点这是一个外部点.这也适用于带有孔的多边形,给定多边形由一条路径组成,该路径由进入和离开孔的重合边组成,这是许多CAD软件包中的常见做法.
我的单元测试显示它确实可靠地工作,即使边界框是'C'形状或甚至形状像圆环.(我的单元测试测试佛罗里达州内的许多点,并确保该函数返回true.我在世界其他地方选择了一些坐标,并确保它返回false.我选择世界各地可能会混淆它的地方.
如果多边形边界框穿过赤道,本初子午线或坐标从-180 - > 180,-90 - > 90变化的任何区域,我不确定这是否有效.或者你的多边形环绕北方的地球/南极.对我来说,我只需要它在佛罗里达州的周边工作.如果你必须定义一个横跨地球或穿过这些线的多边形,你可以通过制作两个多边形来解决它,一个代表子午线一侧的区域,另一个代表另一侧的区域并测试你的观点在这两点之一.
这是我找到这个算法的地方:确定一个点是否位于多边形的内部 - 解决方案2
为自己运行它来仔细检查它.
把它放在一个名为Runner.java的文件中
import java.util.ArrayList;
public class Runner
{
public static double PI = 3.14159265;
public static double TWOPI = 2*PI;
public static void main(String[] args) {
ArrayList<Double> lat_array = new ArrayList<Double>();
ArrayList<Double> long_array = new ArrayList<Double>();
//This is the polygon bounding box, if you plot it,
//you'll notice it is a rough tracing of the parameter of
//the state of Florida starting at the upper left, moving
//clockwise, and finishing at the upper left corner of florida.
ArrayList<String> polygon_lat_long_pairs = new ArrayList<String>();
polygon_lat_long_pairs.add("31.000213,-87.584839");
//lat/long of upper left tip of florida.
polygon_lat_long_pairs.add("31.009629,-85.003052");
polygon_lat_long_pairs.add("30.726726,-84.838257");
polygon_lat_long_pairs.add("30.584962,-82.168579");
polygon_lat_long_pairs.add("30.73617,-81.476441");
//lat/long of upper right tip of florida.
polygon_lat_long_pairs.add("29.002375,-80.795288");
polygon_lat_long_pairs.add("26.896598,-79.938355");
polygon_lat_long_pairs.add("25.813738,-80.059204");
polygon_lat_long_pairs.add("24.93028,-80.454712");
polygon_lat_long_pairs.add("24.401135,-81.817017");
polygon_lat_long_pairs.add("24.700927,-81.959839");
polygon_lat_long_pairs.add("24.950203,-81.124878");
polygon_lat_long_pairs.add("26.0015,-82.014771");
polygon_lat_long_pairs.add("27.833247,-83.014527");
polygon_lat_long_pairs.add("28.8389,-82.871704");
polygon_lat_long_pairs.add("29.987293,-84.091187");
polygon_lat_long_pairs.add("29.539053,-85.134888");
polygon_lat_long_pairs.add("30.272352,-86.47522");
polygon_lat_long_pairs.add("30.281839,-87.628784");
//Convert the strings to doubles.
for(String s : polygon_lat_long_pairs){
lat_array.add(Double.parseDouble(s.split(",")[0]));
long_array.add(Double.parseDouble(s.split(",")[1]));
}
//prints TRUE true because the lat/long passed in is
//inside the bounding box.
System.out.println(coordinate_is_inside_polygon(
25.7814014D,-80.186969D,
lat_array, long_array));
//prints FALSE because the lat/long passed in
//is Not inside the bounding box.
System.out.println(coordinate_is_inside_polygon(
25.831538D,-1.069338D,
lat_array, long_array));
}
public static boolean coordinate_is_inside_polygon(
double latitude, double longitude,
ArrayList<Double> lat_array, ArrayList<Double> long_array)
{
int i;
double angle=0;
double point1_lat;
double point1_long;
double point2_lat;
double point2_long;
int n = lat_array.size();
for (i=0;i<n;i++) {
point1_lat = lat_array.get(i) - latitude;
point1_long = long_array.get(i) - longitude;
point2_lat = lat_array.get((i+1)%n) - latitude;
//you should have paid more attention in high school geometry.
point2_long = long_array.get((i+1)%n) - longitude;
angle += Angle2D(point1_lat,point1_long,point2_lat,point2_long);
}
if (Math.abs(angle) < PI)
return false;
else
return true;
}
public static double Angle2D(double y1, double x1, double y2, double x2)
{
double dtheta,theta1,theta2;
theta1 = Math.atan2(y1,x1);
theta2 = Math.atan2(y2,x2);
dtheta = theta2 - theta1;
while (dtheta > PI)
dtheta -= TWOPI;
while (dtheta < -PI)
dtheta += TWOPI;
return(dtheta);
}
public static boolean is_valid_gps_coordinate(double latitude,
double longitude)
{
//This is a bonus function, it's unused, to reject invalid lat/longs.
if (latitude > -90 && latitude < 90 &&
longitude > -180 && longitude < 180)
{
return true;
}
return false;
}
}
恶魔魔法需要经过单元测试.把它放在一个名为MainTest.java的文件中,以验证它是否适合您
import java.util.ArrayList;
import org.junit.Test;
import static org.junit.Assert.*;
public class MainTest {
@Test
public void test_lat_long_in_bounds(){
Runner r = new Runner();
//These make sure the lat/long passed in is a valid gps
//lat/long coordinate. These should be valid.
assertTrue(r.is_valid_gps_coordinate(25, -82));
assertTrue(r.is_valid_gps_coordinate(-25, -82));
assertTrue(r.is_valid_gps_coordinate(25, 82));
assertTrue(r.is_valid_gps_coordinate(-25, 82));
assertTrue(r.is_valid_gps_coordinate(0, 0));
assertTrue(r.is_valid_gps_coordinate(89, 179));
assertTrue(r.is_valid_gps_coordinate(-89, -179));
assertTrue(r.is_valid_gps_coordinate(89.999, 179));
//If your bounding box crosses the equator or prime meridian,
then you have to test for those situations still work.
}
@Test
public void realTest_for_points_inside()
{
ArrayList<Double> lat_array = new ArrayList<Double>();
ArrayList<Double> long_array = new ArrayList<Double>();
ArrayList<String> polygon_lat_long_pairs = new ArrayList<String>();
//upper left tip of florida.
polygon_lat_long_pairs.add("31.000213,-87.584839");
polygon_lat_long_pairs.add("31.009629,-85.003052");
polygon_lat_long_pairs.add("30.726726,-84.838257");
polygon_lat_long_pairs.add("30.584962,-82.168579");
polygon_lat_long_pairs.add("30.73617,-81.476441");
//upper right tip of florida.
polygon_lat_long_pairs.add("29.002375,-80.795288");
polygon_lat_long_pairs.add("26.896598,-79.938355");
polygon_lat_long_pairs.add("25.813738,-80.059204");
polygon_lat_long_pairs.add("24.93028,-80.454712");
polygon_lat_long_pairs.add("24.401135,-81.817017");
polygon_lat_long_pairs.add("24.700927,-81.959839");
polygon_lat_long_pairs.add("24.950203,-81.124878");
polygon_lat_long_pairs.add("26.0015,-82.014771");
polygon_lat_long_pairs.add("27.833247,-83.014527");
polygon_lat_long_pairs.add("28.8389,-82.871704");
polygon_lat_long_pairs.add("29.987293,-84.091187");
polygon_lat_long_pairs.add("29.539053,-85.134888");
polygon_lat_long_pairs.add("30.272352,-86.47522");
polygon_lat_long_pairs.add("30.281839,-87.628784");
for(String s : polygon_lat_long_pairs){
lat_array.add(Double.parseDouble(s.split(",")[0]));
long_array.add(Double.parseDouble(s.split(",")[1]));
}
Runner r = new Runner();
ArrayList<String> pointsInside = new ArrayList<String>();
pointsInside.add("30.82112,-87.255249");
pointsInside.add("30.499804,-86.8927");
pointsInside.add("29.96826,-85.036011");
pointsInside.add("30.490338,-83.981323");
pointsInside.add("29.825395,-83.344116");
pointsInside.add("30.215406,-81.828003");
pointsInside.add("29.299813,-82.728882");
pointsInside.add("28.540135,-81.212769");
pointsInside.add("27.92065,-82.619019");
pointsInside.add("28.143691,-81.740113");
pointsInside.add("27.473186,-80.718384");
pointsInside.add("26.769154,-81.729126");
pointsInside.add("25.853292,-80.223999");
pointsInside.add("25.278477,-80.707398");
pointsInside.add("24.571105,-81.762085"); //bottom tip of keywest
pointsInside.add("24.900388,-80.663452");
pointsInside.add("24.680963,-81.366577");
for(String s : pointsInside)
{
assertTrue(r.coordinate_is_inside_polygon(
Double.parseDouble(s.split(",")[0]),
Double.parseDouble(s.split(",")[1]),
lat_array, long_array));
}
}
@Test
public void realTest_for_points_outside()
{
ArrayList<Double> lat_array = new ArrayList<Double>();
ArrayList<Double> long_array = new ArrayList<Double>();
ArrayList<String> polygon_lat_long_pairs = new ArrayList<String>();
//upper left tip, florida.
polygon_lat_long_pairs.add("31.000213,-87.584839");
polygon_lat_long_pairs.add("31.009629,-85.003052");
polygon_lat_long_pairs.add("30.726726,-84.838257");
polygon_lat_long_pairs.add("30.584962,-82.168579");
polygon_lat_long_pairs.add("30.73617,-81.476441");
//upper right tip, florida.
polygon_lat_long_pairs.add("29.002375,-80.795288");
polygon_lat_long_pairs.add("26.896598,-79.938355");
polygon_lat_long_pairs.add("25.813738,-80.059204");
polygon_lat_long_pairs.add("24.93028,-80.454712");
polygon_lat_long_pairs.add("24.401135,-81.817017");
polygon_lat_long_pairs.add("24.700927,-81.959839");
polygon_lat_long_pairs.add("24.950203,-81.124878");
polygon_lat_long_pairs.add("26.0015,-82.014771");
polygon_lat_long_pairs.add("27.833247,-83.014527");
polygon_lat_long_pairs.add("28.8389,-82.871704");
polygon_lat_long_pairs.add("29.987293,-84.091187");
polygon_lat_long_pairs.add("29.539053,-85.134888");
polygon_lat_long_pairs.add("30.272352,-86.47522");
polygon_lat_long_pairs.add("30.281839,-87.628784");
for(String s : polygon_lat_long_pairs)
{
lat_array.add(Double.parseDouble(s.split(",")[0]));
long_array.add(Double.parseDouble(s.split(",")[1]));
}
Runner r = new Runner();
ArrayList<String> pointsOutside = new ArrayList<String>();
pointsOutside.add("31.451159,-87.958374");
pointsOutside.add("31.319856,-84.607544");
pointsOutside.add("30.868282,-84.717407");
pointsOutside.add("31.338624,-81.685181");
pointsOutside.add("29.452991,-80.498657");
pointsOutside.add("26.935783,-79.487915");
pointsOutside.add("25.159207,-79.916382");
pointsOutside.add("24.311058,-81.17981");
pointsOutside.add("25.149263,-81.838989");
pointsOutside.add("27.726326,-83.695679");
pointsOutside.add("29.787263,-87.024536");
pointsOutside.add("29.205877,-62.102052");
pointsOutside.add("14.025751,-80.690919");
pointsOutside.add("29.029276,-90.805666");
pointsOutside.add("-12.606032,-70.151369");
pointsOutside.add("-56.520716,-172.822269");
pointsOutside.add("-75.89666,9.082024");
pointsOutside.add("-24.078567,142.675774");
pointsOutside.add("84.940737,177.480462");
pointsOutside.add("47.374545,9.082024");
pointsOutside.add("25.831538,-1.069338");
pointsOutside.add("0,0");
for(String s : pointsOutside){
assertFalse(r.coordinate_is_inside_polygon(
Double.parseDouble(s.split(",")[0]),
Double.parseDouble(s.split(",")[1]), lat_array, long_array));
}
}
}
//The list of lat/long inside florida bounding box all return true.
//The list of lat/long outside florida bounding box all return false.
我使用eclipse IDE来使用java 1.6.0来运行java.对我来说,所有单元测试都通过了.您需要在类路径中包含junit 4 jar文件或将其导入Eclipse.
我的想法与shab相似(他的提议称为Ray-Casting Algorithm),但有像Spacedman这样的第二个想法:
...但是所有几何体都必须在球坐标系中重做......
我实现并测试了数学上正确的方法,即交叉大圆并确定两个交叉点中的一个是否在两个弧上.(注意:我按照这里描述的步骤进行了操作,但是我发现了几个错误:sign在步骤6结束时(之前arcsin)缺少该功能,最后的测试是数字垃圾(因为减法条件很差);请使用而不是L_1T >= max(L_1a, L_1b)测试S1是否在第一个弧等上)
这也是非常缓慢和数字噩梦(评估约100个三角函数,等等); 事实证明它不适用于我们的嵌入式系统.
但是有一个技巧:如果您考虑的区域足够小,只需对每个点进行标准的制图投影,例如球形墨卡托投影:
// latitude, longitude in radians
x = longitude;
y = log(tan(pi/4 + latitude/2));
然后,您可以应用光线投射,此函数检查弧的交点:
public bool ArcsIntersecting(double x1, double y1, double x2, double y2,
double x3, double y3, double x4, double y4)
{
double vx1 = x2 - x1;
double vy1 = y2 - y1;
double vx2 = x4 - x3;
double vy2 = y4 - y3;
double denom = vx1 * vy2 - vx2 * vy1;
if (denom == 0) { return false; } // edges are parallel
double t1 = (vx2 * (y1 - y3) - vy2 * (x1 - x3)) / denom;
double t2;
if (vx2 != 0) { t2 = (x1 - x3 + t1 * vx1) / vx2; }
else if (vy2 != 0) { t2 = (y1 - y3 + t1 * vy1) / vy2; }
else { return false; } // edges are matching
return min(t1, t2) >= 0 && max(t1, t2) <= 1;
}
如果球体上有 WGS84 坐标，那么您的多边形将球体分为两个区域 - 我们如何知道哪个区域在多边形“内部”，哪个区域在多边形“外部”？这个问题本质上是没有意义的！
例如，假设多边形形成了赤道线 - 北半球是“内”还是“外”？