具有GPS坐标的Raycasting算法 [英] Raycasting algorithm with GPS coordinates

问题描述

我使用Google地图制作了一个小应用程序，用于确定输入的地址是否为预定义服务区域的一部分。

用户输入地址， PHP脚本从 Geocoding API 获取纬度/经度，并应用一系列的raycast坐标组成该区域的顶点（从生成的KML文件地图生成）。

问题是这样的：它大部分时间都有效，但有些地址 outside 服务区域错误地报告为合格，而该区域内的其他一些不符合条件。起初，我认为这是谷歌地图的精确问题，但从地理编码服务中的地址生成的坐标准确无误。这可能与公式有关。

这是（它基于我在别处找到的代码）：

  // $ points是一个充满Point对象（顶点）的数组，它包含纬度/长度变量
 // $ ctr只是一个计数器，我们将（$ i = 0，$ j = sizeof（$ points） -  1; $ i< sizeof（$ points）; $ j = $ i ++）{$ b $）来测试它是否为偶数
 b $ p1 = $ points [$ i]; 
 $ p2 = $ points [$ j]; （$ p1-> lat< $ test_point-> lat&& $ p2-> lat> 
 // $ test_point是用户地址
的纬度/ = $ test_point-> lat || $ p2-> lat< $ test_point-> lat&& $ p1-> lat> = $ test_point-> lat）{
 if（ $ p1-> long +（$ test_point-> lat  -  $ p1-> lat）/（$ p2-> lat  -  $ p1-> lat）*（$ p2-> long  -  $ p1- > long）< $ test_point-> long）
 $ ctr ++; 
} 
} 
  

有什么我在这里失踪？我试着自己推导出一个公式，并且我在某种程度上理解了背后的数学，但是使用Google地图的GPS坐标可以吗？

对于错误报道的东西似乎并不是一个真正的模式：我测试了诸如靠近边界的地址或服务区域角落的地址，但在那里没有运气。另外值得注意的是，这个服务区只是一个城市中相对较小的区域，与州或全国范围内没有任何区别。

解决方案

好的......你的第二个if（）不能补偿任何减法可能导致负数的事实;它只会在坐标严格排序时才起作用。

更新：在 http://rosettacode.org/wiki/Ray-casting_algorithmn 有很多用各种语言描述过程的算法（不幸的是，没有PHP的版本）。你的解决方案似乎缺少的是挑选一个保证在多边形之外的点;因为你处理的是经度/方位应该很容易。其次，确保您的多边形已关闭（即，如果Google地图尚未这样做，则从最后一点返回到第一个点）

I'm making a small application with Google maps that determines if an entered address is part of a predefined service region.

The user enters an address, and a PHP script fetches the lat/long from the Geocoding API and applies raycasting with a bunch of coordinates that make up the vertices of the region (taken from a KML file Maps generated).

The problem is this: it works most of the time, but some addresses outside the service region incorrectly report as eligible, while some others inside the region are ineligible. At first I thought this was a precision issue with Google maps, but the coordinates generated from addresses in the Geocoding service are spot-on accurate. It probably has something to do with the formula.

Here it is (it's based off of code I found elsewhere):

// $points is an array full of Point objects (the vertices), which contain lat/long variables
// $ctr is simply a counter that we will test to see if it's even/odd
for ($i = 0, $j = sizeof($points) - 1; $i < sizeof($points); $j = $i++) {
    $p1 = $points[$i];
    $p2 = $points[$j];
    // $test_point is the lat/long pair of the user's address
    if ($p1->lat < $test_point->lat && $p2->lat >= $test_point->lat ||  $p2->lat < $test_point->lat && $p1->lat >= $test_point->lat)  {
        if ($p1->long + ($test_point->lat - $p1->lat)/($p2->lat - $p1->lat)*($p2->long - $p1->long) < $test_point->long)  
            $ctr++;
    }
}

Is there something I'm missing here? I tried deriving a formula on my own and I understand the mathematics behind this to some degree, but is it ok to use GPS coordinates from Google maps with this?

There doesn't seem to be a real pattern as to what is incorrectly reported: I tested for things like addresses close to the boundary or ones in corners of the service area, but no luck there. Also something worth noting is that this service area is just a relatively small region in a city, nothing like state or country-wide areas.

解决方案

Well.... your second if() does not compensate for the fact that any of the subtractions may result in a negative number; it would only work if the coordinates are strictly ordered.

Update: On http://rosettacode.org/wiki/Ray-casting_algorithmn there's a whole bunch of algorithms in various languages that describe the process in detail (unfortunately, there is no version for PHP). What seems to be missing from your solution is picking a point that's guaranteed to be outside of the polygon; since you're dealing with longitude/lattitude that should be easy. Second, make sure your polygon is closed (i.e. go from the last point back to the first, if Google Maps doesn't already do so)

这篇关于具有GPS坐标的Raycasting算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！