moved the files to the right dir

2 files changed, 279 insertions, 0 deletions

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)
+}
diff --git a/structs_test.go b/structs_test.go
new file mode 100644
index 0000000..66598bf
--- /dev/null
+++ b/structs_test.go
@@ -0,0 +1,126 @@
+package quadtree
+
+import (
+	"testing"
+)
+
+// Quadtree Test
+func TestQuadtree(t *testing.T) {
+	testQuadtree := quadtree{
+		nodeCapacity: 0,
+		boundary:     boundingBox{},
+		pointsSlice:  nil,
+		northWest:    nil,
+		northEast:    nil,
+		southWest:    nil,
+		southEast:    nil,
+	}
+
+	t.Log(testQuadtree)
+}
+
+// NewQuadTree test
+func TestNewQuadtree(t *testing.T) {
+	var boundary = boundingBox{
+		center:        Coord{0, 0},
+		halfDimension: 3,
+	}
+
+	var newQuadtree = *newQuadtree(boundary, 0)
+
+	t.Log(newQuadtree)
+}
+
+// Coordinate Test
+func TestCoord(t *testing.T) {
+	testCoord := Coord{
+		x: 0,
+		y: 1,
+	}
+
+	t.Log(testCoord)
+}
+
+// NewCoord test
+func TestNewCoord(t *testing.T) {
+	var newCoordinate = NewCoord(1, 2)
+
+	t.Log(newCoordinate)
+}
+
+func TestBoundingBox(t *testing.T) {
+	var newBoundingBox = boundingBox{
+		center: Coord{
+			x: 1,
+			y: 2,
+		},
+		halfDimension: 3,
+	}
+
+	t.Log(newBoundingBox)
+}
+
+func TestInsideOf(t *testing.T) {
+	var testCoordinate = Coord{0, 0}
+	var testQuadTree = newQuadtree(boundingBox{
+		center: Coord{
+			x: 0,
+			y: 0,
+		},
+		halfDimension: 1,
+	}, 0)
+
+	var isInsideOf = testCoordinate.insideOf(testQuadTree)
+	t.Log(isInsideOf)
+}
+
+// Test the newBoundingBox function
+func TestNewBoundingBox(t *testing.T) {
+
+	// Initialize some values that are needed
+	var newCenter = Coord{1, 2}
+	var newHalfDimension float64 = 3
+
+	// Initialize the bounding box using the values above
+	var newBoundingBox = newBoundingBox(newCenter, newHalfDimension)
+
+	// Print the newBoundingBox
+	t.Log(newBoundingBox)
+}
+
+func TestSubdivide(t *testing.T) {
+	var boundary = boundingBox{
+		center:        Coord{0, 0},
+		halfDimension: 3,
+	}
+
+	var newQuadtree = *newQuadtree(boundary, 0)
+
+	newQuadtree.subdivide()
+
+	t.Logf("newQuadTree: %v\n", newQuadtree)
+	t.Logf("NorthWestCell: %v\n", newQuadtree.northWest)
+	t.Logf("NorthEestCell: %v\n", newQuadtree.northEast)
+	t.Logf("SouthWestCell: %v\n", newQuadtree.southWest)
+	t.Logf("SouthEastCell: %v\n", newQuadtree.southEast)
+
+}
+
+// test the insert function
+func TestInsert(t *testing.T) {
+	// Define a new quadtree-root-boundary
+	var boundary = boundingBox{
+		center:        Coord{0, 0},
+		halfDimension: 3,
+	}
+
+	// create a new quadtree using the boundary
+	var newQuadtree = *newQuadtree(boundary, 0)
+
+	// Define a star and insert it into the quadtree
+	singleCoord := Coord{0.5, 0.5}
+	newQuadtree.insert(singleCoord)
+
+	// Print the stuff generated
+	t.Logf("Complete Tree: %v\n", newQuadtree.northEast.southWest.southWest.northEast)
+}