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
      (map #(add-roughness rng %)))
    (as-> verts
      (subdivide-with
        (fn [a b]
          (when (< 0.005 (dist (a :vertex) (b :vertex)))
            (offset-roughened-midpoint rng a b)))
        verts
        11))
    (->> (map :vertex))))