Mapping Ham Radio Contacts to the Stars

Picture this: you’re tracking hundreds of amateur radio contacts across the night sky, overlaying each QSO position onto constellation charts. A contact in Orion, another near Polaris, dozens scattered across Cygnus. The naive approach—checking every stored contact against every star region—quickly becomes unwieldy as your logbook grows.

Enter the quadtree, a spatial indexing technique that recursively divides two-dimensional space into four quadrants. When a quadrant holds too many points, it splits again. The result? Lightning-fast spatial queries that let you instantly find all radio contacts within any constellation boundary.

type bounds = { min_lat: float; max_lat: float; min_lon: float; max_lon: float }
type contact = float * float * string

type quadtree = 
  | Leaf of contact list
  | Node of quadtree * quadtree * quadtree * quadtree

let child_bounds b =
  let mid_lat = (b.min_lat +. b.max_lat) /. 2.0 in
  let mid_lon = (b.min_lon +. b.max_lon) /. 2.0 in
  ({ b with min_lat = mid_lat; max_lon = mid_lon },
   { b with min_lat = mid_lat; min_lon = mid_lon },
   { b with max_lat = mid_lat; max_lon = mid_lon },
   { b with max_lat = mid_lat; min_lon = mid_lon })

let rec insert ((lat, lon, _) as contact) bounds = function
  | Leaf contacts when List.length contacts < 4 -> 
      Leaf (contact :: contacts)
  | Leaf contacts -> 
      let nw, ne, sw, se = subdivide bounds contacts in
      insert contact bounds (Node (nw, ne, sw, se))
  | Node (nw, ne, sw, se) -> 
      insert_into_quadrant contact bounds (nw, ne, sw, se)

and subdivide bounds contacts =
  List.fold_left
    (fun trees contact -> match insert_into_quadrant contact bounds trees with
       | Node (nw, ne, sw, se) -> (nw, ne, sw, se)
       | Leaf _ -> trees)
    (Leaf [], Leaf [], Leaf [], Leaf []) contacts

and insert_into_quadrant ((lat, lon, _) as contact) bounds (nw, ne, sw, se) =
  let mid_lat = (bounds.min_lat +. bounds.max_lat) /. 2.0 in
  let mid_lon = (bounds.min_lon +. bounds.max_lon) /. 2.0 in
  let nw_b, ne_b, sw_b, se_b = child_bounds bounds in
  if lat >= mid_lat && lon < mid_lon then Node (insert contact nw_b nw, ne, sw, se)
  else if lat >= mid_lat then Node (nw, insert contact ne_b ne, sw, se)
  else if lon < mid_lon then Node (nw, ne, insert contact sw_b sw, se)
  else Node (nw, ne, sw, insert contact se_b se)

OCaml’s pattern matching makes the recursive structure elegant—each node either holds contacts directly (Leaf) or delegates to four child quadrants (Node). The functional approach treats the tree as immutable, rebuilding paths as needed.

data class QSO(val lat: Double, val lon: Double, val callsign: String)
data class Rectangle(val minLat: Double, val maxLat: Double, val minLon: Double, val maxLon: Double) {
    fun contains(lat: Double, lon: Double) = lat in minLat..maxLat && lon in minLon..maxLon
    fun subdivide(): List<Rectangle> {
        val midLat = (minLat + maxLat) / 2.0
        val midLon = (minLon + maxLon) / 2.0
        return listOf(
            Rectangle(midLat, maxLat, minLon, midLon),
            Rectangle(midLat, maxLat, midLon, maxLon),
            Rectangle(minLat, midLat, minLon, midLon),
            Rectangle(minLat, midLat, midLon, maxLon),
        )
    }
}

class QuadTree(private val bounds: Rectangle, private val capacity: Int = 4) {
    private val contacts = mutableListOf<QSO>()
    private var children: Array<QuadTree>? = null
    
    fun insert(qso: QSO): Boolean {
        if (!bounds.contains(qso.lat, qso.lon)) return false
        children?.let { return it.any { child -> child.insert(qso) } }
        
        if (contacts.size < capacity) {
            contacts.add(qso)
            return true
        }

        subdivide()
        val existing = contacts.toList()
        contacts.clear()
        existing.forEach { old -> children?.any { child -> child.insert(old) } }
        return children?.any { child -> child.insert(qso) } ?: false
    }

    private fun subdivide() {
        if (children == null) {
            children = bounds.subdivide().map { QuadTree(it, capacity) }.toTypedArray()
        }
    }
}

Kotlin takes the mutable, object-oriented route—each QuadTree node manages its own state and children. Both approaches achieve O(log n) insertion and spatial queries, transforming your constellation overlay from a computational slog into smooth, real-time navigation across the star-studded frequencies.