Welcome to WebmasterWorld Guest from 54.159.161.138 register, free tools, login, search, pro membership, help, library, announcements, recent posts, open posts, Become a Pro Member
 Home / Forums Index / Code, Content, and Presentation / JavaScript and AJAX
Forum Library, Charter, Moderator: open

# JavaScript and AJAX Forum

 Tweet
Determining if a point is inside a polygon
I'm stumped!
donovanh

Msg#: 3551991 posted 7:20 pm on Jan 18, 2008 (gmt 0)

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

Msg#: 3551991 posted 7:38 pm on Jan 18, 2008 (gmt 0)

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

Msg#: 3551991 posted 7:59 pm on Jan 18, 2008 (gmt 0)

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

Msg#: 3551991 posted 8:02 pm on Jan 18, 2008 (gmt 0)

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

Msg#: 3551991 posted 8:10 pm on Jan 18, 2008 (gmt 0)

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

Msg#: 3551991 posted 8:14 pm on Jan 18, 2008 (gmt 0)

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

Msg#: 3551991 posted 8:16 pm on Jan 18, 2008 (gmt 0)

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

donovanh

Msg#: 3551991 posted 9:01 pm on Jan 18, 2008 (gmt 0)

Nice one guys! That works perfectly. Thank you.

 Global Options: top home search open messages active posts  Tweet

 Home / Forums Index / Code, Content, and Presentation / JavaScript and AJAX