;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;                                                        ;;;;
;;;; Copyright (c) Jun. 2006 by Takehiko Nagakura.          ;;;;
;;;; All rights reserved.                                   ;;;;
;;;;                                                        ;;;;
;;;; Do not copy, use, modify or distribute this software   ;;;;
;;;; without written permission by Nagakura. Nagakura will  ;;;;
;;;; not be responsible for any consequence of its use.     ;;;;
;;;;                                                        ;;;;
;;;; Takehiko Nagakura  (e-mail: takehiko@mit.edu)          ;;;;
;;;;    Massachusetts Institute of Technology               ;;;;
;;;;    77 Massachusetts Ave. 10-472M, Cambridge, MA 02139  ;;;;
;;;;                                                        ;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;; Last updated October 1, 2006 by TN 


;;This program demonstrates various geometric utilities.

; (defun c:r () (load "list_01.lsp"))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;Sets up layers

(command "cmdecho" 0)
;(command "layer" "make" "connect" "color" 8 "connect" "") ; color 8 is gray
;(command "layer" "make" "outline" "color" "white" "outline" "")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; This checks if a given point is in a polygon defined by point_list.
; Point_list is in a form ( (x1 y1) (x2 y2) (x3 y3) .....  ).
; No two points in the list must be the same. The last point must not be
; the same as the first one since the polygon will be automatically closed.
; Returned value:
;     0 : point is on a side of the polygon
;     1 : point is outside of the polygon
;    -1 : point is inside of the polygon

(defun point-in-polygon (x y point-list / x1 x2 y1 y2 on-flag error-flag int-count)
  (setq error-flag nil)
  (setq on-flag nil)  ; will become t if the point is on a side
  (setq int-count 1)  ; will become -1 if the point is inside, 1 if outside
  (setq point-list (append point-list (list (car point-list)))) ; last point is the first point.
  (while (and (null on-flag) (cdr point-list))
    (setq pt1 (car point-list)) (setq x1 (car pt1) y1 (cadr pt1))
    (setq pt2 (cadr point-list)) (setq x2 (car pt2) y2 (cadr pt2))
    ; the strategy is to draw a horizontal ray from the point to the right
    ; and count the number of intersection between the ray and each side of the polygon.
    ; If the ray passes an endpoint of a side, it counts only if the side is below
    ; the ray (meaning the other end of the side is lower than the ray).
  
	; Below is not so elegant but it works ok...
	(cond ((= y1 y2) ; ignore this unless the point is on this side    
             (cond ((and (= y1 y) (or (<= x1 x x2) (<= x2 x x1))) (setq on-flag t))
                   (t nil)))
		  ((or (< y1 y2 y) (< y y1 y2)) nil);  horizontal line does not intersect the side
          ((or (< y2 y1 y) (< y y2 y1)) nil);  horizontal line does not intersect the side
		  ((or (< y1 y y2) (< y2 y y1)) ; horizontal line crosses the side
            (setq xint (+ x1 (/ (* (- y y1) (- x2 x1)) (float (- y2 y1)))))
			(cond ((= x xint) (setq on-flag t))   ; point is on the side
                  ((< x xint) (setq int-count (* int-count -1))) ; point is left of the side
                  (t nil)))
          ((= y1 y) 
            (cond ((= x x1) (setq on-flag t))
                  ((and (< x x1) (< y2 y)) (setq int-count (* int-count -1))) 
				   ; side is lower than the ray, so this touching point count.
                  (t nil)))
          ((= y2 y)
            (cond ((= x x1) (setq on-flag t))
                  ((and (< x x1) (< y1 y)) (setq int-count (* int-count -1))) 
				   ; side is lower than the ray, so this touching point count.
                  (t nil)))
          (t (setq error-flag t)))
;    (print (list pt1 pt2 int-count ))
    (setq point-list (cdr point-list))
  ) ; end of while
  (cond (error-flag (print "error in point-in-polygon")) ; this should not happen...
        (on-flag    0)
        (t          int-count))
) 

(defun c:demo () 
 (terpri)
 (princ "(point-in-polygon 0.5 1   (list '(0 0) '(1 0) '(1 1) '(0 2) )) -> " )
  (print (point-in-polygon 0.5 1   (list '(0 0) '(1 0) '(1 1) '(0 2) )))
 (print "(point-in-polygon 0.5 0.1 (list '(0 0) '(1 0) '(1 1) '(0 2) )) -> " )
  (print (point-in-polygon 0.5 0.1 (list '(0 0) '(1 0) '(1 1) '(0 2) )))
 (print "(point-in-polygon 0.5 2   (list '(0 0) '(1 0) '(1 1) '(0 2) )) -> " )
  (print (point-in-polygon 0.5 2   (list '(0 0) '(1 0) '(1 1) '(0 2) )))
 (print "(point-in-polygon -20 0   (list '(0 0) '(1 0) '(1 1) '(0 2) )) -> " )
  (print (point-in-polygon -20 0   (list '(0 0) '(1 0) '(1 1) '(0 2) )))_
 (print "(point-in-polygon 0 2     (list '(0 0) '(1 0) '(1 1) '(0 2) )) -> " )
  (print (point-in-polygon 0 2     (list '(0 0) '(1 0) '(1 1) '(0 2) )))
 (print "(point-in-polygon -1 2    (list '(0 0) '(1 0) '(1 1) '(0 2) )) -> " )
  (print (point-in-polygon -1 2    (list '(0 0) '(1 0) '(1 1) '(0 2) )))
 (print "(point-in-polygon 1 1     (list '(0 0) '(1 0) '(1 1) '(0 2) )) -> " )
  (print (point-in-polygon 1 1     (list '(0 0) '(1 0) '(1 1) '(0 2) )))
)