Class: Quadtree::Quadtree

Inherits:
Object
  • Object
show all
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.

Returns:

4

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(boundary) ⇒ Quadtree

Returns a new instance of Quadtree.

Parameters:



37
38
39
40
41
42
43
44
 
# File 'lib/quadtree/quadtree.rb', line 37

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.

Returns:



12
13
14
 
# File 'lib/quadtree/quadtree.rb', line 12

def boundary
  @boundary
end

#north_east ⇒ Quadtree

North east corner of this quad.

Returns:



26
27
28
 
# File 'lib/quadtree/quadtree.rb', line 26

def north_east
  @north_east
end

#north_west ⇒ Quadtree

North west corner of this quad.

Returns:



22
23
24
 
# File 'lib/quadtree/quadtree.rb', line 22

def north_west
  @north_west
end

#points ⇒ Array<Point>

Points in this quad tree node.

Returns:



16
17
18
 
# File 'lib/quadtree/quadtree.rb', line 16

def points
  @points
end

#south_east ⇒ Quadtree

South east corner of this quad.

Returns:



34
35
36
 
# File 'lib/quadtree/quadtree.rb', line 34

def south_east
  @south_east
end

#south_west ⇒ Quadtree

South west corner of this quad.

Returns:



30
31
32
 
# File 'lib/quadtree/quadtree.rb', line 30

def south_west
  @south_west
end

Instance Method Details

#insert!(point) ⇒ Boolean

Insert a Point in this Quadtree::Quadtree.

Parameters:

  • point (Point) —

    the point to insert.

Returns:

  • (Boolean) —

    true on success, false otherwise.



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/quadtree/quadtree.rb', line 50

def insert!(point)
  return false unless boundary.contains_point?(point)

  if points.size < NODE_CAPACITY
    points << point
    return true
  end

  subdivide! if north_west.nil?
  return true if north_west.insert!(point)
  return true if north_east.insert!(point)
  return true if south_west.insert!(point)
  return true if south_east.insert!(point)

  false
end

#query_range(range) ⇒ Array<Point>

Finds all points contained within a range.

Parameters:

Returns:



86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/quadtree/quadtree.rb', line 86

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 boundary.intersects?(range)

  # Check objects at this quad level
  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 north_west.nil?

  # Otherwise, add the points from the children
  points_in_range += north_west.query_range(range)
  points_in_range += north_east.query_range(range)
  points_in_range += south_west.query_range(range)
  points_in_range += south_east.query_range(range)

  points_in_range
end

#size ⇒ Integer

Return the size of this instance, the number of Points stored in this

{Quadtree}.

Returns:

  • (Integer) —

    the size of this instance.



70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/quadtree/quadtree.rb', line 70

def size
  count = 0
  count += points.size
  unless north_west.nil?
    count += north_west.size
    count += north_east.size
    count += south_west.size
    count += south_east.size
  end
  count
end