Class: Quadtree::Quadtree

Inherits:
Object
  • Object
show all
Defined in:
lib/quadtree/quadtree.rb

Overview

A Quadtree

Since:

  • 1.0.0

Constant Summary collapse

NODE_CAPACITY =

Arbitrary constant to indicate how many elements can be stored in this quad tree node.

Returns:

  • (Integer)

Since:

  • 1.0.0

4

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(boundary) ⇒ Quadtree

Returns a new instance of Quadtree.

Since:

  • 1.0.0



30
31
32
33
34
35
36
37
 
# File 'lib/quadtree/quadtree.rb', line 30

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:

Since:

  • 1.0.0



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

def boundary
  @boundary
end

#north_east ⇒ Quadtree

Returns:

Since:

  • 1.0.0



24
25
26
 
# File 'lib/quadtree/quadtree.rb', line 24

def north_east
  @north_east
end

#north_west ⇒ Quadtree

Returns:

Since:

  • 1.0.0



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:

Since:

  • 1.0.0



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

def points
  @points
end

#south_east ⇒ Quadtree

Returns:

Since:

  • 1.0.0



28
29
30
 
# File 'lib/quadtree/quadtree.rb', line 28

def south_east
  @south_east
end

#south_west ⇒ Quadtree

Returns:

Since:

  • 1.0.0



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

def south_west
  @south_west
end

Instance Method Details

#insert!(point) ⇒ Boolean

Parameters:

Returns:

  • (Boolean)

Since:

  • 1.0.0



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/quadtree/quadtree.rb', line 41

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.

Parameters:

Returns:

Since:

  • 1.0.0



62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/quadtree/quadtree.rb', line 62

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