Is Point inside Polygon or Block's Area?

[Anonymous]

Anyone come across a good method or the algebraic formula for a funtion to tell me if a point is inside a polygon or block's area? 

Or if a two blocks or polygons are overlapping area? 

[Alfred.NESWADBA]

Hi,

if you can convert Polylines to MPOLYGON-objects you do have the calculation of isPointInside as a function of the object itself.

Public Overridable Function IsPointInsideMPolygon(worldPoint As Autodesk.AutoCAD.Geometry.Point3d, tolerance As Double) As Autodesk.AutoCAD.Geometry.IntegerCollection
     Member von Autodesk.AutoCAD.DatabaseServices.MPolygon

- alfred -

[Anonymous]

Start here
http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

HomeBoy Out

[Anonymous]

Found a formula, link listed below and produced this, appears to work, but you may want to test to ensure it suits your needs.

//Point inside a polyline came from the Solution 2 (2d) section of this website http://paulbourke.net/geometry/insidepoly/

        /// <summary>
        /// Check if the point is within the polyline
        /// </summary>
        /// <param name="polygon"></param>
        /// <param name="pt"></param>
        /// <returns></returns>
        public static bool InsidePolygon(Polyline polygon, Point3d pt)
        {
            int n = polygon.NumberOfVertices;
           double angle=0;
           Point pt1 , pt2 ;

           for (int i = 0; i < n; i++)
           {
              pt1.X = polygon.GetPoint2dAt(i).X - pt.X;
              pt1.Y = polygon.GetPoint2dAt(i).Y - pt.Y;
              pt2.X = polygon.GetPoint2dAt((i+1)%n).X - pt.X;
              pt2.Y = polygon.GetPoint2dAt((i+1)%n).Y - pt.Y;
              angle += Angle2D(pt1.X,pt1.Y,pt2.X,pt2.Y);
           }

           if (Math.Abs(angle) < Math.PI)
              return false;
           else
              return true;
        }
        
        /// <summary>
        /// Point structure to add InsidePolygon function
        /// </summary>
        public struct Point
        {
            public double X, Y;
        };

        /*
           
        */
        /// <summary>
        /// Return the angle between two vectors on a plane
        /// The angle is from vector 1 to vector 2, positive anticlockwise
        /// The result is between -pi -> pi
        /// </summary>
        /// <param name="x1"></param>
        /// <param name="y1"></param>
        /// <param name="x2"></param>
        /// <param name="y2"></param>
        /// <returns></returns>
        public static double Angle2D(double x1, double y1, double x2, double y2)
        {
           double dtheta,theta1,theta2;

           theta1 = Math.Atan2(y1,x1);
           theta2 = Math.Atan2(y2, x2);
           dtheta = theta2 - theta1;
           while (dtheta > Math.PI)
               dtheta -= (Math.PI * 2);
           while (dtheta < -Math.PI)
               dtheta += (Math.PI * 2);
               return(dtheta);
        }

[Anonymous]

Hi,

what about this:

            public bool IsPointInPolyLine(Polyline Polyline, Point3d Point)

            {

                bool hIsInPLine = false;

                Point3d hPoint1 = Point;

                Point3d hPoint2 = PolarPoints(hPoint1, 0, 1);

                Vector3d hVector = hPoint2 - hPoint1;

                Ray hRay = new Ray();

                hRay.BasePoint = new Point3d(Point.X, Point.Y, 0);

                hRay.UnitDir = hVector;

                Point3dCollection hIntersectionPoints =

                        new Point3dCollection();

                Autodesk.AutoCAD.DatabaseServices.PlatformCompatibilityExtensionMethods.IntersectWith

                    (hRay, Polyline, Intersect.OnBothOperands, hIntersectionPoints);

                //hRay.IntersectWith(

                //  Polyline,

                //  Intersect.OnBothOperands,

                //  hIntersectionPoints, 0, 0);

                int hMod = hIntersectionPoints.Count % 2;

                if (hMod == 0)

                {

                    hIsInPLine = false;

                }

                else

                {

                    hIsInPLine = true;

                }

                return hIsInPLine;

            }

This method use a Ray to get the intersection with a polyline.

You get a error-message when yo use a 64 bit Windows but there is a workaround for that problem.

Regards Jürgen

[Alfred.NESWADBA]

Hi,

Attention! Both versions do have problems you should be aware of:

a) the version that summarizes the angles does only work on polylines with no arcs in it, that are not curved and not splined.

b) the version using ray and count the intersections will have two critical situations

• it the ray crosses the poly very near to a vertex, it sometimes returns 2 intersectionpoints instead of 1, because AutoCAD does extend a poly-segment a little bit (even not told to extend any object for intersection-calulation) look at this screenshot:

       

• Second situation is a (primitive/bad) version of creating islands with POLYLINES. The linework goes through the outline, than from one vertex to the inner border (island), around the island and back to the outer border. In this case you see a ray crossing two segments, one from outline to island and one from island to outline. So trying to get the intersectionpoints between the POLYLINE and the RAY should get 2 points ... but AutoCAD returns a collection (Point3DCollection) and within a collection double points are not allowed ... so you get at this point only one intersection back ==> and the result is wrong.

         

Important: I don't want to critism the above suggestions, I just want to inform about situations you should be prepared before start development.

- alfred -

[Anonymous]

Good point, my implementation is timber components which never have curves, so works well for me.

[Anonymous]

Thank you everyone for the help! Thanks again. 

Cheers!

[chiefbraincloud]

Hi Alfred,  FYI Point3dCollections do not require the contents to be distinct.  There are several functions in my code where I am taking the points of a polyline that is required to be a closed loop, in order to standardize the way the polylines were drawn, I test distance from the last point to the first, and if it is not 0 then I add the first point in the collection onto the end of the collection so that the first and last points in the collection are equal.

If your intersection example with the bad return is something you have experienced, then there is another reason for it which I am not sure of.  

[Alfred.NESWADBA]

Hi chiefbraincloud,

>> Point3dCollections do not require the contents to be distinct

Maybe, I have not tested it creating it by myself (as I'm using my own type of PointLists if I need it).

However, AutoCAD does not return 2 Intersections in the above sample (where the ray crosses two segments on the same point). And if I remember right, there are more Curve-functions also avoiding double/same points (neighboring) in the return collection.

For details I would have to search now, sorry to have no time at the moment, next time I get an example I hope to remember to this thread!

- alfred -