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