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