CODEWITHSUNDEEP
c++polygon
Todd
Todd

Reputation: 27

Points inside Polygon (excluding boundaries)

I am currently finding the co-ordinates inside a particular shape with 12 vertices.

          (3,7)  (5,7)
            #######
            #     #
            #  X  #
       (3,5)#     #(5,5)
 (1,5)#######  X  #######(7,5)
      #                 #
      #  X  X  X  X  X  #
      #                 #
 (1,3)#######  X  #######(7,3)
       (3,3)#     #(5,3)
            #  X  #
            #     #
            #######
          (3,1)  (5,1)

I would like to find out the coordinates inside the shape (marked 'X'), excluding the coordinates that make up the shape.

I've tried pnpoly by W. Randolph Franklin (http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html), but it also considers the coordinates that make up the shape as "inside the shape".

Do note that the above shape is just an example. The coordinates could be anywhere.

How can I modify the code such that it doesn't allow the inclusion of the boundaries of the shape?

int pnpoly(int vertx[], int verty[], int testx, int testy) {
    int nvert = 12;
    int i, j, c = 0;
    for (i = 0, j = nvert-1; i < nvert; j = i++) {
        if ( ((verty[i]>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ) {
            c = !c;
        }
    }
    return c;
}

Upvotes: 2

Views: 988

Answers (2)

Angus Johnson
Angus Johnson

Reputation: 4643

Since you have code to test if the point is inside a given polygon, you just need to exclude those points that are on the polygon. Note: This test is only reliable if you're using integer coordinates (not floats).

struct Point {
  int X;
  int Y;
};

bool PointOnLineSegment(const Point pt, const Point linePt1, const Point linePt2)
{
  return ((pt.X == linePt1.X) && (pt.Y == linePt1.Y)) ||
    ((pt.X == linePt2.X) && (pt.Y == linePt2.Y)) ||
    (((pt.X > linePt1.X) == (pt.X < linePt2.X)) &&
    ((pt.Y > linePt1.Y) == (pt.Y < linePt2.Y)) &&
    ((pt.X - linePt1.X) * (linePt2.Y - linePt1.Y) ==
      (linePt2.X - linePt1.X) * (pt.Y - linePt1.Y)));
}

bool PointOnPolygonEdge(const Point pt, Point *poly, int vertexCnt)
{
  if (vertexCnt < 2) return false;
  vertexCnt--;
  for (int i = 0; i < vertexCnt; ++i)
    if (PointOnLineSegment(pt, poly[i], poly[i+1])) 
      return true;
  if (PointOnLineSegment(pt, poly[vertexCnt], poly[0])) return true;
  return false;
}


EDIT (Dec 8, 2018):

My (old) answer above can be much improved upon ...
Reference "The Point in Polygon Problem for Arbitrary Polygons" by Hormann & Agathos
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf

struct Point { int X; int Y; };
typedef std::vector< Point > Path;

int PointInPolygon(const Point &pt, const Path &path)
{
  //returns 0 if false, +1 if true, -1 if pt ON polygon boundary
  int result = 0;
  size_t cnt = path.size();
  if (cnt < 3) return 0;
  Point ip = path[0];
  for(size_t i = 1; i <= cnt; ++i)
  {
    Point ipNext = (i == cnt ? path[0] : path[i]);
    if (ipNext.Y == pt.Y)
    {
        if ((ipNext.X == pt.X) || (ip.Y == pt.Y && 
          ((ipNext.X > pt.X) == (ip.X < pt.X)))) return -1;
    }
    if ((ip.Y < pt.Y) != (ipNext.Y < pt.Y))
    {
      if (ip.X >= pt.X)
      {
        if (ipNext.X > pt.X) result = 1 - result;
        else
        {
          int d = (ip.X - pt.X) * (ipNext.Y - pt.Y) - 
            (ipNext.X - pt.X) * (ip.Y - pt.Y);
          if (!d) return -1;
          if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result;
        }
      } else
      {
        if (ipNext.X > pt.X)
        {
          int d = (ip.X - pt.X) * (ipNext.Y - pt.Y) - 
            (ipNext.X - pt.X) * (ip.Y - pt.Y);
          if (!d) return -1;
          if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result;
        }
      }
    }
    ip = ipNext;
  } 
  return result;
}

Upvotes: 1

Ulrich Eckhardt
Ulrich Eckhardt

Reputation: 17415

Shrink the shape by the border that you want to exclude, then use the existing algorithm.

BTW: Don't use int vertx[], it's a dangerous lie. The equivalent obvious code is int* vertx, which makes it obvious that it lacks a const.

Upvotes: 2

Related Questions