Re: Points within polygons

[Bjorn Brala]

I think i did something similar to you, i use the bounding box of a map view to get items from within that view. But i use intersects.

WHERE Intersects(geofield, GeomFromText("Linestring('. $this->fNElng .' ' . $this->fNElat . ', ' . $this->fSWlng . ' ' . $this->fSWlat . ')"))

I use a linestring plotting a line from a northeast point to a southwest point, abusing the fact MySQL uses a MBR for its functions.

Also for clustering i used the following 'algorithm' slightly modified:

http://postgis.refractions.net/pipermail/postgis-users/2006-March/011430.html

I think its called a zcurve. In order to full the zcurvefield efficiently i convert lat and long to a binary value (padded with zero's on the left) and use that value for rouding, actually creating a sort of quad tree :)

PHP:

static public function binaryInterleave($sLat, $sLon){
$sLat = floatVal($sLat);
$sLon = floatVal($sLon);
$sLat = ($sLat += 90) * 0.5;
$sLon = ($sLon += 180)* 0.3;


$sLat = round($sLat * 100000000);
$sLon = round($sLon * 100000000);

$sLat = str_pad($sLat, 10, "0", STR_PAD_LEFT);
$sLon = str_pad($sLon, 10, "0", STR_PAD_LEFT);

$sLat = base_convert($sLat, 10, 2);
$sLon = base_convert($sLon, 10, 2);

$aLength = array(strlen($sLat), strlen($sLon));
$iMaxLength = max($aLength);

$sLatConverted = str_pad($sLat, 36, "0", STR_PAD_LEFT);
$sLonConverted = str_pad($sLon, 36, "0", STR_PAD_LEFT);

$sReturn = '';
for($i=0;$i<$iMaxLength;$i++){
if($sLonConverted{$i} == '.' || $sLatConverted{$i} == '.'){
$sReturn .= '.';
continue;
}

$sReturn .= $sLonConverted{$i};
$sReturn .= $sLatConverted{$i};
}
$sReturn = str_replace('..', '.', $sReturn);

return $sReturn;
}



By rounding the zcurve column ( varchar(255), indexed ) you can create clusters of points exceptionally fast.

"GROUP BY SUBSTRING(zcurve, 1, ". $this->getRoundAmount() . ")";

You can play around with rounding until you find a nice setting for the zoom level.