具有 GPS 坐标的光线投射算法

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)