From 6bc79c4fb9a3251a6c45932576c9c131c8c6efc3 Mon Sep 17 00:00:00 2001
From: hanemile <hanemile@protonmail.com>
Date: Sat, 3 Nov 2018 00:30:42 +0100
Subject: moved the files to the right dir

---
 structs.go | 153 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 153 insertions(+)
 create mode 100644 structs.go

(limited to 'structs.go')

diff --git a/structs.go b/structs.go
new file mode 100644
index 0000000..9406a5b
--- /dev/null
+++ b/structs.go
@@ -0,0 +1,153 @@
+package quadtree
+
+// coordinate type storing a position
+type Coord struct {
+	x float64
+	y float64
+}
+
+// newCoord returns a new coordinate using the given values
+func NewCoord(x float64, y float64) Coord {
+	return Coord{x, y}
+}
+
+func (point Coord) insideOf(quadtreeCell *quadtree) bool {
+	// define the bounds
+	var lowerXBound = quadtreeCell.boundary.center.x - quadtreeCell.boundary.halfDimension
+	var upperXBound = quadtreeCell.boundary.center.x + quadtreeCell.boundary.halfDimension
+	var lowerYBound = quadtreeCell.boundary.center.y - quadtreeCell.boundary.halfDimension
+	var upperYBound = quadtreeCell.boundary.center.y + quadtreeCell.boundary.halfDimension
+
+	// if the point is in the right x range
+	if point.x < upperXBound && point.x > lowerXBound {
+
+		// test if the point is in the right y range
+		if point.y < upperYBound && point.y > lowerYBound {
+
+			// the star is within the bounds: return true
+			return true
+		}
+	}
+
+	// the star is outside of the bounds: return false
+	return false
+}
+
+// boundingBox defines a single cell in the quadtree
+type boundingBox struct {
+	center        Coord
+	halfDimension float64
+}
+
+// newBoundingBox returns a new bounding with the given struct elements
+func newBoundingBox(inCenter Coord, inHalfDimension float64) boundingBox {
+	return boundingBox{
+		center:        inCenter,
+		halfDimension: inHalfDimension,
+	}
+}
+
+// quadtree defining the whole quadtree and a node in itself (recursively)
+type quadtree struct {
+	// general information (node capacity, spacial outreach)
+	nodeCapacity int
+	boundary     boundingBox
+
+	// slice storing the star coordinates
+	pointsSlice []Coord
+
+	// the quadtree leaves
+	northWest *quadtree
+	northEast *quadtree
+	southWest *quadtree
+	southEast *quadtree
+
+	depth int
+}
+
+// newQuadtree returns a new quadtree
+func newQuadtree(boundary boundingBox, depth int) *quadtree {
+	return &quadtree{
+		nodeCapacity: 0,
+		boundary:     boundary,
+		pointsSlice:  nil,
+		northWest:    nil,
+		northEast:    nil,
+		southWest:    nil,
+		southEast:    nil,
+		depth:        depth,
+	}
+}
+
+func (quadtree *quadtree) subdivide() {
+
+	// Create the new NorthWest boundingbox
+	var newCellBoundingNorthWest = boundingBox{
+		center: Coord{
+			x: quadtree.boundary.center.x - quadtree.boundary.halfDimension/2,
+			y: quadtree.boundary.center.y + quadtree.boundary.halfDimension/2,
+		},
+		halfDimension: quadtree.boundary.halfDimension / 2,
+	}
+	quadtree.northWest = newQuadtree(newCellBoundingNorthWest, quadtree.depth+1)
+
+	// Create the new NorthWest boundingbox
+	var newCellBoundingNorthEast = boundingBox{
+		center: Coord{
+			x: quadtree.boundary.center.x + quadtree.boundary.halfDimension/2,
+			y: quadtree.boundary.center.y + quadtree.boundary.halfDimension/2,
+		},
+		halfDimension: quadtree.boundary.halfDimension / 2,
+	}
+	quadtree.northEast = newQuadtree(newCellBoundingNorthEast, quadtree.depth+1)
+
+	// Create the new NorthWest boundingbox
+	var newCellBoundingSouthWest = boundingBox{
+		center: Coord{
+			x: quadtree.boundary.center.x - quadtree.boundary.halfDimension/2,
+			y: quadtree.boundary.center.y - quadtree.boundary.halfDimension/2,
+		},
+		halfDimension: quadtree.boundary.halfDimension / 2,
+	}
+	quadtree.southWest = newQuadtree(newCellBoundingSouthWest, quadtree.depth+1)
+
+	// Create the new NorthWest boundingbox
+	var newCellBoundingSouthEast = boundingBox{
+		center: Coord{
+			x: quadtree.boundary.center.x + quadtree.boundary.halfDimension/2,
+			y: quadtree.boundary.center.y - quadtree.boundary.halfDimension/2,
+		},
+		halfDimension: quadtree.boundary.halfDimension / 2,
+	}
+	quadtree.southEast = newQuadtree(newCellBoundingSouthEast, quadtree.depth+1)
+}
+
+// insert inserts the given point into the quadtree the method is applied on
+// it returns an error incase the point is not in bounds
+func (quadtree *quadtree) insert(point Coord) {
+
+	// subdivide the quadtree into four new cells
+	quadtree.subdivide()
+
+	// if the maxDepth is not reached...
+	if quadtree.depth < 4 {
+		// ... test if the given point is inside the one of the cells
+		// and add insert it to that specific cell
+		if point.insideOf(quadtree.northWest) {
+			quadtree.northWest.insert(point)
+		}
+		if point.insideOf(quadtree.northEast) {
+			quadtree.northEast.insert(point)
+		}
+		if point.insideOf(quadtree.southWest) {
+			quadtree.southWest.insert(point)
+		}
+		if point.insideOf(quadtree.southEast) {
+			quadtree.southEast.insert(point)
+		}
+	}
+
+	// if the maximal depth of the tree has been reached:
+	// insert the point into the slice
+	quadtree.pointsSlice = append(quadtree.pointsSlice, point)
+}
-- 
cgit 1.4.1