Howto‎ > ‎

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"?>
<kml xmlns="http://www.opengis.net/kml/2.2" xmlns:gx="http://www.google.com/kml/ext/2.2" xmlns:kml="http://www.opengis.net/kml/2.2" xmlns:atom="http://www.w3.org/2005/Atom">
<Document>

<Style id="unmatchedpin">
<IconStyle id="unmatchedpinicon">
     <Icon>
       <href>http://maps.google.com/mapfiles/kml/shapes/caution.png</href>
       <scale>1.0</scale>
     </Icon>
   </IconStyle>
   <LabelStyle><scale>0</scale></LabelStyle>
</Style>

<Style id="matchedpin">
<IconStyle id="matchedpinicon">
     <Icon>
       <href>http://maps.google.com/mapfiles/kml/shapes/info_circle.png</href>
       <scale>1.0</scale>
     </Icon>
   </IconStyle>
   <LabelStyle><scale>0</scale></LabelStyle>
</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 id="%s">
<name>%s</name>
<Point><coordinates>%f,%f,0</coordinates></Point>
<styleUrl>%s</styleUrl>
</Placemark>' . "\n"
, $row["Postal"], $row["Postal"], $row["Longitude"], $row["Latitude"], $style);
        }
}

?>
</Document>
</kml>