Determining if a point is inside a polygon

I'm stumped!

[donovanh]

I'd really appreciate some help. I'm writing a site to use Google Maps, and need to determine if a coordinate is within an area. Since the areas aren't rectangular, but represented by polygons, I'm having trouble writing javascript to determine if the co-ordinates reside inside the area.

This is as far as I have got:

  points1 = new Array();
  points1[0]['lat'] = -33.7700;
  points1[0]['lng'] = 173.5730;
  points1[1]['lat'] = -35.9780;
  points1[1]['lng'] = 175.0122;
  points1[2]['lat'] = -36.8972;
  points1[2]['lng'] = 173.8367;
  points1[3]['lat'] = -34.2073;
  points1[3]['lng'] = 171.9690;
  points1[4]['lat'] = -33.7700;
  points1[4]['lng'] = 173.5730;
  // Get where the map is at this moment
  p = map.getCenter();
  // Test if it's in an area
  if (Contains(points1, p)) {
  // Let the magic happen
  }

Apologies in advance for my attempts at the function 'Contains', I'm trying to base it on another function that takes Google Map polygons as input:

  function Contains (points, p) {
  var j=0;
  var oddNodes = false;
  var x = p.lng();
  var y = p.lat();
  for (i in points) {
   
   j++;
   if (j == array.length(points)) {j = 0;}
   if (((points[i]['lat'] < y) && (points[j]['lat'] >= y))
   ¦¦ ((points[j]['lat'] < y) && (points[i]['lat'] >= y))) {
   if ( points[i]['lng'] + (y - points[i]['lat'])
   / (points[j]['lat']-points[i]['lat'])
   * (points[j]['lng'] - points[i]['lng'])<x ) {
    oddNodes =!oddNodes
   }
   }
  }
  return oddNodes;
  }

[donovanh]

I found that the function I'm trying to replicated in Javascript is based on the following by Randolph Franklin:

int pnpoly(int npol, float *xp, float *yp, float x, float y)
  {
   int i, j, c = 0;
   for (i = 0, j = npol-1; i < npol; j = i++) {
    if ((((yp[i] <= y) && (y < yp[j])) ¦¦
       ((yp[j] <= y) && (y < yp[i]))) &&
      (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
     c =!c;
   }
   return c;
  }

Any idea how this would work in Javascript? How should I format the co-ordinate data to fit it?

[gergoe]

With one modification you can use this function as it is:

int pnpoly(int npol, float *xp, float *yp, float x, float y) {

...becomes:

function pnpoly(xp, yp, x, y) { 
var npol = xp.length;

xp is an array of the Longitude values,
yp is an array of the Latitude values,
x is the Longitude of the point you are looking for,
y is the Latitude of the point you are looking for

You can also rewrite the function to match your current array structure, it is really not difficult, replace the first two parameters with "points" for example, and where the function references xp[idx] you change it to points[idx]['lon'], and yp[idx] should become points[idx]['lat'].

[Fotiman]

I'll be honest, my Geometry(?) is quite rusty. But I don't see how you can tell if a given point is within a polygon unless you know the actual 'sides' of the polygon and not just the points that make up the corners. For example, suppose you have the following points:

............. 
..........oB. 
............. 
.oA.....oC... 
............. 
..........oD. 
............. 

How do you know which of these polygons are represented by those points:

............. 
....../---oB. 
../---.../... 
.oA.....oC... 
..\---...\... 
......\---oD. 
............. 

............. 
....../---oB. 
../---....¦.. 
.oA-----oC¦.. 
.........\¦.. 
..........oD. 
............. 

It's not easy to create this sort of diagram using text, but hopefully it makes sense. Essentially, there's no way to know whether there is a line from point B to point C, or a line from point B to point D, and depending on where the line is can change the polygon.

[donovanh]

Your raise a good point there (pun not indended :P )

For what it's worth, the lines go directly from one point to the next in sequence.

A-------B
¦ ¦
E C
¦_ _¦
D

[Fotiman]

Actually, I suppose the order that the points are defined is how you specify which points are connected, so ignore my last post. :)

function pnpoly(xp, yp, x, y) { 
 var i, j, c = 0, npol = xp.length; 
 for (i = 0, j = npol-1; i < npol; j = i++) { 
  if ((((yp[i] <= y) && (y < yp[j])) ¦¦ 
((yp[j] <= y) && (y < yp[i]))) && 
(x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) { 
   c =!c; 
  } 
 } 
 return c; 
}  

Be sure to replace the ¦¦ with actual pipe characters.

[edited by: Fotiman at 8:18 pm (utc) on Jan. 18, 2008]

[donovanh]

Thanks for the replies, I'll have a go with gergoe's recommendation and let you know how I get on. :)

[donovanh]

Nice one guys! That works perfectly. Thank you.