Fast C# code to determine 2D point containment

I have been asked a few times and I would like to share with you this piece of code. It tests if a point is inside/on/outside a polygon. It’s quite fast since no API call is involved. I am using it in the IsoVist2D & IsoVist3D calculation process. The code can be directly used in a C# component.

Licensed under the MIT 2.0 License.

using Rhino;
using Rhino.Geometry;
using System;

namespace PancakeAlgo.Solver
{
    public static class PointInsidePolygon
    {
        public static double Tolerance = RhinoMath.ZeroTolerance;
        public static PointContainment Contains(Point2d[] polygon, Point2d ptr)
        {
            var crossing = 0;
            var len = polygon.Length;

            for (var i = 0; i < len; i++)
            {
                var j = i + 1;
                if (j == len) j = 0;

                var p1 = polygon[i];
                var p2 = polygon[j];

                var y1 = p1.Y;
                var y2 = p2.Y;

                var x1 = p1.X;
                var x2 = p2.X;

                if (Math.Abs(x1 - x2) < Tolerance && Math.Abs(y1 - y2) < Tolerance)
                    continue;

                var minY = Math.Min(y1, y2);
                var maxY = Math.Max(y1, y2);

                if (ptr.Y < minY || ptr.Y > maxY)
                    continue;

                if (Math.Abs(minY - maxY) < Tolerance)
                {
                    var minX = Math.Min(x1, x2);
                    var maxX = Math.Max(x1, x2);

                    if (ptr.X >= minX && ptr.X <= maxX)
                    {
                        return PointContainment.Coincident;
                    }
                    else
                    {
                        if (ptr.X < minX)
                            ++crossing;
                    }
                }
                else
                {
                    var x = (x2 - x1) * (ptr.Y - y1) / (y2 - y1) + x1;
                    if (Math.Abs(x - ptr.X) <= Tolerance)
                        return PointContainment.Coincident;

                    if (ptr.X < x)
                    {
                        ++crossing;
                    }
                }
            }

            return ((crossing & 1) == 0) ? PointContainment.Outside : PointContainment.Inside;
        }
    }
}
5 Likes