3

我正在使用谷歌地图制作一个小型应用程序，以确定输入的地址是否是预定义服务区域的一部分。

用户输入一个地址，PHP 脚本从地理编码 API中获取纬度/经度，并使用构成该区域顶点的一组坐标应用光线投射（取自生成的 KML 文件地图）。

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

在这里（它基于我在其他地方找到的代码）：

// $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++;
    }
}

我在这里缺少什么吗？我尝试自己推导出一个公式，并且在某种程度上理解了这背后的数学原理，但是可以使用谷歌地图中的 GPS 坐标吗？

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

4

3 回答 3

2

好吧....您的第二个 if() 不能弥补任何减法都可能导致负数的事实；只有当坐标被严格排序时它才会起作用。

更新：在http://rosettacode.org/wiki/Ray-casting_algorithmn上有一大堆各种语言的算法详细描述了这个过程（不幸的是，没有 PHP 版本）。您的解决方案中似乎缺少的是选择一个保证在多边形之外的点；因为您正在处理应该很容易的经度/纬度。其次，确保你的多边形是封闭的（即从最后一个点回到第一个点，如果谷歌地图还没有这样做的话）

于 2013-01-04T03:31:34.807 回答
0

There is a bug with this algorithm, when the ray is tangent to the shape. Just add an epsilon to the test point's latitude when it might happen (line 3 of Ilmari's code):

if ($test_point->lat == $p0->lat)
    $test_point->lat += 0.0000000001;

Also see http://rosettacode.org/wiki/Ray-casting_algorithm (corrected URL).

Thanks.

于 2013-08-28T06:10:39.407 回答
0

假设$points数组包含按顺时针（或逆时针顺序）描述覆盖区域的多边形的角，您的代码对我来说看起来是正确的。基本上，它计算的是与从给定点到第 180 条子午线正东绘制的线相交的多边形边的数量。

为了清楚起见，我可能会像这样重写它：

$p0 = end($points);
foreach ( $points as $p1 ) {
    // ignore edges of constant latitude (yes, this is correct!)
    if ( $p0->lat != $p1->lat ) {
        // scale latitude of $test_point so that $p0 maps to 0 and $p1 to 1:
        $interp = ($test_point->lat - $p0->lat) / ($p1->lat - $p0->lat);
        // does the edge intersect the latitude of $test_point?
        // (note: use >= and < to avoid double-counting exact endpoint hits)
        if ( $interp >= 0 && $interp < 1 ) {
            // longitude of the edge at the latitude of the test point:
            // (could use fancy spherical interpolation here, but for small
            // regions linear interpolation should be fine)
            $long = $interp * $p1->long + (1 - $interp) * $p0->long;
            // is the intersection east of the test point?
            if ( $long < $test_point->long ) {
                // if so, count it:
                $ctr++;
            }
        }
    }
    $p0 = $p1;
}

请注意，如果区域边界越过 180 度子午线，此代码将以各种有趣的方式中断，因此如果您在太平洋中部有任何服务区域，请不要使用它。

如果您仍然遇到问题，请尝试$points在地图上绘制数组所描述的多边形；您可能会发现它看起来不像您想象的那样，例如，如果某些点以错误的顺序列出。

于 2013-01-08T01:08:23.990 回答