Check if a point is inside a polygon

How to tell if a point is inside a polygon?

(1) Area sum discrimination method: determine whether the area sum of the triangle formed by the target point and each side of the polygon is equal to the polygon, and if it is equal, it is inside the polygon.

(2) Angle sum discrimination method: judge whether the sum of the angle between the target point and all sides is 360 degrees, and if it is 360 degrees, it is inside the polygon.

(3) Guide line method: draw a ray from the target point and see the number of intersections between this ray and all sides of the polygon. If there are an odd number of intersections, it is inside, and if there is an even number of intersections, it is outside.

How to do it: Compare the Y coordinate of the test point with each point of the polygon, and you will get a list of intersections of the line where the test point is located and the polygon edge. In this example in the image below, there are 8 edges that intersect the row where the test point is located, and 6 edges that do not. If the number of points on both sides of the test point is an odd number, the test point is inside the polygon, otherwise it is outside the polygon. In this example there are 5 intersections to the left of the test point and three to the right, they are all odd, so the point is inside the polygon.

Algorithm diagram:

More specific graphic examples of this algorithm: http://alienryderflex.com/polygon/

Reference Code:

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) 
  {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

Internal implementation from a polygon:

      public bool IsInside(PointLatLng p)
      {
         int count = Points.Count;

         if(count < 3)
         {
            return false;
         }

         bool result = false;

         for(int i = 0, j = count - 1; i < count; i++)
         {
            var p1 = Points[i];
            var p2 = Points[j];

            if(p1.Lat < p.Lat && p2.Lat >= p.Lat || p2.Lat < p.Lat && p1.Lat >= p.Lat)
            {
               if(p1.Lng + (p.Lat - p1.Lat) / (p2.Lat - p1.Lat) * (p2.Lng - p1.Lng) < p.Lng)
               {
                  result = !result;
               }
            }
            j = i;
         }
         return result;
      }

Special case: The point to be detected is on a polymorphic edge, the result of the ray method is uncertain, and special processing is required (If the test point is on the border of the polygon, this algorithm will deliver unpredictable results).

Calculate the area of ​​a polygon:

        private static double SignedPolygonArea(List<PointLatLng> points)
        {
            // Add the first point to the end.
            int pointsCount = points.Count;
            PointLatLng[] pts = new PointLatLng[pointsCount + 1];
            points.CopyTo(pts, 0);
            pts[pointsCount] = points[0];

            for (int i = 0; i < pointsCount + 1; ++i)
            {
                pts[i].Lat = pts[i].Lat * (System.Math.PI * 6378137 / 180);
                pts[i].Lng = pts[i].Lng * (System.Math.PI * 6378137 / 180);
            }

            // Get the areas.
            double area = 0;
            for (int i = 0; i < pointsCount; i++)
            {
                area += (pts[i + 1].Lat - pts[i].Lat) * (pts[i + 1].Lng + pts[i].Lng) / 2;
            }

            // Return the result.
            return area;
        }

        /// <summary>
        /// Get the area of a polygon
        /// </summary>
        /// <param name="points"></param>
        /// <returns></returns>
        public static double GetPolygonArea(List<PointLatLng> points)
        {
            // Return the absolute value of the signed area.
            // The signed area is negative if the polygon is oriented clockwise.
            return Math.Abs(SignedPolygonArea(points));
        }

 

 

 

References:

http://alienryderflex.com/polygon/

http://en.wikipedia.org/wiki/Point_in_polygon

http://www.codeproject.com/Tips/84226/Is-a-Point-inside-a-Polygon

 

 

 

https://www.cnblogs.com/luxiaoxun/p/3722358.html

Tags: Algorithm

Posted by franko75 on Sat, 21 May 2022 21:28:54 +0300