Class: Tabula::SpatialIndex

Inherits:
Object
  • Object
show all
Defined in:
lib/tabula/core/spatial_index.rb

Overview

Spatial index for efficient rectangle queries. Uses a simple grid-based approach for O(1) average lookup.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(cell_size: 50.0) ⇒ SpatialIndex

Returns a new instance of SpatialIndex.

Parameters:

  • cell_size (Float) (defaults to: 50.0) —

    size of grid cells (default 50)



10
11
12
13
14
 
# File 'lib/tabula/core/spatial_index.rb', line 10

def initialize(cell_size: 50.0)
  @cell_size = cell_size
  @grid = Hash.new { |h, k| h[k] = [] }
  @rectangles = []
end

Instance Attribute Details

#rectangles ⇒ Object (readonly)

Returns the value of attribute rectangles.



7
8
9
 
# File 'lib/tabula/core/spatial_index.rb', line 7

def rectangles
  @rectangles
end

Instance Method Details

#add(rectangle) ⇒ Object

Add a rectangle to the index

Parameters:



18
19
20
21
22
23
24
 
# File 'lib/tabula/core/spatial_index.rb', line 18

def add(rectangle)
  @rectangles << rectangle
  cells_for(rectangle).each do |cell|
    @grid[cell] << rectangle
  end
  self
end

#add_all(rectangles) ⇒ Object

Add multiple rectangles

Parameters:

  • rectangles (Array<Rectangle>) —

    rectangles to add



28
29
30
31
 
# File 'lib/tabula/core/spatial_index.rb', line 28

def add_all(rectangles)
  rectangles.each { |r| add(r) }
  self
end

#at_point(point) ⇒ Array<Rectangle>

Find all rectangles that contain the query point

Parameters:

  • point (Point) —

    query point

Returns:

  • (Array<Rectangle>) —

    rectangles containing the point



52
53
54
55
 
# File 'lib/tabula/core/spatial_index.rb', line 52

def at_point(point)
  cell = cell_for_point(point)
  @grid[cell].select { |r| r.contains_point?(point) }
end

#bounds ⇒ Rectangle?

Compute bounding box of all indexed rectangles

Returns:

  • (Rectangle, nil) —

    bounding box or nil if empty



73
74
75
 
# File 'lib/tabula/core/spatial_index.rb', line 73

def bounds
  Rectangle.bounding_box_of(@rectangles)
end

#clear ⇒ Object

Clear all indexed rectangles



87
88
89
90
91
 
# File 'lib/tabula/core/spatial_index.rb', line 87

def clear
  @grid.clear
  @rectangles.clear
  self
end

#contains(query) ⇒ Array<Rectangle>

Find all rectangles that are fully contained within the query rectangle

Parameters:

Returns:

  • (Array<Rectangle>) —

    contained rectangles



44
45
46
47
 
# File 'lib/tabula/core/spatial_index.rb', line 44

def contains(query)
  candidates = candidate_set(query)
  candidates.select { |r| query.contains?(r) }
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


82
83
84
 
# File 'lib/tabula/core/spatial_index.rb', line 82

def empty?
  @rectangles.empty?
end

#intersects(query) ⇒ Array<Rectangle>

Find all rectangles that intersect with the query rectangle

Parameters:

Returns:

  • (Array<Rectangle>) —

    intersecting rectangles



36
37
38
39
 
# File 'lib/tabula/core/spatial_index.rb', line 36

def intersects(query)
  candidates = candidate_set(query)
  candidates.select { |r| r.intersects?(query) }
end

#nearby(query, distance) ⇒ Array<Rectangle>

Find rectangles within a given distance of the query rectangle

Parameters:

  • query (Rectangle) —

    query rectangle

  • distance (Float) —

    maximum distance

Returns:



61
62
63
64
65
66
67
68
69
 
# File 'lib/tabula/core/spatial_index.rb', line 61

def nearby(query, distance)
  expanded = Rectangle.from_bounds(
    query.top - distance,
    query.left - distance,
    query.bottom + distance,
    query.right + distance
  )
  intersects(expanded)
end

#size ⇒ Object

Number of indexed rectangles



78
79
80
 
# File 'lib/tabula/core/spatial_index.rb', line 78

def size
  @rectangles.size
end