class Quadtree::Quadtree

A Quadtree.

Constants

NODE_CAPACITY

Arbitrary constant to indicate how many elements can be stored in this quad tree node. @return [Integer] number of {Point}s this {Quadtree} can hold.

Attributes

boundary[RW]

Axis-aligned bounding box stored as a center with half-dimensions to represent the boundaries of this quad tree. @return [AxisAlignedBoundingBox]

north_east[RW]

North east corner of this quad. @return [Quadtree]

north_west[RW]

North west corner of this quad. @return [Quadtree]

points[RW]

Points in this quad tree node. @return [Array<Point>]

south_east[RW]

South east corner of this quad. @return [Quadtree]

south_west[RW]

South west corner of this quad. @return [Quadtree]

Public Class Methods

from_json(json_data) click to toggle source

Construct a Quadtree from a JSON String.

@param [String] json_data input JSON String.

@return [Quadtree] the {Quadtree} contained in the JSON String.

# 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
new(boundary, points = [], north_west = nil, north_east = nil, south_west = nil, south_east = nil) click to toggle source

Create a new {Quadtree}.

@param [AxisAlignedBoundingBox] boundary the boundary for this {Quadtree}. @param [Array<Point>] points any initial {Point}s. @param [Quadtree] north_west northwestern child {Quadtree} @param [Quadtree] north_east northeastern child {Quadtree} @param [Quadtree] south_west southwestern child {Quadtree} @param [Quadtree] south_east southestern child {Quadtree}

# 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

Public Instance Methods

insert!(point) click to toggle source

Insert a {Point} in this {Quadtree}.

@param point [Point] the point to insert. @return [Boolean] true on success, false otherwise.

# 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) click to toggle source

Finds all points contained within a range.

@param range [AxisAlignedBoundingBox] the range to search within. @return [Array<Point>] all {Point}s in given range.

# 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() click to toggle source

Return the size of this instance, the number of {Point}s stored in this {Quadtree}.

@return [Integer] the size of this instance.

# 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() click to toggle source

Create a Hash from this {Quadtree}.

@return [Hash] Hash representation.

# 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() click to toggle source

Create a Hash from this {Quadtree}.

@return [Hash] Hash representation of this {Quadtree}.

# File lib/quadtree/quadtree.rb, line 78
def to_hash
  to_h
end
to_json(*_args) click to toggle source

Create a JSON String representation of this {Quadtree}.

@return [String] JSON String of this {Quadtree}.

# File lib/quadtree/quadtree.rb, line 87
def to_json(*_args)
  require 'json'
  to_h.to_json
end
to_s() click to toggle source

Create a String for this {Quadtree}.

@return [String] String representation of this {Quadtree}.

# File lib/quadtree/quadtree.rb, line 97
def to_s
  to_h.to_s
end

Private Instance Methods

subdivide!() click to toggle source

@return [Boolean] true on success, false otherwise.

# File lib/quadtree/quadtree.rb, line 187
def subdivide!
  left_edge = boundary.left
  right_edge = boundary.right
  top_edge = boundary.top
  bottom_edge = boundary.bottom
  quad_half_dimension = boundary.half_dimension / 2

  north_west_center = Point.new(left_edge + quad_half_dimension,
                                top_edge - quad_half_dimension)
  north_east_center = Point.new(right_edge - quad_half_dimension,
                                top_edge - quad_half_dimension)
  south_east_center = Point.new(left_edge + quad_half_dimension,
                                bottom_edge + quad_half_dimension)
  south_west_center = Point.new(right_edge - quad_half_dimension,
                                bottom_edge + quad_half_dimension)

  north_west_boundary = AxisAlignedBoundingBox.new(north_west_center,
                                                   quad_half_dimension)
  north_east_boundary = AxisAlignedBoundingBox.new(north_east_center,
                                                   quad_half_dimension)
  south_west_boundary = AxisAlignedBoundingBox.new(south_west_center,
                                                   quad_half_dimension)
  south_east_boundary = AxisAlignedBoundingBox.new(south_east_center,
                                                   quad_half_dimension)

  self.north_west = Quadtree.new north_west_boundary
  self.north_east = Quadtree.new north_east_boundary
  self.south_west = Quadtree.new south_west_boundary
  self.south_east = Quadtree.new south_east_boundary

  true
rescue StandardError
  false
end