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

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(boundary, points = [], north_west = nil, north_east = nil, south_west = nil, south_east = nil) ⇒ Quadtree

Create a new Quadtree::Quadtree.

Parameters:



48
49
50
51
52
53
54
55
 
# File 'lib/quadtree/quadtree.rb', line 48

def initialize(boundary, points = [], north_west = nil, north_east = nil, south_west = nil, south_east = nil)
  self.boundary = boundary
  self.points = points
  self.north_west = north_west
  self.north_east = north_east
  self.south_west = south_west
  self.south_east = south_east
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:



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

def boundary
  @boundary
end

#north_east ⇒ Quadtree

North east corner of this quad.

Returns:



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

def north_east
  @north_east
end

#north_west ⇒ Quadtree

North west corner of this quad.

Returns:



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

def north_west
  @north_west
end

#points ⇒ Array<Point>

Points in this quad tree node.

Returns:



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

def points
  @points
end

#south_east ⇒ Quadtree

South east corner of this quad.

Returns:



36
37
38
 
# File 'lib/quadtree/quadtree.rb', line 36

def south_east
  @south_east
end

#south_west ⇒ Quadtree

South west corner of this quad.

Returns:



32
33
34
 
# File 'lib/quadtree/quadtree.rb', line 32

def south_west
  @south_west
end

Class Method Details

.from_json(json_data) ⇒ Quadtree

Construct a Quadtree from a JSON String.

Parameters:

  • json_data (String) —

    input JSON String.

Returns:



108
109
110
111
112
113
114
115
116
117
 
# File 'lib/quadtree/quadtree.rb', line 108

def self.from_json(json_data)
  new(
    AxisAlignedBoundingBox.from_json(json_data['boundary']),
    json_data['points'].map { |point_data| Point.from_json(point_data) },
    json_data['north_west'].nil? ? nil : Quadtree.from_json(json_data['north_west']),
    json_data['north_east'].nil? ? nil : Quadtree.from_json(json_data['north_east']),
    json_data['south_west'].nil? ? nil : Quadtree.from_json(json_data['south_west']),
    json_data['south_east'].nil? ? nil : Quadtree.from_json(json_data['south_east'])
  )
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.



123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/quadtree/quadtree.rb', line 123

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:



160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
 
# File 'lib/quadtree/quadtree.rb', line 160

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::Quadtree.

Returns:

  • (Integer) —

    the size of this instance.



144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/quadtree/quadtree.rb', line 144

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

#to_h ⇒ Hash

Create a Hash from this Quadtree::Quadtree.

Returns:

  • (Hash) —

    Hash representation.



62
63
64
65
66
67
68
69
70
71
 
# File 'lib/quadtree/quadtree.rb', line 62

def to_h
  {
    'boundary': boundary.to_h,
    'points': points.map(&:to_h),
    'north_west': north_west.nil? ? nil : north_west.to_h,
    'north_east': north_east.nil? ? nil : north_east.to_h,
    'south_west': south_west.nil? ? nil : south_west.to_h,
    'south_east': south_east.nil? ? nil : south_east.to_h
  }
end

#to_hash ⇒ Hash

Create a Hash from this Quadtree::Quadtree.

Returns:



78
79
80
 
# File 'lib/quadtree/quadtree.rb', line 78

def to_hash
  to_h
end

#to_json(*_args) ⇒ String

Create a JSON String representation of this Quadtree::Quadtree.

Returns:



87
88
89
90
 
# File 'lib/quadtree/quadtree.rb', line 87

def to_json(*_args)
  require 'json'
  to_h.to_json
end

#to_s ⇒ String

Create a String for this Quadtree::Quadtree.

Returns:



97
98
99
 
# File 'lib/quadtree/quadtree.rb', line 97

def to_s
  to_h.to_s
end