Drawing recursive line intersections

Draft of 2019.01.06

May include: gamesgeometryclojure&c.

It wouldn’t be fair for me to pose questions and exercises for which I wasn’t able to at least make an attempt myself. So since asking about the way the recursively-defined intersection points of lines and circles drawn through intersection points of earlier lines and circles, of course I had to give it a try.

I tend to think about these things visually, and I have been writing Clojure and ClojureScript mostly for the last few years. So I worked out a simple quil sketch to get started.

Note that this sketch doesn’t do what I asked—not at all. What’s happening is much simpler; a smaller “bite” if you like of the bigger problem I proposed. I’ve dropped 13 points onto the plane, randomly positioned in the box you’ll see below. Then I’ve drawn all the lines—and just the lines—that are defined by those 13 points (one through each distinct pair of points). Then I’ve found all the intersections of those lines, and labeled those points with little red dots.

I don’t recurse, and I don’t draw circles yet. I wanted to assure myself that I still remembered some quil idioms.

Also, because one can never be too certain about these things, I’ve animated the positions of the thirteen original points, by wiggling them around randomly a bit. Mainly I was worried about the prospect of coincident points (as I mentioned in the bigger proposal), so I wanted to wiggle the “seed” to make sure the derived intersection points wiggle appropriately in response. I might also have been imagining a predicate function for determining whether two apparently-coincident points of intersection are in fact “the same”, which involves wiggling the kinematic mechanism to which they’re attached and seeing if they stray from one another. Somehow that seems to capture the geometry “more easily” (for me), than reducing the points to symbolic algebraic standard forms and looking at those.

A few things I’ve been reminded of already:

  • ClojureScript only gives me double-precision math, which may be problematic for bigger diagrams. That might push me towards an algebraic approach.
  • When the two points though which a line passes are close, wiggling those points has a larger effect on the line’s slope than if they’re far apart. Obvious, in hindsight, but hey there it is in animated reminder form.
  • I’ve ignored lines with infinite slope here, and there are certainly bugs in those edge cases.
  • I’ve done some kludgey stuff drawing the lines so they fill the sketch area, and also to smooth the images, because of being in a hurry. I’ll probably regret that.
  • I’m being dreadfully inefficient when drawing these lines (which are stored in point-point form); I should cache their point-slope form as well.
  • The number of intersections increases very quickly with the number of lines. I mean, you and I both knew that, but again it’s good to be reminded with a picture.
  • It’s not actually obvious how to export a quil sketch for use in an external page. I should probably write that down for myself.


(ns intersection-points.core
  (:require [quil.core :as q :include-macros true]
            [quil.middleware :as m]
            [clojure.math.combinatorics :as combo]))

(defrecord Point [x y])

(defrecord Line [p1 p2])

(defn drawpoint [pt]
  (if (< (:y pt) js/Infinity)
    (q/ellipse (:x pt) (:y pt) 7 7))

(defn drawsquare [pt]
  (q/rect (:x pt) (:y pt) 10 10)

(defn slope [line]
  (let [x1 (:x (:p1 line))
        y1 (:y (:p1 line))
        x2 (:x (:p2 line))
        y2 (:y (:p2 line))]
    (if (= x1 x2)
      (/ (- y2 y1) (- x2 x1))

(defn intercept [line]
  (let [x1 (:x (:p1 line))
        y1 (:y (:p1 line))
        x2 (:x (:p2 line))]
    (if (= x1 x2)
      (- y1 (* x1 (slope line)))

(defn slope-intercept-fxn [line]
  (fn [x] (+ (intercept line) (* x (slope line))))

(defn draw-line
  ([line] (draw-line line 1.0))
  ([line scale]
    (let [si    (slope-intercept-fxn line)
          w     (q/width)
          left  (- (/ w scale))
          right (/ w scale)
          x1    (:x (:p1 line))
          x2    (:x (:p2 line))]
      (if (= x1 x2)
        (q/line x1 left x1 right)
        (q/line left (si left) right (si right))

(defn line-intersection [line1 line2]
  (let [s1 (slope line1)
        s2 (slope line2)
        i1 (intercept line1)
        i2 (intercept line2)
        f  (/ (- i2 i1) (- s1 s2))]
    (if (= s1 s2)
      (Point. js/Infinity js/Infinity)
      (Point. f (+ (* s1 f) i1))

(defn nudge [v]
  (+ v (/ (+ (rand-int 3) -1.0) 2.0))

(defn wiggle-point [point w h]
  (Point. (nudge (:x point)) (nudge (:y point))

(defn rand-point [width height]
  (Point. (- (rand-int width) (/ width 2))
          (- (rand-int height) (/ height 2))

(defn rand-line [width height]
  (Line. (rand-point width height)
         (rand-point width height)

(defn avg [numbers]
  (/ (reduce + numbers) (count numbers))

(defn center-of-mass [pts]
  (let [xs (map :x pts)
        ys (map :y pts)]
    (Point. (avg xs) (avg ys))

(defn setup []
  (q/frame-rate 30)
  (q/color-mode :hsb)
  (q/background 255)
  (let [w (q/width)
        h (q/height)
        pts (repeatedly 13 #(rand-point w h))]
  { :color 255
    :points pts
    :lines (map (fn [[p1 p2]] (Line. p1 p2)) (combo/combinations pts 2))

(defn update-state [state]
  (let [pts (map #(wiggle-point % (q/width) (q/height)) (:points state))]
    { :color 255 ;; (mod (inc (:color state)) 255)
      :points pts
      :lines (map (fn [[p1 p2]] (Line. p1 p2)) (combo/combinations pts 2))}

(defn draw-state [state]
  (q/background 255)
  (q/stroke 80 50)
  (q/translate 250 250)
  (q/scale 0.3)

  ;; draw the lines
  (q/smooth 4)
  (doseq [thisLine (:lines state)] (draw-line thisLine 0.3))

  ;; draw the intersections of those lines
  (q/fill (:color state) 255 255 200)
    [crossing (combo/combinations (:lines state) 2)]
    (drawpoint (apply line-intersection crossing))

  ; (q/fill (:color state) 255 255 10)
  ; (doseq
  ;   [pt (:points state)]
  ;   (drawpoint pt))

  ; (drawsquare (center-of-mass (:points state)))

; this function is called in index.html
(defn ^:export run-sketch []
  (q/defsketch intersection-points
    :host "intersection-points-1"
    :size [500 500]
    ; setup function called only once, during sketch initialization.
    :setup setup
    ; update-state is called on each iteration before draw-state.
    :update update-state
    :draw draw-state
    ; This sketch uses functional-mode middleware.
    ; Check quil wiki for more info about middlewares and particularly
    ; fun-mode.
    :middleware [m/fun-mode]))

; uncomment this line to reset the sketch: