1401678 Posts in 67940 Topics- by 61496 Members - Latest Member: Lankar5

July 07, 2022, 12:18:54 AM

Need hosting? Check out Digital Ocean
TIGSource Forums Developer Technical (Moderator: ThemsAllTook)How to check a point in a polygon Author Topic: How to check a point in a polygon  (Read 3113 times)
nayon
Level 5      dickfish  « on: May 11, 2008, 07:13:38 AM »

So, I have this list of point that form a convex polygon... And I have this other point. How can I check if that point is within that polygon? I can't think of any way to do it, be it nightmarish or easy... So can someone give me a hand please? Logged Terry
TIGSource Editor
Level 10          « Reply #1 on: May 11, 2008, 07:21:09 AM »

This seems really familiar - I think I've read up on it before. But I can't remember much about it Determining if a point lies on the interior of a polygon

It highlights this solution, which returns 0 or 1 (for inside or outside) for a point P on a polygon of N points (as defined below):

Code:
#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)
#define INSIDE 0
#define OUTSIDE 1

typedef struct {
double x,y;
} Point;

int InsidePolygon(Point *polygon,int N,Point p)
{
int counter = 0;
int i;
double xinters;
Point p1,p2;

p1 = polygon;
for (i=1;i<=N;i++) {
p2 = polygon[i % N];
if (p.y > MIN(p1.y,p2.y)) {
if (p.y <= MAX(p1.y,p2.y)) {
if (p.x <= MAX(p1.x,p2.x)) {
if (p1.y != p2.y) {
xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
if (p1.x == p2.x || p.x <= xinters)
counter++;
}
}
}
}
p1 = p2;
}

if (counter % 2 == 0)
return(OUTSIDE);
else
return(INSIDE);
} Logged

nayon
Level 5      dickfish  « Reply #2 on: May 11, 2008, 10:53:23 AM »

Hmm, thanks, I implemented it (hopefully correctly)... I'm not getting the result I desire but I have a hunch why... well we'll see... I'll post back when I'm sure

EDIT: I can't seem to find what's wrong, here's my implementation, in Python:

it seems right to me
Code:
def inside(self, poly, pt):
counter = 0
p1 = poly
for p2 in poly[1:]:
if pt > min(p1,p2):
if pt <= max(p1,p2):
if pt == max(p1,p2):
if p1 != p2:
xinters = float( (pt-p1)*(p2-p1)/(p2-p1)+p1 )
if p1 == p2 or pt <= xinters:
counter+=1
p1 = p2
if counter %2 == 0:
return False
else:
return True
 « Last Edit: May 11, 2008, 11:07:43 AM by NaYoN » Logged Zaphos
Guest « Reply #3 on: May 11, 2008, 11:24:22 AM »

if pt == max(p1,p2):
should be
if pt <= max(p1,p2):

edit: also you broke the for loop, it needs to wrap around
 « Last Edit: May 11, 2008, 11:26:33 AM by Zaphos » Logged
nayon
Level 5      dickfish  « Reply #4 on: May 11, 2008, 11:36:32 AM »

Well first of all thanks for pointing out that small mistake... I never see such small mistakes...

And sicne the for loop traverses only once, what's the point in making it wrap around? I can't see that Logged Zaphos
Guest « Reply #5 on: May 11, 2008, 11:42:26 AM »

So that you get the edge between vertices n-1 and 0.
 « Last Edit: May 11, 2008, 11:59:30 AM by Zaphos » Logged
nayon
Level 5      dickfish  « Reply #6 on: May 11, 2008, 12:03:55 PM »

Thanks.

For reference, here's the current form, even though it still acts a bit awkwardly I think this time it's a fault of the rest of the code, not this guy.

Code:
def inside(self, poly, pt):
counter = 0
p1 = poly
for i in range(poly.__len__()):
p2 = poly[(i+1)%poly.__len__()-1]
if pt > min(p1,p2):
if pt <= max(p1,p2):
if pt <= max(p1,p2):
if p1 != p2:
xinters = float( float( (pt-p1) ) * float((p2-p1)/(p2-p1)) +p1 )
if p1 == p2 or pt <= xinters:
counter+=1
p1 = p2
if counter %2 == 0:
return False
else:
return True Logged Zaphos
Guest « Reply #7 on: May 11, 2008, 12:19:37 PM »

I think that this:
p2 = poly[(i+1)%poly.__len__()-1]
should be this:
p2 = poly[(i+1)%poly.__len__()] Logged