exupero's blog

# Recursive subdivision

In the previous post we subdivided all of a shape's edges, then subdivided them again, going around and around as many times as necessary to get the desired level of detail. But just because there are still long edges that need to be subdivided doesn't mean we have to subdivide edges that are already short enough. I'd like to take an alternate approach to subdivision. Rather than going round and round, we'll recursively subdivide each edge until all the sub-segments are small enough.

Below is a version of `subdivide-with` that's more complicated. It now contains the recursion formerly applied via `iterate-n-times`. While the threaded body at the end remains similar, `mapcat` receives a recursive function that wraps the user-supplied function and terminates the subdivision process if `f` doesn't return anything:

``````(defn subdivide-with [f coll max-depth]
(letfn [(subdivider [[a b] max-depth]
(if (pos? max-depth)
(if-let [mid (f a b)]
(concat (subdivider [a mid] (dec max-depth))
(subdivider [mid b] (dec max-depth)))
[a])
[a]))]
(-> coll
(->> (partition 2 1))
(->> (mapcat #(subdivider % max-depth)))
(concat [(last coll)]))))``````

If the subdividing function never returns `nil`, `max-depth` prevents infinite recursion.

Since `subdivide-with` is a generic function, we can test it by subdividing an interval:

``````(subdivide-with
(fn [a b]
(when (< 1/2 (Math/abs (float (- a b))))
(/ (+ a b) 2)))
[0 4]
5)``````
``````(0 1/2 1 3/2 2 5/2 3 7/2 4)
``````

Just what we should expect.

Note that `doall` has disappeared from `subdivide-with`. We used it in the original `subdivide-with` to avoid Clojure's lazy sequence evaluation from changing the order of random number usage, but because we're recursing we've already changed how we use the sequence of random numbers from `java.util.Random`, so we can omit `doall`. In practice, this means subdividing twice will give us a very different island than subdividing once, and overlaying the outlines generated by fewer subdivisions is no longer meaningful.

Let's subdivide the edges of a polygon, and stop when the distance between the points is smaller than 0.005:

``````(defn sqr [x]
(* x x))``````
``````(defn dist [[x1 y1] [x2 y2]]
(Math/sqrt (+ (sqr (- x1 x2))
(sqr (- y1 y2)))))``````
``````(let [rng (java.util.Random. 1)
sides (.nextInt rng 3 9)]
(-> sides
(->>
regular-ngon
(irregularize rng 0.35)
(map (partial apply cartesian))
loop-around