ansaurus

Question

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

Answer 1

A:

centroids ?

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

dassouki 2010-07-08 11:57:02

Answer 2

+1 A:

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

Extract a list of points from the lines
Find the convex hull of the points:
Find the centroid of the convex hull

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.

fmark 2010-07-10 00:17:49

Answer 3

A:

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.

fmark 2010-07-10 00:49:23

Answer 4

A:

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.

fmark 2010-07-10 01:31:31

thanks I'll give these a go thanks.

Grant Collins 2010-07-12 19:46:43

ansaurus

tags:

views:

answers:

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

related questions