lib/quadtree/quadtree.rb in quadtree-1.0.4 vs lib/quadtree/quadtree.rb in quadtree-1.0.6
- old
+ new
@@ -1,127 +1,127 @@
-module Quadtree
- # A Quadtree.
- class Quadtree
-
- # 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.
- NODE_CAPACITY = 4
-
- # Axis-aligned bounding box stored as a center with half-dimensions to
- # represent the boundaries of this quad tree.
- # @return [AxisAlignedBoundingBox]
- attr_accessor :boundary
-
- # Points in this quad tree node.
- # @return [Array<Point>]
- attr_accessor :points
-
- # Children
-
- # North west corner of this quad.
- # @return [Quadtree]
- attr_accessor :north_west
-
- # North east corner of this quad.
- # @return [Quadtree]
- attr_accessor :north_east
-
- # South west corner of this quad.
- # @return [Quadtree]
- attr_accessor :south_west
-
- # South east corner of this quad.
- # @return [Quadtree]
- attr_accessor :south_east
-
- # @param boundary [AxisAlignedBoundingBox] the boundary for this {Quadtree}
- 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
-
- # Insert a {Point} in this {Quadtree}.
- #
- # @param point [Point] the point to insert.
- # @return [Boolean] +true+ on success, +false+ otherwise.
- 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
-
- # Finds all points contained within a range.
- #
- # @param range [AxisAlignedBoundingBox] the range to search within.
- # @return [Array<Point>]
- 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
-
- private
-
- # @return [Boolean]
- def subdivide!
- left_edge = self.boundary.left
- right_edge = self.boundary.right
- top_edge = self.boundary.top
- bottom_edge = self.boundary.bottom
- quad_half_dimension = self.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 => error
- puts "Something went wrong: #{error}"
- false
- end
- end
-end
+module Quadtree
+ # A Quadtree.
+ class Quadtree
+
+ # 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.
+ NODE_CAPACITY = 4
+
+ # Axis-aligned bounding box stored as a center with half-dimensions to
+ # represent the boundaries of this quad tree.
+ # @return [AxisAlignedBoundingBox]
+ attr_accessor :boundary
+
+ # Points in this quad tree node.
+ # @return [Array<Point>]
+ attr_accessor :points
+
+ # Children
+
+ # North west corner of this quad.
+ # @return [Quadtree]
+ attr_accessor :north_west
+
+ # North east corner of this quad.
+ # @return [Quadtree]
+ attr_accessor :north_east
+
+ # South west corner of this quad.
+ # @return [Quadtree]
+ attr_accessor :south_west
+
+ # South east corner of this quad.
+ # @return [Quadtree]
+ attr_accessor :south_east
+
+ # @param boundary [AxisAlignedBoundingBox] the boundary for this {Quadtree}
+ 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
+
+ # Insert a {Point} in this {Quadtree}.
+ #
+ # @param point [Point] the point to insert.
+ # @return [Boolean] +true+ on success, +false+ otherwise.
+ 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
+
+ # Finds all points contained within a range.
+ #
+ # @param range [AxisAlignedBoundingBox] the range to search within.
+ # @return [Array<Point>]
+ 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
+
+ private
+
+ # @return [Boolean]
+ def subdivide!
+ left_edge = self.boundary.left
+ right_edge = self.boundary.right
+ top_edge = self.boundary.top
+ bottom_edge = self.boundary.bottom
+ quad_half_dimension = self.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 => error
+ puts "Something went wrong: #{error}"
+ false
+ end
+ end
+end