Whether a point lies inside a polygon- 2D

In this post, you can just find the java version of Determining if a point lies on the interior of a polygon .Specifically for 2D.



private class Polygon
      {
            private Point [] vertices;
           
            private boolean isInsidePolygon(Point [] vert,Point p)
            {
                  /*
* Make sure you have initialized vertices[] with valid *polygon
*/
                  int counter = 0;
                  int i;
                  double xid;
                  Point p1,p2;

                  p1 = vertices[0];
                    for (i=1;i<=vertices.length;i++)
                    {
                      p2 = vertices[i % vertices.length];
                      if (p.y > getMinimum(p1.y,p2.y))
                      {
                        if (p.y <= getMaximum(p1.y,p2.y))
                        {
                          if (p.x <= getMaximum(p1.x,p2.x))
                          {
                            if (p1.y != p2.y)
                            {
                  xid = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
                              if (p1.x == p2.x || p.x <= xid)
                              {  
                                    counter++;                                                              }
                            }
                          }
                        }
                      }
                      p1 = p2;
                    }

                    if (counter % 2 == 0)
                    {
                          //IF even, => outside
                      return false;
                    }
                    else
                    {
                          //IF odd, => inside
                      return true;
                    }
            }

           
           
      private int getMinimum(int i,int j)
      {
            return((i<j?i:j));
      }
         
      private int getMaximum(int i,int j)
      {
            return((i>j?i:j));
      }
                        
}



Instantiate 'Polygon'  class and initiate 'vertices' variable with valid instance of 'Point' class. 

You know how to do the rest..

Happy coding :-)

2 comments:

  1. FYI:

    Point exactly over the any of the vertex are not checked. If needed, you can do necessary coding during initial stage of the method.

    Feel free to revert back to me for any details :-)

    ReplyDelete
  2. Hi,

    Can you please share the sample code with valid polygon code too.

    ReplyDelete