next »

[nayon]

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?

[Terry]

This seems really familiar - I think I've read up on it before. But I can't remember much about it

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);
}

[nayon]

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

[Zaphos]

                  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

[nayon]

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

[Zaphos]

So that you get the edge between vertices n-1 and 0.

[nayon]

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

[Zaphos]

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