• Stars
    star
    164
  • Rank 230,032 (Top 5 %)
  • Language
    Go
  • License
    Other
  • Created over 8 years ago
  • Updated almost 5 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

🍀 A Quadtree implemented in Go

🍀 Quadtree (Go)

godoc reference

A quadtree implementation in Go, featuring insertion and retrieval of bounding boxes and points.

What is it?

"A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974." - Wikipedia (2016)



Setup

Usage

    qt := &quadtree.Quadtree{
		Bounds: quadtree.Bounds{
			X:      0,
			Y:      0,
			Width:  100,
			Height: 100,
		},
		MaxObjects: 10,
		MaxLevels:  4,
		Level:      0,
		Objects:    make([]quadtree.Bounds, 0),
		Nodes:      make([]quadtree.Quadtree, 0),
	}

    // Insert some boxes
    qt.Insert(Bounds{
		X:      1,
		Y:      1,
		Width:  10,
		Height: 10,
	})
	qt.Insert(Bounds{
		X:      5,
		Y:      5,
		Width:  10,
		Height: 10,
	})
	qt.Insert(Bounds{
		X:      10,
		Y:      10,
		Width:  10,
		Height: 10,
	})
	qt.Insert(Bounds{
		X:      15,
		Y:      15,
		Width:  10,
		Height: 10,
	})

	//Get all the intersections
	intersections := qt.RetrieveIntersections(Bounds{
		X:      5,
		Y:      5,
		Width:  2.5,
		Height: 2.5,
	})

	// Clear the Quadtree
	qt.Clear()

Acknowledgements

This package is based on Timo Hausmann JavaScript Quadtree implementation. This is in turn based on this post.

License

MIT

Original JavaScript code: Copyright © 2012 Timo Hausmann

Go code: Copyright © 2016 James Milner

More Repositories

1

terra-draw

A library for drawing on maps that supports Mapbox, MapLibre, Google Maps, OpenLayers and Leaflet out the box
TypeScript
476
star
2

cheap-ruler-go

📏 cheapruler in Go: fast geodesic measurements
Go
206
star
3

THREEAR

A marker based Augmented Reality library for Three.js
TypeScript
172
star
4

pip-go

🎯 Point in Polygon implemented in Go
Go
79
star
5

tabsync

A demonstration of sync state across tabs using Service Workers
JavaScript
37
star
6

fibrelite

🎽 keeping the mainthread free with inline Web Workers
JavaScript
37
star
7

lee-algorithm-js

A version of the Lee Algorithm implemented in JavaScript
JavaScript
26
star
8

web-mapping-libraries

A comparison of adding basic map to a page in a variety of different web mapping libraries
HTML
26
star
9

github-map

A map showing the estimates of GitHub users in cities worldwide
JavaScript
26
star
10

wasm-workers

e
JavaScript
22
star
11

worker-assemblyscript-template

A Cloudflare wrangler template for a AssemblyScript worker
WebAssembly
21
star
12

webpack-tsc-worker

An example of using Workers built with TypeScript and Webpack
TypeScript
20
star
13

threejs-fps-controls

Basic First Person controls for Three.js scenes
JavaScript
14
star
14

Loxo

A queryable GeoJSON API using MongoDB & Flask
Python
12
star
15

abortable-fetch-example

Example of abortable fetch
HTML
10
star
16

pixelmatch-asc

pixelmatch reimplemented in AssemblyScript
WebAssembly
10
star
17

globe-gaze

A 3D globe controlled using your eyes
JavaScript
8
star
18

terra-draw-website

The official Terra Draw website
TypeScript
7
star
19

web-worker-comparison

Comparing plain Web Workers and various associated libraries
JavaScript
6
star
20

scratchtheworld

Scratch off countries you've been to around the world. Built with Leaflet and Polymer
JavaScript
5
star
21

github-mapping

An example of how to scrape and map GitHub data
Python
5
star
22

terra-draw-route-snap-mode

An experimental route snapping mode for Terra Draw
TypeScript
5
star
23

chronolite

🕰️ A microlibrary for timing, comparing and benchmarking JavaScript functions
JavaScript
4
star
24

webworker-perf

A benchmarking of Web Workers to measure performance
JavaScript
4
star
25

hello-live-reload

A very simple example of how to use gulp-livereload
JavaScript
3
star
26

gamepad-maps

Maps that can use gamepads for navigation
JavaScript
2
star
27

Lacuna

A 3D GIS using PostGIS and Three.js
JavaScript
2
star
28

esri-twitter

Using the Twitter API in conjunction with the ArcGIS JavaScript API
PHP
2
star
29

esri-dojo

An example of using the ArcGIS JavaScript API with Dojo 3+
TypeScript
2
star
30

tracked-json

JavaScript library for frictionless undo/redo for JSON objects
TypeScript
2
star
31

serviceworker-statemanagement

Putting Redux state management in a Service Worker
JavaScript
2
star
32

esri-what3words

A example demonstrating how the ArcGIS JavaScript API Search Widget can be intergrated with the what3words geocoder
JavaScript
2
star
33

pg-api-go

A HTTP API wrapper for PostgreSQL
Go
1
star
34

dojo-calc

A calculator written in Dojo 2
TypeScript
1
star
35

ArcGISHelloWorld

HTML
1
star
36

globe-plotter

A web app for creating global wireframe visualisations
Go
1
star
37

webcam-gesture-map

A map that has a (basic!) ability to respond to hand gestures in front of a webcam
JavaScript
1
star
38

cf-worker-pixelmatch

TypeScript
1
star
39

together

An experimental data binding library for JavaScript
JavaScript
1
star
40

facebook-pop-viz

Visualising facebook's population density GeoTIFFs
Python
1
star
41

esri-borisbikes

A boris bike availability map for London. Uses ArcGIS JS API and D3.js
JavaScript
1
star
42

Starch

1
star
43

evernote2csv

A python tool for exporting out evernote HTML files to CSV files
Python
1
star
44

esri-soundcloud

An Esri and SoundCloud API intergration; SoundCloud Mapper. Here the user types in a genre of music and it will place the sound onto the presented map.
CSS
1
star
45

polygonclip-go

A Go implementation of the Greiner-Hormann clipping algorithm
JavaScript
1
star