QuadTree

Golang implementation of the quadtree algorithm. Includes removal, update and knearest search.

Godoc

Usage Example

Create a quadtree fitting the world geographic bounds (from [-90,-180] to [90,180])

centerPoint := quadtree.NewPoint(0.0, 0.0, nil)
halfPoint := quadtree.NewPoint(90.0, 180.0, nil)
boundingBox := quadtree.NewAABB(centerPoint, halfPoint)

qtree := quadtree.New(boundingBox, 0, nil)

Insert a point into the tree

point := quadtree.NewPoint(52.5200, 13.4050, "Berlin")
if !qtree.Insert(point) {
  log.Fatal("Failed to insert the point")
}

Find the k-nearest points (results are sorted by distance to the query center, and duplicates are removed):

center := quadtree.NewPoint(lat, lng, nil)
distance := 10000 /* Distance to the center point in meters */
bounds := quadtree.NewAABB(center, center.HalfPoint(distance))

maxPoints := 10
for _, point := range qtree.KNearest(bounds, maxPoints, nil) {
  log.Printf("Found point: %s\n", point.Data().(string))
}

HTTP Handler

Embed the quadtree HTTP API in your application:

import "github.com/asim/quadtree"

// Create quadtree and store
tree := quadtree.New(bounds, 0, nil)
store, _ := quadtree.NewFileStore("data.json")

// Create HTTP handler
handler := quadtree.NewHTTPHandler(tree, store)

// Mount at /api prefix
http.Handle("/api/", http.StripPrefix("/api", handler))

Endpoints:

• GET /points - List all points
• POST /points - Add a point {"x": 51.5, "y": -0.1, "data": "London"}
• GET /points/{id} - Get a point
• DELETE /points/{id} - Delete a point
• POST /search - Search region {"center": [51.5, -0.1], "radius": 10}

Standalone Server

A standalone HTTP server with REST API and interactive UI is available for managing and visualizing points.

cd cmd/server
go run main.go

Visit http://localhost:8080 in your browser for an interactive grid visualization with:

• REST API endpoints for CRUD operations
• Visual point management with mouse/keyboard navigation
• Regional search functionality
• Real-time updates
• Responsive mobile-first design

See cmd/server/README.md for full API documentation and usage.

Reusable UI Package

The visualization UI is available as a subpackage for embedding in other applications:

import "github.com/asim/quadtree/ui"

// Default config for point editor with full controls
http.Handle("/", ui.Handler(ui.DefaultConfig()))

// Read-only network view (e.g., for agent visualization)
http.Handle("/network", ui.Handler(ui.NetworkConfig()))

// Custom configuration
cfg := ui.Config{
    Title:          "My Spatial View",
    APIBase:        "/api",
    PointsEndpoint: "/items",
    SearchEndpoint: "/search",
    ShowAddPoint:   false,
    ShowDelete:     false,
    ReadOnly:       true,
    PointLabel:     "Item",
    AutoRefresh:    true,
    RefreshInterval: 5000, // milliseconds
}
http.Handle("/view", ui.Handler(cfg))

// Serve static assets (CSS, JS)
http.Handle("/quadtree.css", http.FileServer(http.FS(ui.FS())))
http.Handle("/quadtree.js", http.FileServer(http.FS(ui.FS())))

Expected API Format

The UI expects your API endpoints to return points in this format:

[
  {"id": "1", "x": 51.5, "y": -0.1, "name": "London", "data": {"type": "city"}},
  {"id": "2", "x": 48.8, "y": 2.3, "name": "Paris", "data": {"type": "city"}}
]

• id - unique identifier
• x, y - coordinates (lat/lon for geo data)
• name - display label (falls back to data if not present)
• data - optional metadata object

The UI supports:

• Pan/zoom with mouse, touch, and keyboard
• Grid overlay with dynamic scaling
• Point display with labels
• Auto-refresh for live data
• Mobile-responsive design
• Configurable controls and labels

Examples

For complete, runnable examples, see the examples directory:

• simple.go - A minimal example demonstrating basic quadtree operations (insert, search, k-nearest)
• basic.go - A comprehensive example with real-world city coordinates, filtering, updates, and removals

Run any example with:

cd examples
go run simple.go

Notes

• KNearest returns up to k points, sorted by Euclidean distance to the query center.
• Duplicate points are removed from the result.
• The distance metric is Euclidean (straight-line). For geospatial data, you may want to adapt this to use Haversine or another metric if needed.