border around geo coordinates

Question

I have a group of geo coordinates displaying on Google maps. How would one determine the outermost points to build a polygon border containing all the points?

I know how to create a polygon already. But I need to determine all the exterior points.

All the geo coordinates are in a mysql db. I would like to use PHP to separate just the coordinates I need to create the polygon.

I am not looking how to do a bounding box.

Answer 1

You can use a delaunay triangulation and connect all vertex on the convex hull, I.e. find vertexes not with a neighbor. You can download my php class convex hull @ phpclasses.org. You can also look at my website http://www.phpdevpad.de/geofence as an example for a delaunay triangulation and a concave hull based on lat-lng pairs. You can use my example no. 5 to find the convex-hull of lat-lng pairs:

require_once("convex-hull.php"); 
//example5 
$mapPadding  = 100; 
$mapWidth    = 500; 
$mapHeight   = 500; 
$mapLonLeft  =1000; 
$mapLatBottom=1000; 
$mapLonRight =   0; 
$mapLatTop   =   0; 
$set=array(); 
$geocoord = array ("8.6544487,50.1005233", 
                   "8.7839489,50.0907496", 
                   "8.1004734,50.2002273", 
                   "8.4117234,50.0951493", 
                   "8.3508367,49.4765982", 
                   "9.1828630,48.7827027", 
                   "9.1686483,48.7686426", 
                   "9.2118466,48.7829101", 
                   "8.9670738,48.9456327"); 

foreach ($geocoord as $key => $arr) 
{ 
    list($lon,$lat) = explode(",",$arr); 
    $mapLonLeft = min($mapLonLeft,$lon); 
    $mapLonRight = max($mapLonRight,$lon); 
    $mapLatBottom = min($mapLatBottom,$lat); 
    $mapLatTop = max($mapLatTop,$lat); 
    $set[]=array($lon,$lat); 
} 

$mapLonDelta = $mapLonRight-$mapLonLeft; 
$mapLatDelta = $mapLatTop-$mapLatBottom; 
$mapLatTopY=$mapLatTop*(M_PI/180); 
$worldMapWidth=(($mapWidth/$mapLonDelta)*360)/(2*M_PI); 
$LatBottomSin=min(max(sin($mapLatBottom*(M_PI/180)),-0.9999),0.9999); 
$mapOffsetY=$worldMapWidth/2 * log((1+$LatBottomSin)/(1-$LatBottomSin)); 
$LatTopSin=min(max(sin($mapLatTop*(M_PI/180)),-0.9999),0.9999); 
$mapOffsetTopY=$worldMapWidth/2 * log((1+$LatTopSin)/(1-$LatTopSin)); 
$mapHeightD=$mapOffsetTopY-$mapOffsetY; 
$mapRatioH=$mapHeight/$mapHeightD; 
$newWidth=$mapWidth*($mapHeightD/$mapHeight); 
$mapRatioW=$mapWidth/$newWidth; 

foreach ($set as $key => $arr) 
{ 
    list($lon,$lat) = $arr; 
    $tx = ($lon - $mapLonLeft) * ($newWidth/$mapLonDelta)*$mapRatioW; 
    $f = sin($lat*M_PI/180); 
    $ty = ($mapHeightD-(($worldMapWidth/2 * log((1+$f)/(1-$f)))-$mapOffsetY)); 
} 

$chull=new convexhull(); 
$chull->main($set,$mapWidth,$mapHeightD); 

Then the convex-hull is in the array and you need to remove the vertex from the supertriangle and check if the vertex is in the lat-lng pairs:

foreach ($chull->convexhull as $key => $arr)
      {
     foreach ($arr as $ikey => $iarr)
     {
        list($x1,$y1,$x2,$y2) = $iarr;
        if (abs($x1) != SUPER_TRIANGLE && abs($y1) != SUPER_TRIANGLE && abs($x2) != SUPER_TRIANGLE && abs($y2) != SUPER_TRIANGLE)
        {
           $ok=0;
           foreach ($chull->pointset as $iikey => $iiarr)
           {
          if ($iiarr==array($x1,$y1))
          {
             $ok=1;
          }
           }
           if ($ok)
           {
          solution[]=set[$iikey];  
           }
        }
     }
      }