001  (ns walkmap.edge
002    "Essentially the specification for things we shall consider to be an edge.
003    An edge is a line segment having just a start and an end, with no intervening
004    nodes."
005    (:require [clojure.math.numeric-tower :as m]
006              [walkmap.vertex :refer [ensure2d ensure3d vertex vertex= vertex?]]))
007  
008  (defn edge
009    "Return an edge between vertices `v1` and `v2`."
010    [v1 v2]
011    (if
012      (and (vertex? v1) (vertex? v2))
013      {:kind :edge :walkmap.id/id (keyword (gensym "edge")) :start v1 :end v2}
014      (throw (IllegalArgumentException. "Must be vertices."))))
015  
016  (defn edge?
017    "True if `o` satisfies the conditions for a edge. An edge shall be a map
018    having the keys `:start` and `:end`, such that the values of each of those
019    keys shall be a vertex."
020    [o]
021    (and
022      (map? o)
023      (vertex? (:start o))
024      (vertex? (:end o))))
025  
026  (defn length
027    "Return the length of the edge `e`."
028    [e]
029    (let [start (ensure3d (:start e))
030          end (ensure3d (:end e))]
031      (m/sqrt
032        (reduce
033          +
034          (map
035            #(m/expt (- (% end) (% start)) 2)
036            [:x :y :z])))))
037  
038  (defn centre
039    "Return the vertex that represents the centre of this `edge`."
040    [edge]
041    (let [s (ensure3d (:start edge))
042          e (ensure3d (:end edge))]
043      (vertex
044        (+ (:x s) (/ (- (:x e) (:x s)) 2))
045        (+ (:y s) (/ (- (:y e) (:y s)) 2))
046        (+ (:z s) (/ (- (:z e) (:z s)) 2)))))
047  
048  (defn unit-vector
049    "Return an vertex parallel to `e` starting from the coordinate origin. Two
050    edges which are parallel will have the same unit vector."
051    [e]
052    (let [e' {:start (ensure3d (:start e)) :end (ensure3d (:end e))}
053          l (length e')]
054      (reduce
055        merge
056        {}
057        (map
058          (fn [k]
059            {k (/ (- (k (:end e')) (k (:start e'))) l)})
060          [:x :y :z]))))
061  
062  (defn parallel?
063    "True if all `edges` passed are parallel with one another."
064    [& edges]
065    (let [uvs (map unit-vector edges)]
066      (every?
067        #(vertex= % (first uvs))
068        (rest uvs))))
069  
070  (defn collinear?
071    "True if edges `e1` and `e2` are collinear with one another."
072    [e1 e2]
073    (parallel?
074      e1
075      e2
076      (if (vertex= (:start e1) (:start e2))
077        {:start (:start e1) :end (:end e2)}
078        {:start (:start e1) :end (:start e2)})))
079  
080  (defn collinear2d?
081    "True if the projections of edges `e1`, `e2` onto the x, y plane are
082    collinear."
083    [e1 e2]
084    (collinear? {:start (ensure2d (:start e1)) :end (ensure2d (:end e1))}
085                {:start (ensure2d (:start e2)) :end (ensure2d (:end e2))}))
086  
087  (defn minimaxd
088    "Apply function `f` to `coord` of the vertices at start and end of `edge`
089    and return the result. Intended use case is `f` = `min` or `max`, `coord`
090    is `:x`, `:y` or `:z`. No checks are made for sane arguments."
091    [edge coord f]
092    (apply f (list (coord (:start edge)) (coord (:end edge)))))
093  
094  (defn on?
095    "True if the vertex `v` is on the edge `e`."
096    [e v]
097    (let [p (ensure3d (:start e))
098          q (ensure3d v)
099          r (ensure3d (:end e))]
100      (and
101        (collinear? (edge p q) (edge q r))
102        (<= (:x q) (max (:x p) (:x r)))
103        (>= (:x q) (min (:x p) (:x r)))
104        (<= (:y q) (max (:y p) (:y r)))
105        (>= (:y q) (min (:y p) (:y r)))
106        (<= (:z q) (max (:z p) (:z r)))
107        (>= (:z q) (min (:z p) (:z r))))))
108  
109  (defn on2d?
110    "True if vertex `v` is on edge `e` when projected onto the x, y plane."
111    [e v]
112    (on? (edge (ensure2d (:start e)) (ensure2d (:end e))) v))
113  
114  (defn overlaps2d?
115    "True if the recangle in the x,y plane bisected by edge `e1` overlaps that
116    bisected by edge `e2`. It is an error if either `e1` or `e2` is not an edge."
117    [e1 e2]
118    (when (and (edge? e1) (edge? e2))
119      (and
120        (> (minimaxd e1 :x max) (minimaxd e2 :x min))
121        (< (minimaxd e1 :x min) (minimaxd e2 :x max))
122        (> (minimaxd e1 :y max) (minimaxd e2 :y min))
123        (< (minimaxd e1 :y min) (minimaxd e2 :y max)))))
124  
125  (defn intersection2d
126    "The probability of two lines intersecting in 3d space is low, and actually
127    that is mostly not something we're interested in. We're interested in
128    intersection in the `x,y` plane. This function returns a vertex representing
129    a point vertically over the intersection of edges `e1`, `e2` in the `x,y`
130    plane, whose `z` coordinate is
131  
132    * 0 if both edges are 2d (i.e. have missing or zero `z` coordinates);
133    * if one edge is 2d, then the point on the other edge over the intersection;
134    * otherwise, the average of the z coordinates of the points on the two
135    edges over the intersection.
136  
137    If no such intersection exists, `nil` is returned.
138  
139    It is an error, and an exception will be thrown, if either `e1` or `e2` is
140    not an edge."
141    [e1 e2]
142    (if (and (edge? e1) (edge? e2))
143      (when
144        (overlaps2d? e1 e2) ;; relatively cheap check
145        (if
146          (collinear2d? e1 e2)
147          ;; any point within the overlap will do, but we'll pick the end of e1
148          ;; which is on e2
149          (if (on2d? e2 (:start e1)) (:start e1) (:end e1))
150          ;; blatantly stolen from
151          ;; https://gist.github.com/cassiel/3e725b49670356a9b936
152          (let [x1 (:x (:start e1))
153                x2 (:x (:end e1))
154                x3 (:x (:start e2))
155                x4 (:x (:end e2))
156                y1 (:y (:start e1))
157                y2 (:y (:end e1))
158                y3 (:y (:start e2))
159                y4 (:y (:end e2))
160                denom (- (* (- x1 x2) (- y3 y4))
161                         (* (- y1 y2) (- x3 x4)))
162                x1y2-y1x2 (- (* x1 y2) (* y1 x2))
163                x3y4-y3x4 (- (* x3 y4) (* y3 x4))
164                px-num (- (* x1y2-y1x2 (- x3 x4))
165                          (* (- x1 x2) x3y4-y3x4))
166                py-num (- (* x1y2-y1x2 (- y3 y4))
167                          (* (- y1 y2) x3y4-y3x4))
168                result (when-not (zero? denom)
169                         (vertex (/ px-num denom) (/ py-num denom)))]
170            (when (and result (on2d? e1 result) (on2d? e2 result)) result))))
171      (throw (IllegalArgumentException.
172               (str
173                 "Both `e1` and `e2` must be edges."
174                 (map #(or (:kind %) (type %)) [e1 e2]))))))
175