Determine a point is inside of a polygon or outside...

The fundamental algorithm looks very similar to my CCSpointInPolygon implementation in the solution I reference above - here's the same function with an "ab" prefix (I tend to convert the code to use a Cadence Customer Support prefix when publishing solutions). It's in a LISP-style, but you get the picture:

/*************************************************************************
*                                                                        *
*                    (abPointInPolygon point points)                     *
*                                                                        *
*  Uses a ray casting approach to count if the number of intersections   *
* is even or odd. Even means the point is outside, and odd means inside. *
*     Returns t if inside the polygon. Note that the algorithm will      *
*   ensure that for abutting polygons, it is only inside one of them.    *
* So, for a single polygon, needs to be combined with abPointOnBoundary  *
*                   to know if on boundary or inside.                    *
*                                                                        *
*                     Based on Jordan curve theorem                      *
*           See http://en.wikipedia.org/wiki/Point_in_polygon            *
*                                                                        *
*************************************************************************/

(defun abPointInPolygon (point points)
  (let (inside ptj 
	       (testX (car point)) 
	       (testY (cadr point)))
    (setq ptj (car (last points)))
    (foreach pti points
	     (when
	       (and
		 (nequal
		   (greaterp (yCoord pti) testY)
		   (greaterp (yCoord ptj) testY))
		 (lessp
		   testX
		   (plus
		     (quotient
		       (times
			 (difference (xCoord ptj) (xCoord pti))
			 (difference testY (yCoord pti))
			 )
		       (difference (yCoord ptj) (yCoord pti))
		       )
		     (xCoord pti)
		     )
		   )
		 )
	       (setq inside (null inside))
	       )
	     (setq ptj pti)
	     )
    inside
    )
  )

The one thing that's unnecessary in the code above is the conversion of the list into arrays - and in fact the populating of the arrays is inefficient as it uses a for loop together with nth. Most of the time that's probably not a big deal because the number of points in a polygon will often be small, but for large polygons the for loops will be O(N**2) rather than O(N) as it would have been if a foreach had been used.

Kind Regards,

Andrew.

The fundamental algorithm looks very similar to my CCSpointInPolygon implementation in the solution I reference above - here's the same function with an "ab" prefix (I tend to convert the code to use a Cadence Customer Support prefix when publishing solutions). It's in a LISP-style, but you get the picture:

/*************************************************************************
*                                                                        *
*                    (abPointInPolygon point points)                     *
*                                                                        *
*  Uses a ray casting approach to count if the number of intersections   *
* is even or odd. Even means the point is outside, and odd means inside. *
*     Returns t if inside the polygon. Note that the algorithm will      *
*   ensure that for abutting polygons, it is only inside one of them.    *
* So, for a single polygon, needs to be combined with abPointOnBoundary  *
*                   to know if on boundary or inside.                    *
*                                                                        *
*                     Based on Jordan curve theorem                      *
*           See http://en.wikipedia.org/wiki/Point_in_polygon            *
*                                                                        *
*************************************************************************/

(defun abPointInPolygon (point points)
  (let (inside ptj 
	       (testX (car point)) 
	       (testY (cadr point)))
    (setq ptj (car (last points)))
    (foreach pti points
	     (when
	       (and
		 (nequal
		   (greaterp (yCoord pti) testY)
		   (greaterp (yCoord ptj) testY))
		 (lessp
		   testX
		   (plus
		     (quotient
		       (times
			 (difference (xCoord ptj) (xCoord pti))
			 (difference testY (yCoord pti))
			 )
		       (difference (yCoord ptj) (yCoord pti))
		       )
		     (xCoord pti)
		     )
		   )
		 )
	       (setq inside (null inside))
	       )
	     (setq ptj pti)
	     )
    inside
    )
  )

The one thing that's unnecessary in the code above is the conversion of the list into arrays - and in fact the populating of the arrays is inefficient as it uses a for loop together with nth. Most of the time that's probably not a big deal because the number of points in a polygon will often be small, but for large polygons the for loops will be O(N**2) rather than O(N) as it would have been if a foreach had been used.

Kind Regards,

Andrew.