;; 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*))