php - tiempo - Algoritmo de Raycasting con coordenadas GPS

obtener direccion con coordenadas android studio

Question

Estoy haciendo una pequeña aplicación con Google Maps que determina si una dirección ingresada es parte de una región de servicio predefinida.

El usuario ingresa una dirección, y una secuencia de comandos PHP extrae el lat / long de la API de geocodificación y aplica el raycasting con un conjunto de coordenadas que componen los vértices de la región (tomado de un archivo KML generado por Maps).

El problema es este: funciona la mayor parte del tiempo, pero algunas direcciones fuera de la región de servicio informan incorrectamente como elegibles, mientras que otras dentro de la región no son elegibles. Al principio pensé que esto era un problema de precisión con los mapas de Google, pero las coordenadas generadas a partir de direcciones en el servicio de codificación geográfica son precisas. Probablemente tiene algo que ver con la fórmula.

Aquí está (está basado en el código que encontré en otra parte):

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

¿Hay algo que me falta aquí? Intenté derivar una fórmula por mi cuenta y entiendo las matemáticas detrás de esto hasta cierto punto, pero ¿está bien usar las coordenadas de GPS de los mapas de Google con esto?

No parece haber un patrón real en cuanto a lo que se informa incorrectamente: probé cosas como las direcciones cercanas al límite o las que están en las esquinas del área de servicio, pero no tuve suerte allí. También algo que vale la pena señalar es que esta área de servicio es solo una región relativamente pequeña en una ciudad, nada que ver con áreas estatales o de todo el país.

Answer 1

Bueno ... tu segundo if () no compensa el hecho de que cualquiera de las restas pueda dar como resultado un número negativo; solo funcionaría si las coordenadas están estrictamente ordenadas.

Actualización: en http://rosettacode.org/wiki/Ray-casting_algorithmn hay un montón de algoritmos en varios idiomas que describen el proceso en detalle (lamentablemente, no hay una versión para PHP). Lo que parece faltar en su solución es elegir un punto que esté garantizado fuera del polígono; ya que se trata de longitud / latitud que debería ser fácil. En segundo lugar, asegúrese de que su polígono esté cerrado (es decir, vaya desde el último punto al primero, si Google Maps no lo hace)

Answer 2

Suponiendo que la matriz $points contiene las esquinas de un polígono que describe el área de cobertura en sentido horario (o en sentido antihorario), su código me parece correcto. Básicamente, está contando el número de bordes del polígono que se cruzan con una línea trazada hacia el este desde el punto dado hasta el meridiano 180º.

Tal vez lo reescribiera así, solo por claridad:

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

Tenga en cuenta que este código se dividirá en todo tipo de formas interesantes si el límite de la región cruza el meridiano 180º, por lo que no lo use si tiene regiones de servicio en el medio del Océano Pacífico.

Si sigues teniendo problemas, intenta trazar el polígono descrito por la matriz $points en un mapa; puede descubrir que no se parece a lo que pensaba, por ejemplo, si algunos puntos se enumeran en el orden incorrecto.

Answer 3

Hay un error con este algoritmo, cuando el rayo es tangente a la forma. Simplemente agregue un épsilon a la latitud del punto de prueba cuando ocurra (línea 3 del código de Ilmari):

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

También vea http://rosettacode.org/wiki/Ray-casting_algorithm (URL corregida).

Gracias.