Class: RQuad::QuadTree

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

Overview

A quadtree node that can contain QuadTreePayloads and other QuadTree nodes. A quadtree is a tree that subdivides space into recursively defined quadrents that (in this implementation) can contain no more than one spacially-unique payload. Quadtrees are good for answering questions about neighborhoods of points in a space.

Making a quadtree is simple, just initialize a new QuadTree with two vectors, its top left and bottom right points, then add QuadTreePayloads to it and it will store them in an efficiently constructed quadtree structure. You may then ask for all payloads in a region, all payloads near a point, etc.

Example usage with longitudes and latitudes:

qt = QuadTree.new(Vector.new(-180, 90), Vector.new(180, -90)) qt.add(QuadTreePayload.new(Vector.new(lng1, lat1), entity1)) qt.add(QuadTreePayload.new(Vector.new(lng2, lat2), entity2)) qt.add(QuadTreePayload.new(Vector.new(lng3, lat3), entity3)) qt.add(QuadTreePayload.new(Vector.new(lng4, lat4), entity4))

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tl, br, parent_node = nil) ⇒ QuadTree

Initialize a new QuadTree with two vectors: its top-left corner and its bottom-right corner. Optionally, you can also provide a reference to this node’s parent node.



66
67
68
69
70
71
72
73
 
# File 'lib/rquad/quadtree.rb', line 66

def initialize(tl, br, parent_node = nil)
  @parent = parent_node
  @tl = tl
  @br = br
  @size = 0
  @summed_contained_vectors = Vector.new(0,0)
  @depth = 0
end

Instance Attribute Details

#br ⇒ Object

You may ask a QuadTree for its ‘payload`, `tl` point, `br` point, and `depth`.



63
64
65
 
# File 'lib/rquad/quadtree.rb', line 63

def br
  @br
end

#depth ⇒ Object

You may ask a QuadTree for its ‘payload`, `tl` point, `br` point, and `depth`.



63
64
65
 
# File 'lib/rquad/quadtree.rb', line 63

def depth
  @depth
end

#payload ⇒ Object

You may ask a QuadTree for its ‘payload`, `tl` point, `br` point, and `depth`.



63
64
65
 
# File 'lib/rquad/quadtree.rb', line 63

def payload
  @payload
end

#tl ⇒ Object

You may ask a QuadTree for its ‘payload`, `tl` point, `br` point, and `depth`.



63
64
65
 
# File 'lib/rquad/quadtree.rb', line 63

def tl
  @tl
end

Instance Method Details

#add(geo_data, depth = 1, jitter_proc = nil) ⇒ Object

Add a QuadTreePayload to this QuadTree. If this node is empty, it will be stored in this node. If not, both the new payload and the old one will be recursively added to the appropriate one of the four children of this node. There is a special case: if this node already has a payload and the new payload has an identical position to the existing payload, then the new payload will be stored here in ddition to the existing payload.

jitter_proc - a Proc object that, if provided, is used to jitter payloads with identical vectors (accepts and returns a QuadTreePayload).



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/rquad/quadtree.rb', line 77

def add(geo_data, depth = 1, jitter_proc = nil)
  geo_data.node = self
  if size > 0
    if @payload && (@payload.first.vector == geo_data.vector)
      # The vectors match.
      if jitter_proc
        @payload << jitter_proc.call(geo_data)
      else
        @payload << geo_data
      end
    else
      # The vectors don't match.
      if payload
        @payload.each { |p| add_into_subtree(p, depth + 1, jitter_proc) }
        @payload = nil
      end
      add_into_subtree(geo_data, depth + 1, jitter_proc)
    end
  else
    @payload = [geo_data]
    @depth = depth
  end
  @summed_contained_vectors += geo_data.vector
  @size += 1
end

#approx_near(location, approx_number) ⇒ Object

Returns approxametly ‘approx_number` payloads near `location`.



201
202
203
204
205
206
207
 
# File 'lib/rquad/quadtree.rb', line 201

def approx_near(location, approx_number)
  if approx_number >= size
    return get_contained_payloads
  else
    get_containing_quad(location).approx_near(location, approx_number)
  end
end

#blq(build = true) ⇒ Object

The bottom-left quadrent of this quadtree. If ‘build` is true, this will make the quadrent quadtree if it doesn’t alredy exist.



268
269
270
271
 
# File 'lib/rquad/quadtree.rb', line 268

def blq(build = true)
  @blq ||= QuadTree.new(Vector.new(tl.x, br.y + (tl.y - br.y) / 2.0), Vector.new(tl.x + (br.x - tl.x) / 2.0, br.y), self) if build
  @blq
end

#blq? ⇒ Boolean

Returns true if this quadtree has a bottom-left quadrent already defined.

Returns:

  • (Boolean) 


290
291
292
 
# File 'lib/rquad/quadtree.rb', line 290

def blq?
  @blq && (@blq.payload || (@blq.tlq? || @blq.trq? || @blq.blq? || @blq.brq?))
end

#breadth_first_each ⇒ Object

Performs a breath-first traversal of this quadtree, yielding [node, depth] for each node.



142
143
144
145
146
147
148
149
150
151
152
 
# File 'lib/rquad/quadtree.rb', line 142

def breadth_first_each
  queue = [self]
  while queue.length > 0
    node = queue.shift
    queue << node.tlq if node.tlq?
    queue << node.trq if node.trq?
    queue << node.blq if node.blq?
    queue << node.brq if node.brq?
    yield node, node.depth
  end
end

#brq(build = true) ⇒ Object

The bottom-right quadrent of this quadtree. If ‘build` is true, this will make the quadrent quadtree if it doesn’t alredy exist.



274
275
276
277
 
# File 'lib/rquad/quadtree.rb', line 274

def brq(build = true)
  @brq ||= QuadTree.new(Vector.new(tl.x + (br.x - tl.x) / 2.0, br.y + (tl.y - br.y) / 2.0), Vector.new(br), self) if build
  @brq
end

#brq? ⇒ Boolean

Returns true if this quadtree has a bottom-right quadrent already defined.

Returns:

  • (Boolean) 


295
296
297
 
# File 'lib/rquad/quadtree.rb', line 295

def brq?
  @brq && (@brq.payload || (@brq.tlq? || @brq.trq? || @brq.blq? || @brq.brq?))
end

#center_of_mass ⇒ Object

Returns the centroid of the payloads contained in this quadtree.



137
138
139
 
# File 'lib/rquad/quadtree.rb', line 137

def center_of_mass
  @summed_contained_vectors / @size
end

#center_of_masses_in_region(region_tl, region_br, depth) ⇒ Object

Returns an array of [centroid (Vector), count] pairs summarizing the set of centroids at a certain tree depth. That is, it provides centroids and counts of all of the subtrees still available at depth ‘depth`, plus any that terminated above that depth.



224
225
226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/rquad/quadtree.rb', line 224

def center_of_masses_in_region(region_tl, region_br, depth)
  quad1 = get_containing_quad(region_tl)
  quad2 = get_containing_quad(region_br)
  if quad1 == quad2 && payload.nil?
    quad1.center_of_masses_in_region(region_tl, region_br, depth)
  else
    centers_of_mass = []
    leaves_each(depth) do |node|
      centers_of_mass << [node.center_of_mass, node.size]
    end
    centers_of_mass
  end    
end

#child_of?(node) ⇒ Boolean

True if this node is a direct child of ‘node`.

Returns:

  • (Boolean) 


170
171
172
 
# File 'lib/rquad/quadtree.rb', line 170

def child_of?(node)
  node.parent_of?(self)
end

#clip_vector(v) ⇒ Object

Clips Vector ‘v` to the bounds of this quadtree.



306
307
308
309
310
311
312
313
 
# File 'lib/rquad/quadtree.rb', line 306

def clip_vector(v)
  v = v.dup
  v.x = tl.x if v.x < tl.x
  v.y = tl.y if v.y > tl.y
  v.x = br.x if v.x > br.x
  v.y = br.y if v.y < br.y
  v
end

#each_payload ⇒ Object

Yields each payload in this quadtree via a breadth-first traversal.



155
156
157
158
159
160
161
162
 
# File 'lib/rquad/quadtree.rb', line 155

def each_payload
  breadth_first_each do |node, depth|
    next unless node.payload
    node.payload.each do |payload|
      yield payload
    end
  end
end

#family_size_at_width(in_tl, in_br) ⇒ Object

Scans back up a quadtree from this node until a node is found that contains the region defined by ‘in_tl` and `in_br`, at which point the subtree size is returned from that point. (Only scans back up the tree, won’t scan down.)



317
318
319
320
321
322
323
 
# File 'lib/rquad/quadtree.rb', line 317

def family_size_at_width(in_tl, in_br)
  if (inside?(in_tl) && inside?(in_br)) || parent.nil?
    size
  else
    parent.family_size_at_width(in_tl, in_br)
  end
end

#get_contained(options = {}) ⇒ Object

This method returns the payloads contained under this node in the quadtree. It takes an options hash with the following optional keys:

:max_count - the maximum number of payloads to return, provided via a breadth-first search.
:details_proc - a Proc object to which every internal node at the maximum deoth achieved by the search is passed -- this is useful for providing summary statistics about subtrees that were not explored by this traversal due to a :max_count limitation.
:requirement_proc - a Proc object that, if provided, must return true when evaluating a payload in order for that payload to be returned.

Returns a Hash with keys :payloads, an array of all of the payloads below this node, and :details, the mapped result of applying :details_proc (if provided) to every internal node at the mximum depth achieved by the search.



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/rquad/quadtree.rb', line 108

def get_contained(options = {})
  payloads = []
  internal_nodes = []
  last_depth = -1
  breadth_first_each do |node, depth|
    break if options[:max_count] && payloads.length >= options[:max_count] && (!options[:details_proc] || depth != last_depth)

    if node.payload
      internal_nodes.delete_if {|i| i.parent_of?(node)} if options[:details_proc]
      node.payload.each do |entry|
        if !options[:requirement_proc] || options[:requirement_proc].call(entry)
          payloads << entry
        end
      end
    elsif options[:details_proc] && (node.tlq? || node.trq? || node.blq? || node.brq?)
      internal_nodes.delete_if {|i| i.parent_of?(node)}
      internal_nodes << node
    end
    last_depth = depth
  end
  { :payloads => payloads, :details => (options[:details_proc] ? internal_nodes.map {|i| options[:details_proc].call(i)} : nil) }
end

#get_contained_payloads(options = {}) ⇒ Object

Calls get_contained and only returns the :payloads key. Accepts the same options as get_contained except for the :details_proc option.



132
133
134
 
# File 'lib/rquad/quadtree.rb', line 132

def get_contained_payloads(options = {})
  get_contained(options)[:payloads]
end

#inside?(v) ⇒ Boolean

Returns true if Vector ‘v` falls inside of this quadtree.

Returns:

  • (Boolean) 


300
301
302
303
 
# File 'lib/rquad/quadtree.rb', line 300

def inside?(v)
  # Greedy, so the order of comparison of quads will matter.
  tl.x <= v.x && br.x >= v.x && tl.y >= v.y && br.y <= v.y
end

#inspect ⇒ Object 



329
330
331
 
# File 'lib/rquad/quadtree.rb', line 329

def inspect
  to_s
end

#leaves_each(leaf_depth) ⇒ Object

Yields all pseudo-leaves formed when the graph is cut off at a certain depth, plus any leaves encountered before that depth.



175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/rquad/quadtree.rb', line 175

def leaves_each(leaf_depth)
  stack = [self]
  while stack.length > 0
    node = stack.pop
    start_size = stack.length
    stack << node.tlq if node.tlq? && node.tlq.depth < leaf_depth + depth
    stack << node.trq if node.trq? && node.trq.depth < leaf_depth + depth
    stack << node.blq if node.blq? && node.blq.depth < leaf_depth + depth
    stack << node.brq if node.brq? && node.brq.depth < leaf_depth + depth
    if node.depth == leaf_depth + depth - 1 || (!node.tlq? && !node.trq? && !node.blq? && !node.brq?)
      yield node
    end
  end
end

#parent ⇒ Object

Returns this node’s parent node or nil if this node is a root node.



196
197
198
 
# File 'lib/rquad/quadtree.rb', line 196

def parent
  @parent
end

#parent_of?(node) ⇒ Boolean

True if this node is a direct parent of ‘node`.

Returns:

  • (Boolean) 


165
166
167
 
# File 'lib/rquad/quadtree.rb', line 165

def parent_of?(node)
  node && node == tlq(false) || node == trq(false) || node == blq(false) || node == brq(false)
end

#payloads_and_centers_in_region(region_tl, region_br, approx_num_to_return) ⇒ Object

Returns a hash with keys :payloads and :details. The :payloads are payloads found, while details are for nodes that didn’t get to be explored because the requisite number of payloads were already found.



239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
 
# File 'lib/rquad/quadtree.rb', line 239

def payloads_and_centers_in_region(region_tl, region_br, approx_num_to_return)
  quad1 = get_containing_quad(region_tl)
  quad2 = get_containing_quad(region_br)
  if quad1 == quad2 && payload.nil?
    quad1.payloads_and_centers_in_region(region_tl, region_br, approx_num_to_return)
  else
    region_containment_proc = lambda do |i|
      region_tl.x <= i.vector.x && region_br.x >= i.vector.x && region_tl.y >= i.vector.y && region_br.y <= i.vector.y
    end
    details_proc = lambda do |i|
      [i.center_of_mass, i.size]
    end
    get_contained(:max_count => approx_num_to_return, :requirement_proc => region_containment_proc, :details_proc => details_proc)
  end
end

#payloads_in_region(region_tl, region_br, max_number = nil) ⇒ Object

Returns up to ‘max_number` payloads inside of the region specified by `region_tl` and `region_br`.



210
211
212
213
214
215
216
217
218
219
220
221
 
# File 'lib/rquad/quadtree.rb', line 210

def payloads_in_region(region_tl, region_br, max_number = nil)
  quad1 = get_containing_quad(region_tl)
  quad2 = get_containing_quad(region_br)
  if quad1 == quad2 && payload.nil?
    quad1.payloads_in_region(region_tl, region_br, max_number)
  else
    region_containment_proc = lambda do |i|
      region_tl.x <= i.vector.x && region_br.x >= i.vector.x && region_tl.y >= i.vector.y && region_br.y <= i.vector.y
    end
    get_contained_payloads(:max_count => max_number, :requirement_proc => region_containment_proc)
  end
end

#size ⇒ Object

Returns the size of this node: the number of contained payloads.



191
192
193
 
# File 'lib/rquad/quadtree.rb', line 191

def size
  @size
end

#tlq(build = true) ⇒ Object

The top-left quadrent of this quadtree. If ‘build` is true, this will make the quadrent quadtree if it doesn’t alredy exist.



256
257
258
259
 
# File 'lib/rquad/quadtree.rb', line 256

def tlq(build = true)
  @tlq ||= QuadTree.new(Vector.new(tl), Vector.new(tl.x + (br.x - tl.x) / 2.0, br.y + (tl.y - br.y) / 2.0), self) if build
  @tlq
end

#tlq? ⇒ Boolean

Returns true if this quadtree has a top-left quadrent already defined.

Returns:

  • (Boolean) 


280
281
282
 
# File 'lib/rquad/quadtree.rb', line 280

def tlq?
  @tlq && (@tlq.payload || (@tlq.tlq? || @tlq.trq? || @tlq.blq? || @tlq.brq?))
end

#to_s ⇒ Object 



325
326
327
 
# File 'lib/rquad/quadtree.rb', line 325

def to_s
  "[Quadtree #{object_id}, size: #{size}, depth: #{depth}]"
end

#trq(build = true) ⇒ Object

The top-right quadrent of this quadtree. If ‘build` is true, this will make the quadrent quadtree if it doesn’t alredy exist.



262
263
264
265
 
# File 'lib/rquad/quadtree.rb', line 262

def trq(build = true)
  @trq ||= QuadTree.new(Vector.new(tl.x + (br.x - tl.x) / 2.0, tl.y), Vector.new(br.x, br.y + (tl.y - br.y) / 2.0), self) if build
  @trq
end

#trq? ⇒ Boolean

Returns true if this quadtree has a top-right quadrent already defined.

Returns:

  • (Boolean) 


285
286
287
 
# File 'lib/rquad/quadtree.rb', line 285

def trq?
  @trq && (@trq.payload || (@trq.tlq? || @trq.trq? || @trq.blq? || @trq.brq?))
end