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;
        }
    }
}
8 Likes

Please can you share this script as grasshopper definition. Thank you.

thanks for this code. I might ask a stupid question, but I am very much of a nooB regarding computional geometry and about to learn the really basics… Is this more efficient than the usual “draw a line and check if the intersection number is pair or odd”? I am working on a gem scanner project in python on a raspi and this would come in very handy if it was more efficient than my code… worst case just a paper reference would be enough.

thanks

Ben

I didn’t test @gankeyu script, but I use Clipper one that is surely very similar
image

Please, can somebody fix this code. I don’t understand what it is wrong.
2D_point_cointainment.gh (2.0 KB)

Don’t put a class in RunScript
Don’t use the namespace
Like this it compile !
image

Please can your share your grasshopper file because this thing drives me crazy. It is not working, no matter where I put the code.

2D_point_cointainment.gh (1.5 KB)

1 Like

Got-it. Needed to delete the

namespace PancakeAlgo.Solver
{

bit. Now it is working. Thank you.

I just a quick test and seems that it is not capable of detecting a point in a polygon:

2D_point_cointainment.gh (5.2 KB)

Hello
I think it will be good you learn the programming basics. There are surely some good tutorials.
From what I see you just copy without understanding. So I am not sure it is worth giving you a working program.
Try to reuse the scripts that are here. There are many so test them and find the one you need.

1 Like

See attached.
Polyline_ContainsPt_EntryLevel_V1.gh (130.4 KB)

1 Like

Nice one, 3mins 38 seconds for ~650,000 points in complex polyline boundary…

In fact, Elapsed is hideous: but the non EntryLevel version is strictly internal (as are all my thread safe // things). I’ll see if I can implement some derestricted Method for that one.