Author Topic: IsPointInside for Polyline  (Read 9538 times)

0 Members and 1 Guest are viewing this topic.

kaefer

  • Guest
IsPointInside for Polyline
« on: August 01, 2011, 02:36:34 AM »
There have been various solutions to decide if a point resides inside a Curve, e.g.in LE's PolyClass, which either operate on straight lines only or involve a trade-off between speed and accuracy.

I haven't seen yet an implementation using a CurveCurveIntersector, checking the number of intersections of a ray extending from the point in question. Here goes:

Code: [Select]
    public static class Extensions
    {
        public static bool IsPointInside(this Polyline pl, Point2d pt)
        {
            Curve2d[] ca = new Curve2d[pl.NumberOfVertices];
            for(int i = 0; i < pl.NumberOfVertices; i++)
            {
                bool last = i == pl.NumberOfVertices - 1;
                Point2d sp = pl.GetPoint2dAt(i);
                Point2d ep = pl.GetPoint2dAt(last ? 0 : i + 1);
                double b = last && !pl.Closed ? 0.0 : pl.GetBulgeAt(i);
                if(b == 0.0)
                    ca[i] = new LineSegment2d(sp, ep);
                else
                    ca[i] = new CircularArc2d(sp, ep, b, false);
            }
            int n = 0;
            using(CompositeCurve2d c2d = new CompositeCurve2d(ca))
            using(Ray2d r2d = new Ray2d(pt, Vector2d.XAxis))
            using(CurveCurveIntersector2d cci2d = new CurveCurveIntersector2d(c2d, r2d))
            {   
                for(int i = 0; i < cci2d.NumberOfIntersectionPoints; i++)
                    if(cci2d.IsTransversal(i)) n++;
            }
            return(n % 2 != 0);
        }
    }

This will obviously fail to return consistent results if the point is on the Polyline, that condition need to be checked separately. But it will work regardless of the Polyline's self-intersections. Here's a test command for it:

Code: [Select]
    public class Commands
    {
        Database db;
        Editor ed;
        public Commands()
        {
            Document doc = AcadApp.DocumentManager.MdiActiveDocument;
            db = doc.Database;
            ed = doc.Editor;
        }
        [CommandMethod("TestIsPointInside")]
        public void testIsPointInside()
        {
            PromptEntityOptions peo = new PromptEntityOptions("\nSelect  a Polyline: ");
            peo.SetRejectMessage("\nOnly Polyline permitted. ");
            peo.AddAllowedClass(typeof(Polyline), true);

            PromptEntityResult per = ed.GetEntity(peo);
            if (per.Status != PromptStatus.OK) return;

            PromptIntegerOptions pio = new PromptIntegerOptions("\nNumber of points: ");
            pio.AllowNegative = false;
            pio.AllowNone = false;
            pio.AllowZero = false;
            PromptIntegerResult pir = ed.GetInteger(pio);
            if (pir.Status != PromptStatus.OK) return;

            using (Transaction tr = db.TransactionManager.StartTransaction())
            {
                Polyline pl = (Polyline)tr.GetObject(per.ObjectId, OpenMode.ForRead);
                BlockTableRecord cs = (BlockTableRecord)tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite);

                Extents3d ext = pl.GeometricExtents;
                double dx = ext.MaxPoint.X - ext.MinPoint.X;
                double dy = ext.MaxPoint.Y - ext.MinPoint.Y;
                double cenx = ext.MinPoint.X + dx / 2.0;
                double ceny = ext.MinPoint.Y + dy / 2.0;
                dx = dx * 1.2; dy = dy * 1.2;
                double minx = cenx - dx / 2.0;
                double miny = ceny - dy / 2.0;
                Random rnd = new System.Random();
                for (int i = 0; i < pir.Value; i++)
                {
                    Point2d pt = new Point2d(minx + rnd.NextDouble() * dx, miny + rnd.NextDouble() * dy);
                    DBPoint dp = new DBPoint(new Point3d(pt.X, pt.Y, 0.0));
                    if(pl.IsPointInside(pt))
                        dp.ColorIndex = 1;
                    cs.AppendEntity(dp);
                    tr.AddNewlyCreatedDBObject(dp, true);
                }
                tr.Commit();
            }
        }
    }

LE3

  • Guest
Re: IsPointInside for Polyline
« Reply #1 on: August 01, 2011, 06:24:10 PM »
hi kaefer,

the idea behind that function was to avoid the use of any object or rays apart of that i was learning c#(and still) (that was discussed 15+ years ago in the adesk forums by many of the masters of disasters back then - and was based on John Uhden idea).

le!

kaefer

  • Guest
Re: IsPointInside for Polyline
« Reply #2 on: August 01, 2011, 06:50:58 PM »
the idea behind that function was to avoid the use of any object or rays

doing heavy maths in a tight loop. Why, I wouldn't dare to question the ways it was done back then, only wondering if it was so much faster than the alternatives. I can dimly remember the time a costly numeric coprocessor was required to run Autodesk's product.

I'm amazed how fast the composite curve can be assembled and disposed, having it left inside the test loop. Here's a still unoptimized generalization for Curve:

Code: [Select]
    public static class Extensions
    {
        public static bool IsBetween (this Point2d pt,  Point2d p1, Point2d p2)
        {
            return((pt - p1).GetNormal() == (p2 - pt).GetNormal());
        }
        public static Point2d To2d (this Point3d pt)
        {
            return(new Point2d(pt.X, pt.Y));
        }
        public static bool IsPointInside(this Curve c, Point2d pt)
        {
            if(c.StartParam != 0.0 || (c.EndParam - Math.Truncate(c.EndParam) != 0.0))
                throw(new ArgumentException("Invalid Curve Parameter"));

            int n = (int)c.EndParam;
            Curve2d[] ca = new Curve2d[n];
            for(int i = 0; i < n; i++)
            {
                Point2d sp = (c.GetPointAtParameter(i)).To2d();
                Point2d mp = (c.GetPointAtParameter(i + 0.5)).To2d();
                Point2d ep = (c.GetPointAtParameter(i + 1.0)).To2d();
                if(mp.IsBetween(sp, ep))
                    ca[i] = new LineSegment2d(sp, ep);
                else
                    ca[i] = new CircularArc2d(sp, mp, ep);
            }
            n = 0;
            using(CompositeCurve2d c2d = new CompositeCurve2d(ca))
            using(Ray2d r2d = new Ray2d(pt, Vector2d.XAxis))
            using(CurveCurveIntersector2d cci2d = new CurveCurveIntersector2d(c2d, r2d))
            {   
                for(int i = 0; i < cci2d.NumberOfIntersectionPoints; i++)
                    if(cci2d.IsTransversal(i)) n++;
            }
            return(n % 2 != 0);
        }
    }

LE3

  • Guest
Re: IsPointInside for Polyline
« Reply #3 on: August 01, 2011, 07:15:25 PM »
hope to get a chance to test your function, have not been able to run any code to test in autocad for the last 4+ months and counting...

le!

LE3

  • Guest
Re: IsPointInside for Polyline
« Reply #4 on: August 01, 2011, 08:47:09 PM »

Jeff H

  • Needs a day job
  • Posts: 6144
Re: IsPointInside for Polyline
« Reply #5 on: August 02, 2011, 03:56:14 AM »
Here is a cheating way and probably has gotchas like if a polyline that is self intersecting etc.....

Just added a DBPoint then checked if its Objectid was in WindowPolygon and if not checked if it is in a CrossingPolygon
Then erased Point

Code: [Select]
  [CommandMethod("CheckForPointInsideClosedPloyline")]
        public void CheckForPointInsideClosedPloyline() // This method can have any name
        {
            Document doc = Application.DocumentManager.MdiActiveDocument;
            Database db = doc.Database;
            Editor ed = doc.Editor;
            Point3dCollection vertices = new Point3dCollection();
            ObjectId dbPntId = ObjectId.Null;

            using (Transaction trx = db.TransactionManager.StartTransaction())
            {
                BlockTable bt = (BlockTable)trx.GetObject(db.BlockTableId, OpenMode.ForRead);
                BlockTableRecord btr = (BlockTableRecord)trx.GetObject(db.CurrentSpaceId, OpenMode.ForWrite);

                Point3d pnt = ed.GetPoint("\nSelectPoint").Value;
                Polyline polyLine = (Polyline)trx.GetObject(ed.GetEntity("\nSelect PolyLine").ObjectId, OpenMode.ForRead);

                DBPoint dbPnt = new DBPoint(pnt);
                dbPntId = btr.AppendEntity(dbPnt);
                trx.AddNewlyCreatedDBObject(dbPnt, true);
               

                for (int i = 0; i < polyLine.NumberOfVertices; i++)
                {
                  vertices.Add(polyLine.GetPoint3dAt(i)); 
                }
                trx.Commit();
            }


            using (Transaction trx = db.TransactionManager.StartTransaction())
            {

                DBPoint dbPnt = (DBPoint)trx.GetObject(dbPntId, OpenMode.ForWrite);
                SelectionSet ssWP = ed.SelectWindowPolygon(vertices).Value;

                if (ssWP != null)
                {
                    foreach (ObjectId id in ssWP.GetObjectIds())
                    {
                        if (id == dbPntId)
                        {
                            ed.WriteMessage("\nIs Inside");
                            dbPnt.Erase();
                            trx.Commit();
                            return;
                        }
                    }
                }

                SelectionSet ssCP = ed.SelectCrossingPolygon(vertices).Value;

                if (ssCP != null)
                {
                    foreach (ObjectId id in ssCP.GetObjectIds())
                    {
                        if (id == dbPntId)
                        {
                            ed.WriteMessage("\nIs On Polyline");
                            dbPnt.Erase();
                            trx.Commit();
                            return;
                        }
                    }
                }

                ed.WriteMessage("\nIs not Inside or On Polyline");
                dbPnt.Erase();
                trx.Commit();
            }
        }


kaefer

  • Guest
Re: IsPointInside for Polyline
« Reply #6 on: August 02, 2011, 05:40:58 AM »
also, no idea if you have seen this:
http://www.theswamp.org/index.php?topic=17222.msg207884#msg207884

Yeah, that's another one. Won't work under 2010 here (wants AcMPolygonObj18d.dbx, wassup?) and bombs the first time when run under 2011 (Access Violation Reading 0x0000 ... in acmpolygonmgd.dll) but otherwise it's fine and runs even half as fast as the ray intersector; 1.4 s instead of 0.7 s for 10,000 points.

BTW le, would you consider yourself yet another victim of the burst property bubble?

Here is a cheating way and probably has gotchas like if a polyline that is self intersecting etc....

Wouldn't support arc segments then? Did that in lisp a while ago, interpolating arcs with lines for Window-/CrossingPolygon. Works too, in a way.

kaefer

  • Guest
Re: IsPointInside for Polyline
« Reply #7 on: August 02, 2011, 04:49:29 PM »
Uh-oh, I had overlooked the possibility of open Curves. And I could have special cased Arc and Circle. There goes the beauty of simplicity...

Code: [Select]
    // Extensions to convert Curve to CompositeCurve2d
    public static class Extensions
    {
        public static bool IsBetween (this Point2d pt,  Point2d p1, Point2d p2)
        {
            return((pt - p1).GetNormal() == (p2 - pt).GetNormal());
        }
        public static Point2d To2d (this Point3d pt)
        {
            return(new Point2d(pt.X, pt.Y));
        }
        public static Point2d GetPointAtRelativeParam(this Curve c, double rpm)
        {
            double spm = c.StartParam;
            double epm = c.EndParam;
            return c.GetPointAtParameter(spm + (epm - spm) * rpm).To2d();
        }
        public static Curve2d[] ToCurve2dArray(this Arc a)
        {
            Point2d sp = a.GetPointAtRelativeParam(0.0);
            Point2d mp = a.GetPointAtRelativeParam(0.5);
            Point2d ep = a.GetPointAtRelativeParam(1.0);
            return new Curve2d[2]{
                new CircularArc2d(sp, mp, ep),
                new LineSegment2d(ep, sp)
            };
        }
        public static Curve2d[] ToCurve2dArray(this Circle ci)
        {
            Point2d sp = ci.GetPointAtRelativeParam(0.0);
            Point2d q1 = ci.GetPointAtRelativeParam(0.25);
            Point2d ep = ci.GetPointAtRelativeParam(0.5);
            Point2d q3 = ci.GetPointAtRelativeParam(0.75);
            return new Curve2d[2]{
                new CircularArc2d(sp, q1, ep),
                new CircularArc2d(ep, q3, sp)
            };
        }
        public static Curve2d[] ToCurve2dArray(this Curve c)
        {
            if (c.StartParam != 0.0 || (c.EndParam - Math.Truncate(c.EndParam) != 0.0))
                throw (new ArgumentException("Invalid Curve Parameter"));

            int n = (int)c.EndParam;
            Curve2d[] ca = new Curve2d[c.Closed ? n : n + 1];
            Point2d sp0 = (c.GetPointAtParameter(0.0)).To2d();
            Point2d sp = sp0;
            for (int i = 0; i < n; i++)
            {
                Point2d mp = (c.GetPointAtParameter(i + 0.5)).To2d();
                Point2d ep = (c.GetPointAtParameter(i + 1.0)).To2d();
                if (mp.IsBetween(sp, ep))
                    ca[i] = new LineSegment2d(sp, ep);
                else
                    ca[i] = new CircularArc2d(sp, mp, ep);
                sp = ep;
            }
            if (!c.Closed)
                ca[n] = new LineSegment2d(sp, sp0);
            return ca;
        }
        public static CompositeCurve2d ToCompositeCurve2d(this Curve c)
        {
            Curve2d[] ca;
            Arc a = c as Arc;
            if (a != null)
                ca = a.ToCurve2dArray();
            else
            {
                Circle ci = c as Circle;
                if (ci != null)
                    ca = ci.ToCurve2dArray();
                else
                    ca = c.ToCurve2dArray();
            }
            return new CompositeCurve2d(ca);
        }
        public static bool IsPointInside(this Curve c, Point2d pt)
        {
            int n = 0;
            using(CompositeCurve2d c2d = c.ToCompositeCurve2d())
            using(Ray2d r2d = new Ray2d(pt, Vector2d.XAxis))
            using(CurveCurveIntersector2d cci2d = new CurveCurveIntersector2d(c2d, r2d))
            {   
                for(int i = 0; i < cci2d.NumberOfIntersectionPoints; i++)
                    if(cci2d.IsTransversal(i)) n++;
            }
            return(n % 2 != 0);
        }
    }

LE3

  • Guest
Re: IsPointInside for Polyline
« Reply #8 on: August 02, 2011, 06:49:28 PM »
BTW le, would you consider yourself yet another victim of the burst property bubble?

No idea what do you mean by that..... :)

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: IsPointInside for Polyline
« Reply #9 on: March 07, 2014, 05:34:05 PM »
Hi,

This post is quite old but this thread remind me the MPolygon route.
Needs to reference AcMPolygonMGD.dll from the installation folder.

This works for me (tested on A2011 to A2014).
For points on boundary, the tolerance argument set to 0.0 returns false and true with Tolerance.Global.EqualPoint.
It works with self intersecting polylines.


<EDIT> new version
The IsPointInside() extension method returns PointContainment enum member (Inside, Outside, OnBoundary)

Code - C#: [Select]
  1.     public static class PolylineExtension
  2.     {
  3.         public enum PointContainment { Inside, OutSide, OnBoundary }
  4.  
  5.         // Insures the AcMPolygonObj##.dbx object enabler is loaded when a method is callled
  6.         static PolylineExtension()
  7.         {
  8.             Autodesk.AutoCAD.Runtime.SystemObjects.DynamicLinker.LoadModule(
  9.                 "AcMPolygonObj" + AcAp.Version.Major + ".dbx", false, false);
  10.         }
  11.  
  12.         // Creates a MPolygon from a polyline using Tolerance.Global.EqualPoint
  13.         public static MPolygon MakeMPolygon(this Polyline pline)
  14.         {
  15.             return pline.MakeMPolygon(Tolerance.Global.EqualPoint);
  16.         }
  17.  
  18.         // Creates a MPolygon from a polyline using the specfied tolerance
  19.         public static MPolygon MakeMPolygon(this Polyline pline, double tolerance)
  20.         {
  21.             if (pline == null)
  22.                 throw new ArgumentNullException("pline");
  23.  
  24.             if (!pline.Closed)
  25.                 throw new ArgumentException("polyline must be closed");
  26.  
  27.             MPolygon mPolygon = new MPolygon();
  28.             mPolygon.AppendLoopFromBoundary(pline, false, tolerance);
  29.             mPolygon.Elevation = pline.Elevation;
  30.             mPolygon.Normal = pline.Normal;
  31.             return mPolygon;
  32.         }
  33.  
  34.         // Returns the PointContainment using Tolerance.Global.EqualPoint
  35.         public static PointContainment GetPointContainment(this Polyline pline, Point3d point)
  36.         {
  37.             return pline.GetPointContainment(point, Tolerance.Global.EqualPoint);
  38.         }
  39.  
  40.         // Returns the PointContainment using the specified tolerance (equal or greater to Tolerance.Global)
  41.         public static PointContainment GetPointContainment(this Polyline pline, Point3d point, double tolerance)
  42.         {
  43.             tolerance = Math.Max(tolerance, Tolerance.Global.EqualPoint);
  44.             using (MPolygon mPolygon = pline.MakeMPolygon())
  45.             {
  46.                 for (int i = 0; i < mPolygon.NumMPolygonLoops; i++)
  47.                 {
  48.                     if (mPolygon.IsPointOnLoopBoundary(point, i, tolerance))
  49.                         return PointContainment.OnBoundary;
  50.                 }
  51.                 if (mPolygon.IsPointInsideMPolygon(point, tolerance).Count == 1)
  52.                     return PointContainment.Inside;
  53.                 return PointContainment.OutSide;
  54.             }
  55.         }
  56.     }
« Last Edit: March 08, 2014, 05:09:33 AM by gile »
Speaking English as a French Frog

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
Re: IsPointInside for Polyline
« Reply #10 on: June 24, 2016, 06:45:04 PM »
Here is a cheating way and probably has gotchas like if a polyline that is self intersecting etc.....

Jeff, after searching for a while on the best way to do this, I've decided that your cheating way is a nice simple solution to a complex problem.

Thank you!

Jeff H

  • Needs a day job
  • Posts: 6144
Re: IsPointInside for Polyline
« Reply #11 on: June 25, 2016, 02:18:47 AM »
Here is a cheating way and probably has gotchas like if a polyline that is self intersecting etc.....

Jeff, after searching for a while on the best way to do this, I've decided that your cheating way is a nice simple solution to a complex problem.

Thank you!
If you ain't cheating your ain't trying
Thanks

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
Re: IsPointInside for Polyline
« Reply #12 on: June 27, 2016, 09:36:25 AM »
Welp. You were right Jeff, the selectionset method is pretty particular about the order of the points (self crossing). I couldn't just pass the points from a polyline (even if it didn't cross) and expect good results, prompt result would throw an error flag. So much for getting away with cheating.. :)

Rather than trouble shooting the cheat, I've implemented Giles solution utilizing AcMPolygonMGD.dll and it seems to be working well.

Giles: Thank you. :)
« Last Edit: July 24, 2016, 02:41:30 PM by Atook »