-
Notifications
You must be signed in to change notification settings - Fork 0
/
quadtree.h
71 lines (60 loc) · 1.75 KB
/
quadtree.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Name:
// Quarter, Year:
// Lab:
//
// This file is to be modified by the student.
// quadtree.h
////////////////////////////////////////////////////////////
#ifndef __QUADTREE_H__
#define __QUADTREE_H__
#include <vector>
#include "object.h"
enum QuadTreeType { QUAD_TREE_PARENT, QUAD_TREE_LEAF };
class QuadTreeNode
{
public:
QuadTreeNode(const Rect2D & space);
void insert(const Line2D & value, int currentDepth, int depthLimit, int listLimit);
void query(const Point2D & mbr, std::vector<Line2D> & ret) const;
void dealloc();
void render() const;
private:
//Shared between Parent and Leaf Nodes
QuadTreeType nodeType;
Rect2D space;
//Information for Leaf Nodes
std::vector<Line2D> objects;
//Information for Parent Nodes
QuadTreeNode* topLeft;
QuadTreeNode* topRight;
QuadTreeNode* bottomLeft;
QuadTreeNode* bottomRight;
//Useful Helper Functions
QuadTreeNode* findQuadrant(const Point2D & p) const;
std::vector<Line2D> splitLine(const Line2D & value) const;
int findQuadrantNumber(const Point2D & p) const;
};
//A Wrapper for the QuadTreeNode class
class QuadTree
{
public:
QuadTree(const Rect2D & space, int dLim, int listLim);
~QuadTree();
void insert(const Line2D & value);
std::vector<Line2D> query(const Point2D & p) const;
std::vector<Line2D> query(const Point2D & p, const Circle2D c);
void render() const;
private:
QuadTreeNode* root;
//These are additional variables to simplify the QuadTree
//
//A LEAF node cannot become a PARENT node if its depth in the recursion
//is greater than or equal to depthLimit.
//
//The listLimit variable is a relaxed limit to notify when a LEAF node
//should split. This condition is not met when the LEAF node is already
//at the lowest depth in the tree.
int depthLimit;
int listLimit;
};
#endif