Class: Quadtree::Quadtree
- Inherits:
-
Object
- Object
- Quadtree::Quadtree
- Defined in:
- lib/quadtree/quadtree.rb
Overview
A Quadtree.
Constant Summary collapse
- NODE_CAPACITY =
Arbitrary constant to indicate how many elements can be stored in this quad tree node.
4
Instance Attribute Summary collapse
-
#boundary ⇒ AxisAlignedBoundingBox
Axis-aligned bounding box stored as a center with half-dimensions to represent the boundaries of this quad tree.
-
#north_east ⇒ Quadtree
North east corner of this quad.
-
#north_west ⇒ Quadtree
North west corner of this quad.
-
#points ⇒ Array<Point>
Points in this quad tree node.
-
#south_east ⇒ Quadtree
South east corner of this quad.
-
#south_west ⇒ Quadtree
South west corner of this quad.
Instance Method Summary collapse
-
#initialize(boundary) ⇒ Quadtree
constructor
A new instance of Quadtree.
- #insert!(point) ⇒ Boolean
-
#query_range(range) ⇒ Array<Point>
Finds all points contained within a range.
Constructor Details
#initialize(boundary) ⇒ Quadtree
Returns a new instance of Quadtree.
38 39 40 41 42 43 44 45 |
# File 'lib/quadtree/quadtree.rb', line 38 def initialize(boundary) self.boundary = boundary self.points = [] self.north_west = nil self.north_east = nil self.south_west = nil self.south_east = nil end |
Instance Attribute Details
#boundary ⇒ AxisAlignedBoundingBox
Axis-aligned bounding box stored as a center with half-dimensions to represent the boundaries of this quad tree.
13 14 15 |
# File 'lib/quadtree/quadtree.rb', line 13 def boundary @boundary end |
#north_east ⇒ Quadtree
North east corner of this quad.
27 28 29 |
# File 'lib/quadtree/quadtree.rb', line 27 def north_east @north_east end |
#north_west ⇒ Quadtree
North west corner of this quad.
23 24 25 |
# File 'lib/quadtree/quadtree.rb', line 23 def north_west @north_west end |
#points ⇒ Array<Point>
Points in this quad tree node.
17 18 19 |
# File 'lib/quadtree/quadtree.rb', line 17 def points @points end |
#south_east ⇒ Quadtree
South east corner of this quad.
35 36 37 |
# File 'lib/quadtree/quadtree.rb', line 35 def south_east @south_east end |
#south_west ⇒ Quadtree
South west corner of this quad.
31 32 33 |
# File 'lib/quadtree/quadtree.rb', line 31 def south_west @south_west end |
Instance Method Details
#insert!(point) ⇒ Boolean
Insert a Point in this Quadtree::Quadtree.
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
# File 'lib/quadtree/quadtree.rb', line 51 def insert!(point) return false unless self.boundary.contains_point?(point) if self.points.size < NODE_CAPACITY self.points << point return true end subdivide! if self.north_west.nil? return true if self.north_west.insert!(point) return true if self.north_east.insert!(point) return true if self.south_west.insert!(point) return true if self.south_east.insert!(point) false end |
#query_range(range) ⇒ Array<Point>
Finds all points contained within a range.
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
# File 'lib/quadtree/quadtree.rb', line 72 def query_range(range) # Prepare an array of results points_in_range = [] # Automatically abort if the range does not intersect this quad return points_in_range unless self.boundary.intersects?(range) # Check objects at this quad level self.points.each do |point| points_in_range << point if range.contains_point?(point) end # Terminate here, if there are no children return points_in_range if self.north_west.nil? # Otherwise, add the points from the children points_in_range += self.north_west.query_range(range) points_in_range += self.north_east.query_range(range) points_in_range += self.south_west.query_range(range) points_in_range += self.south_east.query_range(range) points_in_range end |