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

JavaScript and AJAX Forum

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




msg:3551993
 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:3552018
 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:3552044
 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:3552047
 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:3552054
 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:3552057
 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:3552058
 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:3552095
 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  
 

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

All trademarks and copyrights held by respective owners. Member comments are owned by the poster.
Home ¦ Free Tools ¦ Terms of Service ¦ Privacy Policy ¦ Report Problem ¦ About ¦ Library ¦ Newsletter
WebmasterWorld is a Developer Shed Community owned by Jim Boykin.
© Webmaster World 1996-2014 all rights reserved