;;; -*- Mode: Lisp; Package: DESIGN; Syntax: Ansi-common-lisp -*-

;; Angle sorting

;;; Is the vector [x1,y1] less-than-in-angle than [x2,y2]
;;; where the "least" angle is in the positive-X-axis direction,
;;; and angles increase counter-clockwise.


(defun angle-< (x1 y1 x2 y2)
  (macrolet ((tan-branch (x y)
               `(if (> ,x 0) (if (> ,y 0) 1 3) 2)))
    (let ((tan-branch-1 (tan-branch x1 y1))
          (tan-branch-2 (tan-branch x2 y2)))
      (declare (fixnum tan-branch-1 tan-branch-2))
      (cond ((< tan-branch-1 tan-branch-2)
             t)
            ((> tan-branch-1 tan-branch-2)
             nil)
            (t ; (= tan-branch-1 tan-branch-2)
             (let ((y1x2 (* y1 x2))
                   (y2x1 (* y2 x1)))
               (if (= y1x2 y2x1)
                   (< y2 y1)
                   (< y1x2 y2x1))))))))

(defun point-< (pt1 pt2)
  (angle-< (point-x pt1) (point-y pt1) (point-x pt2) (point-y pt2)))

;; would be nice if segment endpoints were stored in order (e.g. endpoint1 < endpoint2)

(defun edge-< (edge1 edge2)
  (flet ((edge-with-endpoints (pt1 pt2)
	   (if (or (and (eq (endpoint1 edge1) pt1)
			(eq (endpoint2 edge1) pt2))
		   (and (eq (endpoint1 edge1) pt2)
			(eq (endpoint2 edge1) pt1)))
	       edge1 edge2)))
  (let ((endpoints (sort (append (endpoints edge1) (endpoints edge2)) #'point-<)))
    (values (list (edge-with-endpoints (first endpoints) (second endpoints))
		  (edge-with-endpoints (third endpoints) (fourth endpoints)))
	    endpoints))))