;;; This software is being provided to you, the LICENSEE, by the
;;; Massachusetts Institute of Technology (M.I.T.), and the NEC Research
;;; Institute (NECI) under the following license.  By obtaining, using
;;; and/or copying this software, you agree that you have read,
;;; understood, and will comply with these terms and conditions:
;;; 
;;; Permission to use, copy, modify and distribute, including the right to
;;; grant others rights to distribute at any tier, this software and its
;;; documentation for research purposes only and without fee or royalty is
;;; hereby granted, provided that you agree to comply with the following
;;; copyright notice and statements, including the disclaimer, and that
;;; the same appear on ALL copies of the software and documentation,
;;; including modifications that you make for internal use or for
;;; distribution:
;;; 
;;; Copyright 1995 by the Massachusetts Institute of Technology.  All
;;; rights reserved.  Copyright 1995 by NEC Research Institute Inc. All
;;; rights reserved
;;; 
;;; THIS SOFTWARE IS PROVIDED "AS IS", AND M.I.T. and NECI MAKE NO
;;; REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.  By way of example,
;;; but not limitation, M.I.T. and NECI MAKE NO REPRESENTATIONS OR
;;; WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE OR
;;; THAT THE USE OF THE LICENSED SOFTWARE OR DOCUMENTATION WILL NOT
;;; INFRINGE ANY THIRD PARTY PATENTS, COPYRIGHTS, TRADEMARKS OR OTHER
;;; RIGHTS.
;;; 
;;; The name of the Massachusetts Institute of Technology or M.I.T., or
;;; NEC Research Institute, or NECI may NOT be used in advertising or
;;; publicity pertaining to distribution of the software.  Title to
;;; copyright in this software and any associated documentation shall at
;;; all times remain with M.I.T. and NECI, and USER agrees to preserve
;;; same.
;;; 

;;; -*- Mode: LISP; Base: 10; Package: 2DG; Syntax: Common-Lisp -*-
(in-package '2DG)

(export '(colinear? colinear-point-and-line? colinear-line-and-line? colinear-points?))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Colinearity
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun COLINEAR? (object-1 object-2)
  "Returns T if OBJECT-1 and OBJECT-2 are colinear."
  (cond ((or (null object-1) (null object-2))
	 ;; We include this case for calls where one of the objects is itself returned by a function
	 nil)
	((point-p object-1)
	 ;; OBJECT-1 is a point
	 (cond ((point-p object-2)
		t)				;points are always colinear
	       ((line-segment-p object-2)
		(colinear-point-and-line? object-1 (g-coerce object-2 'line)))
	       ((line-p object-2)
		(colinear-point-and-line? object-1 object-2))
	       (t
		(error "Can't determine colinearity between ~A and ~A" object-1 object-2))))
	((point-p object-2)
	 ;; OBJECT-2 is a point, but OBJECT-1 is not
	 (colinear? object-2 object-1))
	((line-segment-p object-1)
	 ;; OBJECT-1 is a line segment
	 (cond ((line-segment-p object-2)
		(colinear-line-and-line? (g-coerce object-1 'line) (g-coerce object-2 'line)))
	       ((line-p object-2)
		(colinear-line-and-line? (g-coerce object-1 'line) object-2))
	       (t
		(error "Can't determine colinearity between ~A and ~A" object-1 object-2))))
	((line-segment-p object-2)
	 ;; OBJECT-2 is a line segment, but OBJECT-1 is not
	 (colinear? object-2 object-1))
	((line-p object-1)
	 ;; OBJECT- is a line
	 (cond ((line-p object-2)
		(colinear-line-and-line? object-1 object-2))
	       (t
		(error "Can't determine colinearity between ~A and ~A" object-1 object-2))))
	(t
	 (error "Can't determine colinearity between ~A and ~A" object-1 object-2))))

(defun THREE-POINTS-COLINEAR? (point point-1 point-2)
  "Returns T if POINT, POINT-1, and POINT-2 are colinear."
  (colinear-points? (list point point-1 point-2)))

(defun COLINEAR-POINT-AND-LINE? (point line)
  "
  Purpose:  Determine if a point is colinear with a line
  Args:	POINT	-- a point (X Y)
	LINE	-- a line
  Returns:  T if the point and line segment are colinear, Nil otherwise.
  "
  (declare (values boolean))
  (colinear-points? (list point (first-point line) (second-point line))))
						
(defun COLINEAR-LINE-AND-LINE? (line-1 line-2)
  "
  Purpose:  Determine if LINE-1 and LINE-2 are colinear
  Returns:  T if the line segments are colinear
  "
  (declare (values boolean))
  (colinear-points? (list (line-point-1 line-1) (line-point-2 line-1)
			  (line-point-1 line-2) (line-point-2 line-2))))

(defun COLINEAR-POINTS? (pts)
  "
  Points are colinear when they could all be moved by less than *epsilon* and line up exactly.
  A quick approximation to testing that is to find the line connecting the two exteme points,
  and test that no other point is more than *epsilon from this line.
  "
  (let ((max-squared-distance 0)
	(pt1)
	(pt2))
    (loop for p1 in pts
	  for rest-pts on (cdr pts)
	  doing
      (loop for p2 in rest-pts
	    doing
	(let ((squared-distance (distance-squared-between-point-and-point p1 p2)))
	  (when (<= max-squared-distance squared-distance)
	    (setf max-squared-distance squared-distance)
	    (setf pt1 p1)
	    (setf pt2 p2)))))
    (let ((line (make-line pt1 pt2)))
      (loop for pt in (remove pt1 (remove pt2 pts))
	    always
	      (~zerop (distance-between-point-and-line pt line))))))
