Locating a point within a GPS polygon

I don't know if this will be relevant for anyone else, but I was challenged to figure out whether a point occurred within a polygon as drawn within a KML (Google Earth/Google Maps) file.

I had originally tried to implement this in pure MySQL using the spatial extensions but frankly didn't have a lot of luck with that.

What I do is extract out the coordinates from the KML, copy and paste them into a PHP string, and then from there it's entirely automated:

<?php

header('Content-Type: text/xml;charset=UTF-8');

print '<?xml version="1.0" encoding="UTF-8"?>

<Icon>

<href>http://maps.google.com/mapfiles/kml/shapes/caution.png</href>

</Icon>

</IconStyle>

</Style>

<Icon>

<href>http://maps.google.com/mapfiles/kml/shapes/info_circle.png</href>

</Icon>

</IconStyle>

</Style>

/* Do not service */

$in_dns_txt_1 =

-94.987793,49.009052,0.000000

-95.097649,51.124210,0.000000

-94.482422,53.041214,0.000000

-88.945312,56.800869,0.000000

-85.253899,55.528629,0.000000

-82.529289,55.229019,0.000000

-82.001953,53.852520,0.000000

-80.595703,53.041214,0.000000

-80.595703,51.944260,0.000000

-79.562988,51.631657,0.000000

-78.486320,52.268150,0.000000

-79.453117,54.673828,0.000000

-76.640617,55.973789,0.000000

-77.255852,58.170700,0.000000

-78.925781,58.995312,0.000000

-77.607422,59.977001,0.000000

-78.134758,60.973099,0.000000

-78.398430,62.471722,0.000000

-75.410149,62.471722,0.000000

-73.652344,62.552849,0.000000

-71.103508,61.564571,0.000000

-70.048820,61.227951,0.000000

-67.302246,60.392147,0.000000

-69.169922,60.020950,0.000000

-68.378899,58.631210,0.000000

-67.148430,58.447731,0.000000

-64.687500,60.769890,0.000000

-61.699211,57.891491,0.000000

-59.699707,55.899956,0.000000

-57.304688,54.927143,0.000000

-56.074211,53.800652,0.000000

-55.458981,52.268150,0.000000

-55.634762,50.958420,0.000000

-55.722649,50.007729,0.000000

-53.854980,49.823811,0.000000

-53.162842,49.360912,0.000000

-52.470703,46.513515,0.000000

-54.843750,46.860191,0.000000

-56.359863,46.611713,0.000000

-59.567871,47.694973,0.000000

-59.216309,49.353756,0.000000

-57.546387,50.708633,0.000000

-56.601559,51.672550,0.000000

-59.501949,50.345459,0.000000

-64.248039,50.233150,0.000000

-61.699211,49.382370,0.000000

-62.490231,49.037861,0.000000

-60.117180,46.980251,0.000000

-59.677731,46.073231,0.000000

-60.908199,45.274879,0.000000

-61.523430,44.087582,0.000000

-66.621094,44.964790,0.000000

-67.851562,47.338821,0.000000

-69.873039,47.694969,0.000000

-71.279289,45.398449,0.000000

-75.146477,45.089031,0.000000

-76.816399,43.961189,0.000000

-79.453117,44.087582,0.000000

-80.156250,43.004639,0.000000

-82.089844,42.098221,0.000000

-81.738281,43.516682,0.000000

-82.089844,45.151051,0.000000

-83.320312,46.377251,0.000000

-86.132812,47.694969,0.000000

-87.978508,48.574791,0.000000

-89.121094,48.429199,0.000000

-90.878906,48.195389,0.000000

-94.987793,49.009052,0.000000

function poly_string_into_coordinate_arrays($instring)

{

$x_array = array();

$y_array = array();

$lines = preg_split('/\n/', $instring);

foreach($lines as $l)

{

$fields = preg_split('/,/', $l);

if(count($fields) == 3)

{

$x = $fields[0];

$y = $fields[1];

$z = $fields[2];

$x_array[] = $x;

$y_array[] = $y;

}

return array(

'polyx' => $x_array,

'polyy' => $y_array,

);

}

$in_dns_1 = poly_string_into_coordinate_arrays($in_dns_txt_1);

function pointInPolygon($out,$x,$y)

{

$polyX = $out['polyx'];

$polyY = $out['polyy'];

$polySides = count($polyX);

$j = $polySides-1 ;

$oddNodes = 0;

for ($i=0; $i<$polySides; $i++) {

if ($polyY[$i]<$y && $polyY[$j]>=$y

|| $polyY[$j]<$y && $polyY[$i]>=$y) {

if ($polyX[$i]+($y-$polyY[$i])/($polyY[$j]-$polyY[$i])*($polyX[$j]-$polyX[$i])<$x) {

$oddNodes=!$oddNodes; }}

$j=$i; }

return $oddNodes;

}

$mysqli = new mysqli("localhost", "root", "rootpassword", "geolocatedb");

$sql = "SELECT Postal,Latitude,Longitude FROM canada GROUP BY City ORDER BY RAND()*MAX(id) LIMIT 1000";

if($result = $mysqli->query($sql))

{

while($row = $result->fetch_array(MYSQLI_ASSOC))

{

$style = "#unmatchedpin";

if(pointInPolygon($in_dns_1, $row["Longitude"], $row["Latitude"]))

{

$style = "#foundpin";

}

printf('

</Placemark>' . "\n"

, $row["Postal"], $row["Postal"], $row["Longitude"], $row["Latitude"], $style);

}

</Document>

</kml>