Linear Interpolation and sorted-map

utilities — cgrand, 8 June 2009 @ 19 h 07 min

Sorted collections (with subseq and rsubseq) can help when working with a partition of disjoint intervals, eg when you need to interpolate.

(defn interpolator 
 "Takes a coll of 2D points (vectors) and returns 
  their linear interpolation function."
 [points]
  (let [m (into (sorted-map) points)]
    (fn [x]
      (let [[[x1 y1]] (rsubseq m <= x)
            [[x2 y2]] (subseq m > x)]
        (if x2 
          (+ y1 (* (- x x1) (/ (- y2 y1) (- x2 x1))))
          y1)))))

;; => (map (interpolator [[0 0] [1 1] [3 2] [4 3]]) (range 0 9/2 1/2))
;; (0 1/2 1 5/4 3/2 7/4 2 5/2 3)

2 Comments »

  1. Nice.
    The function does something sensible for inputs that outside the range of points.
    (map (interpolator points) (range 0 19/2 1/2))
    ; (0 1/2 1 5/4 3/2 7/4 2 5/2 3 3 3 3 3 3 3 3 3 3 3)

    But only on one side
    (map (interpolator points) (range -1 19/2 1/2)) ; java.lang.NullPointerException

    Comment by John — 19 September 2009 @ 14 h 35 min
  2. @john, true, here is an amended version:
    (defn interpolator
     "Takes a coll of 2D points (vectors) and returns
      their linear interpolation function."
     [points]
      (let [m (into (sorted-map) points)]
        (fn [x]
          (let [[[x1 y1]] (rsubseq m <= x)
                [[x2 y2]] (subseq m > x)]
            (cond
              (not x2) y1
              (not x1) y2
              :else (+ y1 (* (- x x1) (/ (- y2 y1) (- x2 x1)))))))))

    ;; => (map (interpolator [[0 0] [1 1] [3 2] [4 3]]) (range -1 11/2 1/2))
    ;; (0 0 0 1/2 1 5/4 3/2 7/4 2 5/2 3 3 3)

    Comment by Christophe Grand — 20 September 2009 @ 11 h 48 min

RSS feed for comments on this post. TrackBack URI

Leave a comment

(c) 2018 Clojure and me | powered by WordPress with Barecity