(defparameter *lines*
'((p0 p5 p8 p10)
(p0 p3 p7 p9)
(p0 p2 p4 p6)
(p0 p1)
(p1 p2 p3 p5)
(p1 p4 p7 p8)
(p1 p6 p9 p10))
"The lines in the figure. Each list corresponds to one line, with
the member symbols being the points on that line.")
(defparameter *points*
(delete-duplicates (loop for l in *lines* append l) :test #'eq)
"The points in the figure. Generated from *lines*.")
(defun symbol< (sym1 sym2)
"Ordering predicate for symbols, based on SYMBOL-NAME."
(string< (symbol-name sym1) (symbol-name sym2)))
(defun canonicalize (triangle)
"Return a \"canonical\" representation of the triangle."
(sort triangle #'symbol<))
(defun on-line-p (point line)
"True if point is on line."
(member point line :test #'eq))
(defun collinear-p (point1 point2 point3)
"True if all three points are on the same line."
(some (lambda (line)
(and (on-line-p point1 line)
(on-line-p point2 line)
(on-line-p point3 line)))
*lines*))
(defun find-endpoints (fixed-point)
"Find all the \"other\" endpoints of lines starting at fixed-point."
(loop for line in *lines*
when (on-line-p fixed-point line)
nconc (remove fixed-point line)))
(defun find-all-triangles (point)
"Find all triangles with point as one apex."
(loop with endpoints = (find-endpoints point)
for point2 in endpoints
for endpoints-2 = (find-endpoints point2)
nconc (loop for point3 in (intersection endpoints endpoints-2)
unless (collinear-p point point2 point3)
collect (canonicalize (list point point2 point3)))))
(defun find-triangles ()
"Return a list of all triangles based on *lines*."
(delete-duplicates (mapcan #'find-all-triangles *points*) :test #'equal))
;; Actually, due to the nature of the figure we only need to call
;; find-all-triangles on p0 and p1. This makes the solution more
;; efficient but less general.
(defun find-triangles-2 ()
"Return a list of all triangles based on *lines*."
(delete-duplicates (mapcan #'find-all-triangles '(p0 p1)) :test #'equal))