Welcome, Guest. Please login or register.

Login with username, password and session length

 
Advanced search

1411283 Posts in 69325 Topics- by 58380 Members - Latest Member: bob1029

March 29, 2024, 07:26:17 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperTechnical (Moderator: ThemsAllTook)How to check a point in a polygon
Pages: [1]
Print
Author Topic: How to check a point in a polygon  (Read 3272 times)
nayon
Level 5
*****


dickfish


View Profile
« 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
******



View Profile WWW
« 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 Tongue

However, I found this page through google that looks like it might be very helpful:

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[0];
  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


View Profile
« 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[0]
        for p2 in poly[1:]:
            if pt[1] > min(p1[1],p2[1]):
               if pt[1] <= max(p1[1],p2[1]):
                  if pt[0] == max(p1[0],p2[0]):
                     if p1[1] != p2[1]:
                        xinters = float( (pt[1]-p1[1])*(p2[0]-p1[0])/(p2[1]-p1[1])+p1[0] )
                        if p1[0] == p2[0] or pt[0] <= 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[0] == max(p1[0],p2[0]):
should be
                  if pt[0] <= max(p1[0],p2[0]):

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


View Profile
« 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


View Profile
« 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[0]
        for i in range(poly.__len__()):
            p2 = poly[(i+1)%poly.__len__()-1]
            if pt[1] > min(p1[1],p2[1]):
               if pt[1] <= max(p1[1],p2[1]):
                  if pt[0] <= max(p1[0],p2[0]):
                     if p1[1] != p2[1]:
                        xinters = float( float( (pt[1]-p1[1]) ) * float((p2[0]-p1[0])/(p2[1]-p1[1])) +p1[0] )
                        if p1[0] == p2[0] or pt[0] <= 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
Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic