;; | -----------------------------------------------------------------------------
;; | GE_PtInPoly
;; | -----------------------------------------------------------------------------
;; | Function :	Detects if a point is within a closed polygon.  This is done by
;; |			drawing a line from pt to x+ direction and count the number of
;; |			times it cuts the polygon under test. An even number of cut
;; |			indicates that the pt is outside the polygon.
;; | Argument : 'pt'    - point ot be tested 
;; |            'vlist' - List of points forming the polgon
;; |            'flag'  - If 'T', point on the line is inside else outside
;; |
;; | Return   : T if point is inside else nil 
;; | Updated  : July 24, 1999
;; | e-mail   : rakesh.rao@4d-technologies.com 
;; | Web      : www.4d-technologies.com
;; | -----------------------------------------------------------------------------


(defun GE_PtInPoly( pt vlist flag / NumInts diff cnt online p1 p1code p1x p1y p2 p2code 
                               p2x p2y ttl x xdiff xx y ydiff Idx len)

(if (not (equal (car vlist) (last vlist)))
	(setq vlist (append vlist (list (car vlist))))
)

(setq
	X       (car pt)
	Y       (cadr pt)
	len     (length vlist)
	cnt     0
	Idx     0
	NumInts 0
	OnLine  nil
)

(while (and (not OnLine) (< cnt len))
(setq
	p2     (nth cnt vlist)
	p2x    (car p2)
	p2y    (cadr p2)
	p2code (if (>= p2y y) 2 0)						; add 2 if p2 is higher
	p2code (if (>= p2x x) (1+ p2code) p2code)		; add 1 if p2 on the right
)
              
(if p1
(setq
	diff  (boole 6 p1code p2code)					; xor to see if quadrant has changed eg 1-2
	ydiff (boole 1 diff 2)							; AND to see if 2nd bit has chnaged => crssing of y axis
	xdiff (boole 1 diff 1)							; and to see if 1st bit changed
	p1x   (car p1)
	p1y   (cadr p1)
))

; ** check to see if segment has crossed x+ line
(if (= ydiff 2)															; 0001 (or 1) means y axis crossed
(progn
	(setq xx (+ p1x (* (/ (- p2x p1x) (- p2y p1y) ) (- y p1y))))		; x value of intersection pt
	(cond
		; ** Check to see if point is on the line
		((equal xx x 0.0001)        ; is it on the line?
			(setq online T)			; force Outside after adding 1
		)

		; ** check if pt is on the line
		((> xx x)					; is intersect on RHS?
			(setq NumInts (1+ NumInts))
		)
	)
))

; **Special treatment for horizontal line
(if (and (= xdiff 1)(= y p1y p2y )) (setq OnLine T))

; ** Proceed to next segment 
(setq
	p1code p2code
	p1     p2
	cnt    (1+ cnt) 
)
)

(if Online
	flag						; flag = T means ptonline is inside poly
	(= (boole 1 NumInts 1) 0001)	; odd number of crosing - masking off all bots > 1 (and 0001 with result)
)
)