README
¶
QuadTree
A fast, production-ready spatial index for Go. Insert, remove, update, and search millions of points with k-nearest neighbor queries.
Used for location-based services, game development, spatial analytics, and anywhere you need efficient 2D point lookups.
Features
- Fast spatial queries - K-nearest neighbor search with distance sorting
- Full CRUD - Insert, update, remove, and query points
- Persistence - Built-in file storage with JSON or custom backends
- HTTP API - Ready-to-use REST endpoints for your application
- Interactive UI - Embeddable visualization for debugging and management
- Zero dependencies - Pure Go, no external libraries
- Battle-tested - Used in production for location services
Install
go get github.com/asim/quadtree
Quick Start
package main
import (
"fmt"
"github.com/asim/quadtree"
)
func main() {
// Create a quadtree covering the world
center := quadtree.NewPoint(0, 0, nil)
half := quadtree.NewPoint(90, 180, nil)
bounds := quadtree.NewAABB(center, half)
tree := quadtree.New(bounds, 0, nil)
// Insert some cities
tree.Insert(quadtree.NewPoint(51.5074, -0.1278, "London"))
tree.Insert(quadtree.NewPoint(48.8566, 2.3522, "Paris"))
tree.Insert(quadtree.NewPoint(52.5200, 13.4050, "Berlin"))
// Find 2 nearest cities to a point
query := quadtree.NewPoint(50.0, 5.0, nil)
searchBounds := quadtree.NewAABB(query, query.HalfPoint(500000))
for _, p := range tree.KNearest(searchBounds, 2, nil) {
fmt.Printf("Found: %s\n", p.Data().(string))
}
}
HTTP API
Embed a REST API in your application:
import "github.com/asim/quadtree"
// Create tree with persistent storage
tree := quadtree.New(bounds, 0, nil)
store, _ := quadtree.NewFileStore("points.json")
handler := quadtree.NewHTTPHandler(tree, store)
http.Handle("/api/", http.StripPrefix("/api", handler))
http.ListenAndServe(":8080", nil)
Endpoints:
| Method | Path | Description |
|---|---|---|
| GET | /points | List all points |
| POST | /points | Add a point |
| GET | /points/{id} | Get a point |
| DELETE | /points/{id} | Delete a point |
| POST | /search | Search within radius |
Interactive UI
A built-in visualization UI for debugging and point management:
import "github.com/asim/quadtree/ui"
// Add UI to your server
http.Handle("/", ui.Handler(ui.DefaultConfig()))
Features:
- Pan/zoom with mouse, touch, keyboard
- Real-time point visualization
- CRUD operations via UI
- Mobile-responsive
- Customizable appearance
Standalone Server
Run the included server for quick testing:
cd cmd/server
go run main.go
# Visit http://localhost:8080
Use Cases
- Location services - Find nearby restaurants, stores, users
- Game development - Spatial collision detection, entity lookup
- Mapping - Efficient point-of-interest queries
- Analytics - Geospatial data clustering and search
- IoT - Device location tracking and proximity alerts
Performance
Quadtree provides O(log n) average case for insertions and queries, making it suitable for datasets from thousands to millions of points.
Examples
See the examples directory for complete, runnable code:
cd examples
go run simple.go # Basic operations
go run basic.go # Real-world cities demo
Enterprise Support
Using QuadTree in production? Need custom features, priority support, or consulting?
Create an issue or contact for enterprise inquiries.
License
Built by Asim Aslam • Part of Mu.XYZ
Documentation
¶
Index ¶
- Variables
- type AABB
- type FileStore
- type HTTPHandler
- type MemoryStore
- type Point
- type PointRequest
- type PointResponse
- type QuadTree
- func (qt *QuadTree) Count() int
- func (qt *QuadTree) DebugFind(x, y float64) bool
- func (qt *QuadTree) Insert(p *Point) bool
- func (qt *QuadTree) KNearest(a *AABB, i int, fn filter) []*Point
- func (qt *QuadTree) RInsert(p *Point) bool
- func (qt *QuadTree) Remove(p *Point) bool
- func (qt *QuadTree) Search(a *AABB) []*Point
- func (qt *QuadTree) Update(p *Point, np *Point) bool
- type SearchRequest
- type Store
- type StoredPoint
Constants ¶
This section is empty.
Variables ¶
var ( Capacity = 8 MaxDepth = 6 )
Functions ¶
This section is empty.
Types ¶
type AABB ¶
type AABB struct {
// contains filtered or unexported fields
}
func (*AABB) ContainsPoint ¶
ContainsPoint checks whether the point provided resides within the axis aligned bounding box.
type FileStore ¶ added in v0.3.0
type FileStore struct {
// contains filtered or unexported fields
}
FileStore persists points to a JSON file with batched async writes
func NewFileStore ¶ added in v0.3.0
NewFileStore creates a new file-based store with batched writes
func (*FileStore) Close ¶ added in v0.3.0
Close saves any pending changes and stops background saver
type HTTPHandler ¶ added in v0.3.0
type HTTPHandler struct {
// contains filtered or unexported fields
}
HTTPHandler provides HTTP API for a quadtree with persistence
func NewHTTPHandler ¶ added in v0.3.0
func NewHTTPHandler(tree *QuadTree, store Store) *HTTPHandler
NewHTTPHandler creates an HTTP handler for the given quadtree and store
func (*HTTPHandler) Points ¶ added in v0.3.0
func (h *HTTPHandler) Points() map[string]*Point
Points returns all points (for external iteration)
func (*HTTPHandler) ServeHTTP ¶ added in v0.3.0
func (h *HTTPHandler) ServeHTTP(w http.ResponseWriter, r *http.Request)
ServeHTTP handles /points and /points/{id} and /search
type MemoryStore ¶ added in v0.3.0
type MemoryStore struct {
// contains filtered or unexported fields
}
MemoryStore is an in-memory implementation of Store
func NewMemoryStore ¶ added in v0.3.0
func NewMemoryStore() *MemoryStore
NewMemoryStore creates a new in-memory store
func (*MemoryStore) Close ¶ added in v0.3.0
func (s *MemoryStore) Close() error
Close is a no-op for memory store
func (*MemoryStore) Delete ¶ added in v0.3.0
func (s *MemoryStore) Delete(id string) error
Delete removes a point from memory
func (*MemoryStore) List ¶ added in v0.3.0
func (s *MemoryStore) List() (map[string]*Point, error)
List returns all points from memory
type Point ¶
type Point struct {
// contains filtered or unexported fields
}
func (*Point) Coordinates ¶
Coordinates return the x and y coordinates of a point.
type PointRequest ¶ added in v0.3.0
type PointRequest struct {
X float64 `json:"x"`
Y float64 `json:"y"`
Data interface{} `json:"data"`
}
PointRequest is the JSON request format for adding/updating points
type PointResponse ¶ added in v0.3.0
type PointResponse struct {
ID string `json:"id"`
X float64 `json:"x"`
Y float64 `json:"y"`
Data interface{} `json:"data"`
}
PointResponse is the JSON response format for points
type QuadTree ¶
type QuadTree struct {
// contains filtered or unexported fields
}
func New ¶
New creates a new *QuadTree. It requires a boundary defining the center and half points, depth at which the QuadTree resides and parent node. Depth of 0 and parent as nil implies the root node.
func (*QuadTree) DebugFind ¶ added in v0.3.0
DebugFind searches for a point by coordinates and returns if found
func (*QuadTree) Insert ¶
Insert will attempt to insert the point into the QuadTree. It will recursively search until it finds the leaf node. If the leaf node is at capacity then it will try split the node. If the tree is at max depth then point will be stored in the leaf.
func (*QuadTree) Remove ¶
Remove attemps to remove a point from the QuadTree. It will recurse until the leaf node is found and then try to remove the point.
type SearchRequest ¶ added in v0.3.0
SearchRequest is the JSON request format for search
type Store ¶ added in v0.3.0
type Store interface {
// Save stores a point with the given ID
Save(id string, point *Point) error
// Load retrieves a point by ID
Load(id string) (*Point, error)
// Delete removes a point by ID
Delete(id string) error
// List returns all points in the store
List() (map[string]*Point, error)
// Close closes the store and performs cleanup
Close() error
}
Store defines the interface for persisting quadtree points
type StoredPoint ¶ added in v0.3.0
type StoredPoint struct {
ID string `json:"id"`
X float64 `json:"x"`
Y float64 `json:"y"`
Data interface{} `json:"data"`
}
StoredPoint represents a point that can be serialized
Source Files
Directories