check point is within polygon

[Vyliss]

is there a function that allows you to check whether a x,y point is within a polygon?

[corbin]

Ummmm you could make a function but that would be some wierd logic...

[Vyliss]

well, I'm trying to create a map where there are like polygon shapes that are clickable (like a image map) and those takes you to a function, but wherever you click on the map/image it puts a dot where u clicked, but the thing is if I use apache mod_imap, there is no way for me to record the clicked x,y coordinates, cos u can't parse php within the .map file.
don't know if that makes anysense, but if I use php instead, i can get the x,y coordinates but there;s no way for me to tell whether the click is within a polygon shape or not.

grr

[Barand]

Logic not that weird

Draw a filled black polygon on white background. If the pixel at your point is black then its in the polygon

[code]
<?php
function ptInPoly ($pt, $poly) {
    $max1 = max($pt);
    $max2 = max($poly);
    $max = max($max1, $max2)+5;
    $im = imagecreate($max, $max);
    $bg = imagecolorallocate($im, 0xFF, 0xFF, 0xFF);
    $fg = imagecolorallocate($im, 0x00, 0x00, 0x00);
    $points = count($poly)/2;
    imagefilledpolygon($im,$poly,$points,$fg);
    $color = imagecolorat($im, $pt[0], $pt[1]) ;
    $inPoly = $color == $fg;
    imagedestroy($im);
    return $inPoly;
}

$pt = array (13, 10);
$poly = array (5,5,20,5,20,20,5,20);

if (ptInPoly($pt, $poly))
    echo 'YES';
else
    echo 'NO';
?>[/code]

[beckjoh]

Barand,

I have revisited your idea to find the point within a polygon.  I am using Lat Long values.  Would I first have to convert the lat long values to screen coordinates?  If so, can you show me how with your example?

Thanks.

JB

[corbin]

Does the polygon change or stay the same?


(Same shape/measurements, not same coordinates.)

[Barand]

it would just require scaling your ranges of lat/long coordinates to the chosen size of your image

[beckjoh]

The polygon would not change it would stay the same.

[beckjoh]

I know I need to scale the coordinates to an image, but I really don't care about the scale.  I am just trying to find out if an xy coordinate in within a polygon made up of several vertices.  Any suggestions on a scale?

[Mchl]

Draw a vertical line starting at x,y going right (or left, or just any direction, your choice) and calculate how many times it intersects sides of polygon.
Even: outside
Odd: inside

[beckjoh]

This is my last attempt at trying to use Barand's idea to find points within polygons.  I have a shapefile with 18 polygons.  I import this shapefile and us GD to draw the polygons.  I have a mysql table with the x, y (long, lat) coordinates.  This table has approximately 5,000 points.  I put the following code together from a variety of sources from this site http://www.easywms.com/easywms/?q=zh-hant/node/78.  When I use only one point, the code works great.  But when I loop the 5,000 points it takes over 10 minutes to run. Way too long.  Here is my code.  If anyone knows how to speed this up or approach in a different manner please let me know.  THanks for your help in advance.

$image_sx = 600;
$image_sy = 600;
if(empty($scale))$scale    = 350000000;
$select = mysql_query("SELECT * FROM dbtable");
$rows = mysql_num_rows($select);

while ($query = mysql_fetch_array($select)) {
$my_long[] = $query['Long'];
$my_lat[] = $query['Lat'];
}
for($m = 0;$m < $rows; $m++) {

$my_long = $my_long[$m];
$my_lat = $my_long[$m];

$sx   = 2 * $scale;
$sy      = $scale;

$center  = getlocationcoords($my_lat, $my_long, $sx,$sy) ;
$min_x    = $center["x"] - ($image_sx / 2);
$min_y    = $center["y"] - ($image_sy / 2);

$im        = imagecreate($image_sx,$image_sy);

$land      = imagecolorallocate ($im, 0xF7,0xEF,0xDE);
$land2      = imagecolorallocate ($im, 0x00, 0x00, 0x00);
$red      = imagecolorallocate ($im, 0xff,0x00,0x00);

$pt["x"] = $center["x"] - $min_x;
$x = $pt["x"];
$pt["y"] = $center["y"] - $min_y;
$y = $pt["y"];
$pts = array($x,$y);


$arrGeometry = loadShapeFile("polygons.shp") ;


foreach($arrGeometry as $poly) {
    $converted_points = array();
    $numparts = $poly["geom"]["numparts"];
if ($numparts >= 1) {
        for($j = 0;$j < $numparts;$j++)
        // make "x y " to "x y"
        $points = trim($poly["geom"]["parts"][$j]["pointString"]);
        $points = explode(" ", $points);
        $number_points = count($points);
        $i = 0;

        while ($i < $number_points) {
            $lon = $points[$i];
            $lat = $points[$i + 1];
         
            $pt = getlocationcoords($lat, $lon, $sx, $sy);
            $converted_points[] = $pt["x"] - $min_x;
            $converted_points[] = $pt["y"] - $min_y;
            $i += 2;
        }
        switch ($poly["shapetype"]) {
            case '0':// null
                break;
            case '1':// point
                imagefilledellipse($im, $converted_points[0], $converted_points[1], 4, 4, $red);
                break;
            case '3':// polyline
                imageline($im, $converted_points[0], $converted_points[1], $converted_points[2], $converted_points[3], $red);
                break;
            case '5':// polygon
//print_r($converted_points);
                imagefilledpolygon($im, $converted_points, $number_points / 2, $land2);
                break;
            case '8':// multipoint
                imagefilledpolygon($im, $converted_points, $number_points / 2, $red);
                break;
        }
    }
}
$color = imagecolorat($im, $pts[0], $pts[1]) ;

if ($color == $land2) {
echo 'YES';
echo '<br>';

} else {
echo 'NO';
echo '<br>';
}

}

imagedestroy($im);

function getlocationcoords($lat, $lon, $width, $height)
{
    $x = (($lon + 180) * ($width / 360));
    $y = ((($lat * -1) + 90) * ($height / 180));
    return array("x" => round($x), "y" => round($y));
}

function loadShapeFile($file_name)
{
    $handle = fopen($file_name, "rb");
    // fetchShpBasicConfiguration();
    // fetchRecords();
    loadHeaders($handle);
    return $arrGeometry = loadRecords($handle);
}

function loadHeaders($handle)
{

    fseek($handle, 24, SEEK_SET);
    $fileLength = loadData("N", fread($handle, 4));
    // echo $fileLength;
    fseek($handle, 32, SEEK_SET);
    $shapeType = loadData("V", fread($handle, 4));
    //echo $shapeType;
    $boundingBox = array();
    $boundingBox["xmin"] = loadData("d", fread($handle, 8));
    $boundingBox["ymin"] = loadData("d", fread($handle, 8));
    $boundingBox["xmax"] = loadData("d", fread($handle, 8));
    $boundingBox["ymax"] = loadData("d", fread($handle, 8));
    //print_r($boundingBox);
}

function loadRecords($handle)
{
    fseek($handle, 100);
    while (!feof($handle)) {
        $bByte = ftell($handle);
        $record = new ShapeRecord(-1);
        $record->loadFromFile($handle);
        $records["shapetype"] = $record->shapeType;
        $records["geom"] = $record->SHPData;
        if (isset($records)) {
            $arrGeometry[] = $records;
            unset($records);
        }

        $eByte = ftell($handle);
        if ($eByte <= $bByte) {
            return $arrGeometry;
        }
    }
}

function loadData($type, $data)
{
    if (!$data) return $data;
    $tmp = unpack($type, $data);
    return current($tmp);
}

class ShapeRecord {
    var $SHPFile = null;

    var $recordNumber = null;
    var $shapeType = null;

    var $SHPData = array();

    function ShapeRecord($shapeType)
    {
        $this->shapeType = $shapeType;
    }

    function loadFromFile($handle)
    {
        $this->SHPFile = $handle;
        $this->loadStoreHeaders();

        switch ($this->shapeType) {
            case 0:
                $this->loadNullRecord();
                break;
            case 1:
                $this->loadPointRecord();
                break;
            case 3:
                $this->loadPolyLineRecord();
                break;
            case 5:
                $this->loadPolygonRecord();
                break;
            case 8:
                $this->loadMultiPointRecord();
                break;
            default:
                // $setError(sprintf("The Shape Type '%s' is not supported.", $shapeType));
                break;
        }
    }

    function loadStoreHeaders()
    {
        $this->recordNumber = loadData("N", fread($this->SHPFile, 4));
        $tmp = loadData("N", fread($this->SHPFile, 4)); //We read the length of the record
        $this->shapeType = loadData("V", fread($this->SHPFile, 4));
    }

    function loadPoint()
    {
        $data = array();
        $x1 = loadData("d", fread($this->SHPFile, 8));
        $y1 = loadData("d", fread($this->SHPFile, 8));
        $data["pointString"] = "$x1 $y1 ";
        return $data;
    }
    function loadNullRecord()
    {
        $this->SHPData = array();
    }

    function loadPointRecord()
    {
        $data = $this->loadPoint();
        $tmp = explode(" ", $data["pointString"]);
        $this->SHPData["xmin"] = $this->SHPData["xmax"] = $tmp[0];
        $this->SHPData["ymin"] = $this->SHPData["ymax"] = $tmp[1];
        $this->SHPData["numparts"] = 1;
        $this->SHPData["numpoints"] = 1;
        $this->SHPData["parts"][0]["pointString"] = $data["pointString"];
        // $this->SHPData["pointString"] = $data["pointString"];
    }

    function loadMultiPointRecord()
    {
        $this->SHPData = array();
        $this->SHPData["xmin"] = loadData("d", fread($this->SHPFile, 8));
        $this->SHPData["ymin"] = loadData("d", fread($this->SHPFile, 8));
        $this->SHPData["xmax"] = loadData("d", fread($this->SHPFile, 8));
        $this->SHPData["ymax"] = loadData("d", fread($this->SHPFile, 8));

        $this->SHPData["numpoints"] = loadData("V", fread($this->SHPFile, 4));

        for ($i = 0; $i <= $this->SHPData["numpoints"]; $i++) {
            $data = $this->loadPoint();
            $this->SHPData["pointString"] .= $data["pointString"];
        }
    }

    function loadPolyLineRecord()
    {
        $this->SHPData = array();
        $this->SHPData["xmin"] = loadData("d", fread($this->SHPFile, 8));
        $this->SHPData["ymin"] = loadData("d", fread($this->SHPFile, 8));
        $this->SHPData["xmax"] = loadData("d", fread($this->SHPFile, 8));
        $this->SHPData["ymax"] = loadData("d", fread($this->SHPFile, 8));

        $this->SHPData["numparts"] = loadData("V", fread($this->SHPFile, 4));
        $this->SHPData["numpoints"] = loadData("V", fread($this->SHPFile, 4));

        for ($i = 0; $i < $this->SHPData["numparts"]; $i++) {
            $this->SHPData["parts"][$i] = loadData("V", fread($this->SHPFile, 4));
        }

        $firstIndex = ftell($this->SHPFile);
        $readPoints = 0;
        while (list($partIndex, $partData) = each($this->SHPData["parts"])) {
            if (!isset($this->SHPData["parts"][$partIndex]["pointString"]) || !is_array($this->SHPData["parts"][$partIndex]["pointString"])) {
                $this->SHPData["parts"][$partIndex] = array();
                // $this->SHPData["parts"][$partIndex]["pointString"] = array();
            } while (!in_array($readPoints, $this->SHPData["parts"]) && ($readPoints < ($this->SHPData["numpoints"])) && !feof($this->SHPFile)) {
                $data = $this->loadPoint();
                $this->SHPData["parts"][$partIndex]["pointString"] .= $data["pointString"];
                $readPoints++;
            }
        }

        fseek($this->SHPFile, $firstIndex + ($readPoints * 16));
    }

    function loadPolygonRecord()
    {
        $this->loadPolyLineRecord();
    }
}