# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1506123229 14400
# Node ID 4da3832f0f99fc56777ba4dd46a48c4df00b6957
# Parent  02ac02c3f88dc8c78f14c73d2ead67f5d3ad3811
Solve 102 with barycentric coordinates instead

diff -r 02ac02c3f88d -r 4da3832f0f99 src/problems.lisp
--- a/src/problems.lisp	Fri Sep 22 19:11:14 2017 -0400
+++ b/src/problems.lisp	Fri Sep 22 19:33:49 2017 -0400
@@ -1726,49 +1726,17 @@
              (iterate (for line :in-file file :using #'read-line)
                       (for (ax ay bx by cx cy) =
                            (mapcar #'parse-integer (cl-strings:split line #\,)))
-                      (collect (list (cons ax ay)
-                                     (cons bx by)
-                                     (cons cx cy)))))
-           (find-side-vertical (a b p)
-             "Return which side of the line AB point P falls on."
-             (destructuring-bind (ax . ay) a
-               (destructuring-bind (bx . by) b
-                 (if (= ax bx)
-                   (find-side-horizontal a b p)
-                   (destructuring-bind (px . py) p
-                     (let* ((slope (/ (- ay by)
-                                      (- ax bx)))
-                            (y-intercept (- ay (* slope ax)))
-                            (line-y (+ y-intercept (* slope px))))
-                       (cond
-                         ((> py line-y) :above)
-                         ((< py line-y) :below)
-                         ((= py line-y) :on))))))))
-           (find-side-horizontal (a b p)
-             "Return which side of the line AB point P falls on."
-             (destructuring-bind (ax . ay) a
-               (destructuring-bind (bx . by) b
-                 (if (= ay by)
-                   (find-side-vertical a b p)
-                   (destructuring-bind (px . py) p
-                     (let* ((slope (/ (- ax bx)
-                                      (- ay by)))
-                            (x-intercept (- ax (* slope ay)))
-                            (line-x (+ x-intercept (* slope py))))
-                       (cond
-                         ((> px line-x) :right)
-                         ((< px line-x) :left)
-                         ((= px line-x) :on))))))))
-           (check-line (a b c p)
-             (let ((result-triangle (find-side-vertical a b c))
-                   (result-point (find-side-vertical a b p)))
-               (or (eq result-point :on)
-                   (eq result-point result-triangle))))
+                      (collect (list (vec2 ax ay)
+                                     (vec2 bx by)
+                                     (vec2 cx cy)))))
            (check-triangle (a b c)
-             (let ((origin (cons 0 0)))
-               (and (check-line a b c origin)
-                    (check-line c a b origin)
-                    (check-line b c a origin)))))
+             ;; A point is within a triangle if its barycentric coordinates
+             ;; (with respect to that triangle) are all within 0 to 1.
+             (multiple-value-bind (u v w)
+                 (barycentric a b c (vec2 0 0))
+               (and (<= 0 u 1)
+                    (<= 0 v 1)
+                    (<= 0 w 1)))))
     (iterate (for (a b c) :in (parse-file "data/102-triangles.txt"))
              (counting (check-triangle a b c)))))
 
diff -r 02ac02c3f88d -r 4da3832f0f99 src/utils.lisp
--- a/src/utils.lisp	Fri Sep 22 19:11:14 2017 -0400
+++ b/src/utils.lisp	Fri Sep 22 19:33:49 2017 -0400
@@ -535,3 +535,50 @@
   (coerce (let ((div (expt 10 precision)))
             (/ (funcall rounder (* number div)) div))
           (type-of number)))
+
+
+(defun vec2 (x y)
+  (vector x y))
+
+(defun vx (vec2)
+  (aref vec2 0))
+
+(defun vy (vec2)
+  (aref vec2 1))
+
+(defun vec2+ (a b)
+  (vec2 (+ (vx a) (vx b))
+        (+ (vy a) (vy b))))
+
+(defun vec2- (a b)
+  (vec2 (- (vx a) (vx b))
+        (- (vy a) (vy b))))
+
+(defun vec2-dot (a b)
+  (+ (* (vx a) (vx b))
+     (* (vy a) (vy b))))
+
+
+(defun barycentric (a b c point)
+  "Return the barycentric coords of `point` with respect to the triangle `abc`.
+
+  `a`, `b`, `c`, and `point` must be `vec2`s.
+
+  The resulting `u`, `v`, and `w` barycentric coordinates will be returned as
+  three values.
+
+  "
+  ;; https://gamedev.stackexchange.com/a/23745
+  (let* ((v0 (vec2- b a))
+         (v1 (vec2- c a))
+         (v2 (vec2- point a))
+         (d00 (vec2-dot v0 v0))
+         (d01 (vec2-dot v0 v1))
+         (d11 (vec2-dot v1 v1))
+         (d20 (vec2-dot v2 v0))
+         (d21 (vec2-dot v2 v1))
+         (denom (- (* d00 d11) (* d01 d01)))
+         (v (/ (- (* d11 d20) (* d01 d21)) denom))
+         (w (/ (- (* d00 d21) (* d01 d20)) denom))
+         (u (- 1 v w)))
+    (values u v w)))