;; The graph is represented as a list of lines
;; line = list of points
;; segment = two points on the same line
;; Each segment in graph Px <---> Py (in both directions) is stored in a hash table
;; Hash (Px) -> Hash (Py) -> line
(let (segment-hash)
(defun point->hash (point)
(or (gethash point segment-hash)
(setf (gethash point segment-hash) (make-hash-table))))
(defun init-hash (lines)
(setf segment-hash (make-hash-table))
(dolist (line lines)
(dolist (start-point line)
(dolist (end-point (remove start-point line))
(setf (gethash end-point (point->hash start-point)) line)))))
(defun all-points ()
(loop for point being each hash-key of segment-hash collect point))
(defun segment-p (p1 p2)
(gethash p2 (gethash p1 segment-hash))))
(defun point->adjust-points (point)
(loop for adjust-point being each hash-key of (point->hash point) collect adjust-point))
(defun line-p (p1 p2 p3)
(eq (segment-p p1 p2) (segment-p p2 p3)))
(defun triangle-p (p1 p2 p3)
(and (not (line-p p1 p2 p3))
(segment-p p1 p2) (segment-p p2 p3) (segment-p p3 p1)
(sort (list p1 p2 p3) #'(lambda (s1 s2) (string-lessp (symbol-name s1) (symbol-name s2))))))
(defun all-triangles (lines)
(init-hash lines)
(let (triangles)
(dolist (first-point (all-points))
(dolist (second-point (point->adjust-points first-point))
(dolist (third-point (point->adjust-points second-point))
(let ((triangle (triangle-p first-point second-point third-point)))
(when triangle
(pushnew triangle triangles :test #'equal))))))
triangles))
#+test
(defparameter *lines*
'((p0 p1)
(p0 p5 p8 p10)
(p0 p3 p7 p9)
(p0 p2 p4 p6)
(p1 p2 p3 p5)
(p1 p4 p7 p8)
(p1 p6 p9 p10)))
#+test (length (all-triangles *lines*))