10
\$\begingroup\$

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.

\$\endgroup\$
  • 14
    \$\begingroup\$ Removing all white space doesn't make code faster. \$\endgroup\$ – JPhi1618 Oct 27 '15 at 14:01
  • 1
    \$\begingroup\$ Almost a code golf. \$\endgroup\$ – Aidiakapi Oct 27 '15 at 16:10
6
\$\begingroup\$
  • 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;
}
\$\endgroup\$
  • \$\begingroup\$ I made a few edits to further improve performance that are only possible now because I can read the code more easily! \$\endgroup\$ – rodolphito Oct 30 '15 at 1:53
  • \$\begingroup\$ Oddly enough, your method with the caching and my improvements, takes 50% more time than my original method without a single improvement! This needs more testing. (results of 10000 random point tests on a random polygon with 20 points: polyCheck:25460ns, IsPointInPolygon:37700ns) \$\endgroup\$ – rodolphito Oct 30 '15 at 2:25
  • \$\begingroup\$ Undid the reordering of the expression after I noticed extraneous results, turns out that I would need to flip the inequality if (startY - endY) is negative since I am multiplying by a negative. I did some further investigation, and it seems that the caching itself is slowing it down. \$\endgroup\$ – rodolphito Oct 30 '15 at 2:56
  • 1
    \$\begingroup\$ Vector2 is from the Unity engine, it is most certainly of float precision, at least according to the documentation, and Mono. I think the performance degradation has something to do with the reusing of the variables, I'm going to try moving the variable declarations into the for loop. I think that it's causing the CPU to reuse registers and maybe one-use registers are faster. (But this is absolutely pure speculation on my part, I would need to disassemble it and I am not sure how to go about doing that, or what to do once it is disassembled). \$\endgroup\$ – rodolphito Oct 30 '15 at 7:27
  • 1
    \$\begingroup\$ You can look at the byte-code generated quite easily with some tools (search 'C# spy code'). For and while should both be very well treated i guess. Yes, trading a div for a mul might be worth a try... and to be fair you should do the same in your original code... Damn it ! those compilers are smart !!! :-) \$\endgroup\$ – GameAlchemist Oct 30 '15 at 8:22
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks, I will try to do those things. Should I put the result in an edit to the question? \$\endgroup\$ – rodolphito Oct 27 '15 at 6:33
  • 1
    \$\begingroup\$ Nope. Adding updated code isn't allowed on code review if the question has answers because it would invalidate these answers. \$\endgroup\$ – Heslacher Oct 27 '15 at 6:38
  • \$\begingroup\$ Also, use temporary variables to hold intermediate values. The compiler will optimize them away in many cases, and having them in the code will make what you're doing much clearer. \$\endgroup\$ – JPhi1618 Oct 27 '15 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.