Point inside Polygon check

Question

I have written a method to determine whether a Vector2 lies inside a polygon or outside of it. The polygon is defined by an array of clockwise vertices, p[]. It returns true if the point is inside, false otherwise.

public bool polyCheck(Vector2 v, Vector2[] p)
{
    int j = p.Length-1;
    bool c = false;
    for(int i=0;i<p.Length;j=i++)c^=p[i].y>v.y^p[j].y>v.y&&v.x<(p[j].x-p[i].x)*(v.y-p[i].y)/(p[j].y-p[i].y)+p[i].x;
    return c;
}

It is perfectly functional, works with all edge cases, and is blazing fast. I want to know how I could make the method look prettier, and have better 'coding practices' though.

Answer 1

• Naming (signature): polyCheck is not a clear name. And the arguments's names could help explain the function's semantic as well.

  public bool IsPointInPolygon(Vector2 point, Vector2[] polygon) 
  

• Packing / golfing: not using the {} for the for loop doesn't help for anything (including speed), neither does packing all the computation in one line : it just makes the code impossible to read which seems of little use. In the same manner, make the operator precedence obvious by using () and using several lines.

• Performance:

  1. What is striking at first glance is the redundancy of p[i] and p[j]: do cache those vectors inside some vars. 8 array indirection per polygon point can be avoided. And even better : cache the polygon point's coordinates instead of caching the polygon points to save 6 property indirection per polygon point.
  2. point.x and point.y won't change: cache them.
  3. after reading more closely, since i always follows j, you could load p[j] from p[i], or rather those points' coordinates, to reduce by a factor of 2 the array/property access.
  4. Maybe you are doing this test before, but computing a bounding box for your polygons and using it as a first test could -depending on many factors of course- tremendously speed up things.

• Naming (variables): c, p, ... think about someone else reading this code... or you in 3 months !!!

I'd be curious to know if this code is faster, and by which amount, since compilers are very smart. Let me know if you happen to test it!

public bool IsPointInPolygon(Vector2 point, Vector2[] polygon) {
   int polygonLength = polygon.Length, i=0;
   bool inside = false;
   // x, y for tested point.
   float pointX = point.x, pointY = point.y;
   // start / end point for the current polygon segment.
   float startX, startY, endX, endY;
   Vector2 endPoint = polygon[polygonLength-1];           
   endX = endPoint.x; 
   endY = endPoint.y;
   while (i<polygonLength) {
      startX = endX;           startY = endY;
      endPoint = polygon[i++];
      endX = endPoint.x;       endY = endPoint.y;
      //
      inside ^= ( endY > pointY ^ startY > pointY ) /* ? pointY inside [startY;endY] segment ? */
                && /* if so, test if it is under the segment */
                ( (pointX - endX) < (pointY - endY) * (startX - endX) / (startY - endY) ) ;
   }
   return inside;
}

Answer 2

I want to know how I could make the method look prettier, and have better 'coding practices' though

• avoid single letter variable if they aren't iterator variables. If you or Sam the maintainer needs to come back to this method in a few months, neither you nor Sam will grasp at first glance what the variables are about.

• avoid shortening of method names. polyCheck does not tell anything about what the method tries to do. A name like IsInPolygon would be better. With a more OO approach by adding a Polygon class having a method Contains(Vector2) it would be more clear.

  public class Polygon
  {
      public Vector2[] Vertices { get; private set; }
      public Polygon(Vector2[] vertices)
      {
          Vertices = vertices;
      }
      public bool ContainsVector(Vector2 vector)
      {
          // do the magic
          return true;
      }
  }  
  

• always use braces {} although they are optional for single lined for's. This will help you to make your code less error prone.

• let your variables and operators have some space to breathe. This

  c^=p[i].y>v.y^p[j].y>v.y&&v.x<(p[j].x-p[i].x)*(v.y-p[i].y)/(p[j].y-p[i].y)+p[i].x;
  

  is just not readable.