# check point is within polygon

10 replies to this topic

### #1 Vyliss

Vyliss
• New Members
• Newbie
• 2 posts

Posted 18 September 2006 - 12:37 AM

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

### #2 corbin

corbin
• Staff Alumni
• 8,129 posts

Posted 18 September 2006 - 12:58 AM

Ummmm you could make a function but that would be some wierd logic...
Why doesn't anyone ever say hi, hey, or whad up world?

### #3 Vyliss

Vyliss
• New Members
• Newbie
• 2 posts

Posted 18 September 2006 - 02:00 AM

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

### #4 Barand

Barand
• Moderators
• Sen . ( ile || sei )
• 18,017 posts

Posted 18 September 2006 - 11:21 AM

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

```<?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';
?>```

If you are still using mysql_ functions, STOP! Use mysqli_ or PDO. The longer you leave it the more you will have to rewrite.

 |baaGrid| easy data tables - and more|baaChart| easy line, column and pie charts

### #5 beckjoh

beckjoh
• Members
• Member
• 20 posts

Posted 11 December 2008 - 02:51 AM

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

### #6 corbin

corbin
• Staff Alumni
• 8,129 posts

Posted 11 December 2008 - 03:23 AM

Does the polygon change or stay the same?

(Same shape/measurements, not same coordinates.)
Why doesn't anyone ever say hi, hey, or whad up world?

### #7 Barand

Barand
• Moderators
• Sen . ( ile || sei )
• 18,017 posts

Posted 11 December 2008 - 10:15 AM

it would just require scaling your ranges of lat/long coordinates to the chosen size of your image
If you are still using mysql_ functions, STOP! Use mysqli_ or PDO. The longer you leave it the more you will have to rewrite.

 |baaGrid| easy data tables - and more|baaChart| easy line, column and pie charts

### #8 beckjoh

beckjoh
• Members
• Member
• 20 posts

Posted 12 December 2008 - 02:50 AM

The polygon would not change it would stay the same.

### #9 beckjoh

beckjoh
• Members
• Member
• 20 posts

Posted 13 December 2008 - 08:17 PM

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?

### #10 Mchl

Mchl
• Staff Alumni
• 8,507 posts
• LocationHigh Memory Area

Posted 13 December 2008 - 08:21 PM

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
NetBeans fanatic | ExtJS masochist | C++ denier
PHP4 & MySQL4 are no longer supported.
PHPFreaks Tutorials | PHP Debugging: A Beginner's guide | PHP Security Tutorial || How To Ask Questions The Smart Way

### #11 beckjoh

beckjoh
• Members
• Member
• 20 posts

Posted 21 December 2008 - 02:33 AM

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.c...-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);

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));
}

{
\$handle = fopen(\$file_name, "rb");
// fetchShpBasicConfiguration();
// fetchRecords();
}

{

fseek(\$handle, 24, SEEK_SET);
// echo \$fileLength;
fseek(\$handle, 32, SEEK_SET);
//echo \$shapeType;
\$boundingBox = array();
//print_r(\$boundingBox);
}

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

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

{
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;
}

{
\$this->SHPFile = \$handle;

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

{
}

{
\$data = array();
\$data["pointString"] = "\$x1 \$y1 ";
return \$data;
}
{
\$this->SHPData = array();
}

{
\$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"];
}

{
\$this->SHPData = array();

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

{
\$this->SHPData = array();

for (\$i = 0; \$i < \$this->SHPData["numparts"]; \$i++) {
}

\$firstIndex = ftell(\$this->SHPFile);
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();
\$this->SHPData["parts"][\$partIndex]["pointString"] .= \$data["pointString"];
}
}

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

{
}
}

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users