How to find the centre of a grid of lines on google maps

I'm struggling with a problem with some GIS information that I am trying to put into a KML file to be used by google maps and google Earth.

I have SQL database containing a number of surveys, which are stored in lines. When all the lines are drawn on the map, they create a grid. What I am trying to do is work out the centre of these 'grids' so that I can put a placemarker reference into the kml to show all the grid locations on a map.

lines is stored in the database like this:

118.718318,-19.015803,0 118.722449,-19.016919,0 118.736223,-开发者_如何学C19.020637,0 118.749936,-19.024023,0 118.763897,-19.027722,0 118.777705,-19.031277,0 118.791416,-19.034826,0 118.805276,-19.038367,0 118.818862,-19.041962,0 118.832862,-19.045582,0 118.846133,-19.049563,0 118.859801,-19.053851,0 118.873322,-19.058145,0 118.887022,-19.062349,0 118.900595,-19.066594,0 118.914066,-19.070839,0 118.927885,-19.075151,0 118.941468,-19.079354,0 118.955064,-19.083658,0 118.968766,-19.087896,0 118.982247,-19.092054,0 118.995795,-19.096324,0 119.009192,-19.100448,0 119.022805,-19.104787,0 119.036414,-19.10893,0 119.049625,-19.113166,0 119.063155,-19.11738,0 119.076626,-19.121563,0 119.090079,-19.125738,0 119.103679,-19.129968,0 119.117009,-19.134168,0 119.130637,-19.138418,0 119.144134,-19.142613,0 119.157749,-19.146767,0 119.171105,-19.151058,0 119.184722,-19.155252,0 119.19844,-19.159399,0 119.211992,-19.163737,0 119.225362,-19.167925,0 119.239109,-19.17218,0 119.252552,-19.176239,0 119.265975,-19.180483,0 119.279718,-19.184901,0 119.2931,-19.189118,0 119.306798,-19.193267,0 119.320561,-19.197631,0 119.33389,-19.201898,0 119.34772,-19.206063,0 119.361322,-19.210282,0 119.374522,-19.214505,0 119.38825,-19.218753,0 119.401948,-19.22299,0 119.415609,-19.227171,0 119.42913,-19.231407,0 119.44269,-19.235604,0 119.456221,-19.240254,0 119.469772,-19.244165,0 119.483159,-19.248341,0 119.496911,-19.252483,0 119.510569,-19.256818,0 119.524034,-19.261068,0 119.537822,-19.265332,0 119.551409,-19.269529,0 119.564744,-19.273764,0 119.578357,-19.277874,0 119.591935,-19.282171,0 119.605472,-19.286424,0 119.619009,-19.290593,0 119.632777,-19.294862,0 119.646394,-19.299146,0 119.660107,-19.303469,0 119.673608,-19.307602,0 119.6872,-19.31182,0 119.700838,-19.31605,0 119.714555,-19.320301,0 119.728202,-19.324615,0 119.741511,-19.328794,0 119.755299,-19.333098,0 119.768776,-19.337206,0 119.782216,-19.341528,0 119.796141,-19.345829,0 119.809691,-19.349879,0 119.822889,-19.354112,0 119.836822,-19.358414,0 119.850077,-19.362618,0 119.864069,-19.366916,0 119.8773,-19.371092,0 119.891263,-19.37536,0 119.904612,-19.379556,0 119.918522,-19.38394,0 119.932101,-19.388108,0 119.945577,-19.392184,0 119.959304,-19.396544,0 119.973042,-19.400809,0 119.986433,-19.405015,0 119.999196,-19.408981,0 120.011959,-19.412946,0 120.014512,-19.41374,0  
118.990393,-19.523933,0 118.990833,-19.522296,0 118.994368,-19.509069,0 118.997911,-19.49589,0 119.001249,-19.48258,0 119.004939,-19.469658,0 119.008437,-19.456658,0 119.01183,-19.443361,0 119.015332,-19.430439,0 119.01869,-19.417491,0 119.022303,-19.40421,0 119.025853,-19.391381,0 119.029387,-19.377966,0 119.032821,-19.365006,0 119.036247,-19.352047,0 119.039935,-19.338701,0 119.043376,-19.325781,0 119.046824,-19.312713,0 119.050223,-19.299634,0 119.053822,-19.286711,0 119.05736,-19.273441,0 119.060722,-19.260467,0 119.064357,-19.247382,0 119.067863,-19.234069,0 119.071361,-19.221168,0 119.07486,-19.208268,0 119.078303,-19.19503,0 119.081721,-19.181915,0 119.085296,-19.169016,0 119.088851,-19.155937,0 119.092245,-19.142828,0 119.095887,-19.12944,0 119.099337,-19.116291,0 119.102821,-19.103421,0 119.106333,-19.090384,0 119.109885,-19.077356,0 119.113395,-19.063976,0 119.116866,-19.050973,0 119.120467,-19.037886,0 119.123751,-19.024888,0 119.127385,-19.011622,0 119.130775,-18.998856,0 119.134503,-18.98547,0 119.13873,-18.9728,0 119.14289,-18.959666,0 119.146076,-18.946541,0 119.149065,-18.933693,0 119.152281,-18.920522,0 119.155414,-18.907033,0 119.158442,-18.894058,0 119.161421,-18.88097,0 119.164632,-18.867484,0 119.167668,-18.854501,0 119.170744,-18.841401,0 119.173939,-18.827999,0 119.17703,-18.815028,0 119.17984,-18.802218,0 119.182902,-18.789334,0 119.186088,-18.776136,0 119.189031,-18.762862,0 119.192179,-18.749824,0 119.19539,-18.7365,0 119.198255,-18.723279,0 119.201476,-18.710134,0 119.204345,-18.69705,0 119.20746,-18.683768,0 119.210555,-18.670607,0 119.213641,-18.657632,0 119.216727,-18.644301,0 119.21982,-18.630956,0 119.223094,-18.617243,0 119.22625,-18.603885,0 119.229368,-18.590534,0 119.232494,-18.577364,0 119.235477,-18.564287,0 119.238496,-18.550953,0 119.241392,-18.53789,0 119.244609,-18.524881,0 119.247551,-18.512017,0 119.250532,-18.498916,0 119.253729,-18.485859,0 119.256428,-18.473845,0 119.259288,-18.461645,0 119.262064,-18.4491,0 119.265024,-18.437048,0 119.267877,-18.424992,0 119.270457,-18.4136,0 119.273429,-18.401305,0 119.276346,-18.388484,0 119.279506,-18.375299,0 119.282307,-18.362197,0 119.285494,-18.34918,0 119.288695,-18.336115,0 119.291008,-18.323772,0 119.294026,-18.310635,0 119.297332,-18.297714,0 119.300499,-18.284553,0 119.303442,-18.271193,0 119.307081,-18.258278,0 119.309945,-18.245139,0 119.313121,-18.232137,0 119.31642,-18.218993,0 119.319499,-18.205722,0 119.322801,-18.192774,0 119.325986,-18.179558,0 119.329173,-18.166332,0 119.33236,-18.15312,0 119.335558,-18.140071,0 119.338761,-18.126696,0 119.342007,-18.113502,0 119.345238,-18.100349,0 119.34808,-18.088343,0 119.350259,-18.079138,0
119.912412,-18.177179,0 119.910223,-18.183223,0 119.905619,-18.195973,0 119.901171,-18.208645,0 119.896641,-18.221452,0 119.89198,-18.234323,0 119.887547,-18.246912,0 119.882922,-18.259925,0 119.878421,-18.272522,0 119.873909,-18.285223,0 119.869264,-18.298194,0 119.864746,-18.310939,0 119.860203,-18.323628,0 119.855692,-18.336434,0 119.850997,-18.349262,0 119.846561,-18.362014,0 119.841916,-18.374866,0 119.837406,-18.387565,0 119.832778,-18.400657,0 119.828259,-18.413072,0 119.82364,-18.426273,0 119.819088,-18.438992,0 119.814546,-18.451696,0 119.810103,-18.464425,0 119.80548,-18.477041,0 119.800935,-18.48989,0 119.796359,-18.502741,0 119.791812,-18.515489,0 119.787314,-18.528536,0 119.782724,-18.540965,0 119.778079,-18.553994,0 119.773558,-18.56663,0 119.768931,-18.57955,0 119.76446,-18.592177,0 119.759793,-18.605255,0 119.755393,-18.617736,0 119.750648,-18.630757,0 119.746479,-18.643371,0 119.741779,-18.656176,0 119.737071,-18.669135,0 119.732572,-18.681798,0 119.727954,-18.694669,0 119.723453,-18.707473,0 119.718855,-18.720259,0 119.714169,-18.733198,0 119.70946,-18.746355,0 119.704998,-18.759005,0 119.700581,-18.771793,0 119.696226,-18.784893,0 119.691577,-18.797373,0 119.68662,-18.810064,0 119.682182,-18.822772,0 119.677711,-18.835621,0 119.672955,-18.848475,0 119.668536,-18.861252,0 119.663856,-18.873901,0 119.659412,-18.88663,0 119.654815,-18.899592,0 119.650185,-18.912338,0 119.645586,-18.925118,0 119.640925,-18.937923,0 119.636617,-18.950753,0 119.631874,-18.963446,0 119.627376,-18.976275,0 119.622845,-18.98893,0 119.618175,-19.001942,0 119.613727,-19.014668,0 119.608878,-19.027398,0 119.60445,-19.039954,0 119.599954,-19.053249,0 119.595066,-19.066008,0 119.590562,-19.078866,0 119.586062,-19.091703,0 119.58155,-19.104199,0 119.576948,-19.116924,0 119.572431,-19.129926,0 119.567449,-19.142699,0 119.563227,-19.155474,0 119.558555,-19.168309,0 119.553956,-19.181053,0 119.549545,-19.193649,0 119.544854,-19.20646,0 119.540133,-19.21929,0 119.535606,-19.232162,0 119.53108,-19.245054,0 119.526509,-19.257772,0 119.522079,-19.270427,0 119.517419,-19.283013,0 119.512755,-19.296126,0 119.508159,-19.309031,0 119.503557,-19.321821,0 119.498966,-19.334394,0 119.494487,-19.347232,0 119.489815,-19.359907,0 119.485201,-19.372962,0 119.48067,-19.385811,0 119.476151,-19.398326,0 119.471526,-19.411138,0 119.466856,-19.424266,0 119.462284,-19.436788,0 119.457752,-19.449628,0 119.452975,-19.462718,0 119.448612,-19.47499,0 119.444249,-19.48726,0 119.439886,-19.499531,0 119.437704,-19.505666,0    

Each point is where a mesasurement took place.

Is there a PHP library or a formula that can be used to work this out without being too intensive?

Thanks

It depends very much on how you define "center". One somewhat sophisticated approach you might like to try:

1. Extract a list of points from the lines
2. Find the convex hull of the points:
3. Find the centroid of the convex hull

The convex hull is simply described as the simplest polygon that passes through some of the points, forming an envelop that encloses all of the points within the polygon. wikipedia has a more rigorous description.

The centroid provides a simple way for finding the "center of gravity" of a polygon. A wikipedia and a nice tutorial provide more information.

Alternatively, a very simple implementation might find the minimum bounding rectangle of the lines, and then find the geometric center of the box. The following code assumes the lines you posted above are represented as strings, and are in an array. I'm no php performance expert, but this algorithm should execute in O(n) asymptotic time:

<?php

$line_strs = array(
"118.718318,-19.015803,0 118.722449,-19.016919,0 118.736223,-19.020637,0 118.749936,-19.024023,0 118.763897,-19.027722,0 118.777705,-19.031277,0",  "118.791416,-19.034826,0 118.805276,-19.038367,0 118.818862,-19.041962,0 118.832862,-19.045582,0 118.846133,-19.049563,0 118.859801,-19.053851,0",  
[SNIP majority of lines...]
"119.448612,-19.47499,0 119.444249,-19.48726,0 119.439886,-19.499531,0 119.437704,-19.505666,0");
$xs = array();
$ys = array();
foreach ($line_strs as $line){
    $points = explode(' ', $line);
    foreach ($points as $pt){
        $xyz = explode(',', $pt);  
        $xs[] = (float)$xyz[0];
        $ys[] = (float)$xyz[1]; 
    }
}
$x_mean = (max($xs) + min($xs)) / 2;
$y_mean = (max($ys) + min($ys)) / 2;
echo "$x_mean,$y_mean\n";
?>

This outputs 119.366415,-18.8015355.

centroids ?

If I have time, I'll edit this answer to include a python implementation

Another very simple answer finds the mean location of all vertices. It favours areas that are densely populated by points. This returns a slightly different answer to the bounding box method. You might want to try them box to see which provides a "better" result for your data.

<?php

$line_strs = array(
"118.718318,-19.015803,0 118.722449,-19.016919,0 118.736223,-19.020637,0 118.749936,-19.024023,0 118.763897,-19.027722,0 118.777705,-19.031277,0",  "118.791416,-19.034826,0 118.805276,-19.038367,0 118.818862,-19.041962,0 118.832862,-19.045582,0 118.846133,-19.049563,0 118.859801,-19.053851,0",  
[SNIP majority of lines...]
"119.448612,-19.47499,0 119.444249,-19.48726,0 119.439886,-19.499531,0 119.437704,-19.505666,0");
$x_sum = 0.0;
$y_sum = 0.0;
$n = 0;
foreach ($line_strs as $line){
    $points = explode(' ', $line);
    foreach ($points as $pt){
        $xyz = explode(',', $pt);  
        $x_sum += (float)$xyz[0];
        $y_sum += (float)$xyz[1]; 
        $n++;
    }
}
$x_mean = $x_sum / $n;
$y_mean = $y_sum / $n;
echo "$x_mean,$y_mean\n";
?>

This outputs 119.402034114,-18.9427670536.