Class: Tsuga::Service::Aggregator

Inherits:
Object
  • Object
show all
Defined in:
lib/tsuga/service/aggregator.rb

Overview

Aggregates clusters together until no two clusters are closer than a given minimum distance.

Defined Under Namespace

Classes: FencedPair, IdSet, Pair

Instance Method Summary collapse

Constructor Details

#initialize(clusters: nil, ratio: nil, fence: nil) ⇒ Aggregator

  • clusters (Array): list of points to aggregate

  • fence (Tile): clusters outside this will not be aggregated

  • ratio (0..1): minimum distance between clusters after aggregation, as a ratio of the tile diagonal



14
15
16
17
18
19
20
 
# File 'lib/tsuga/service/aggregator.rb', line 14

def initialize(clusters:nil, ratio:nil, fence:nil)
  @_clusters          = clusters
  @_fence             = fence || _default_fence
  @min_distance_ratio = ratio # fraction of tile diagonal
  @_dropped_clusters   = IdSet.new
  @_updated_clusters   = IdSet.new
end

Instance Method Details

#dropped_clusters ⇒ Object

after #run, this contains the clusters that were merged into other clusters



69
70
71
 
# File 'lib/tsuga/service/aggregator.rb', line 69

def dropped_clusters
  _dropped_clusters.to_a
end

#min_distance ⇒ Object

fraction of the diagonal of the fence tile



79
80
81
 
# File 'lib/tsuga/service/aggregator.rb', line 79

def min_distance
  @min_distance ||= (_fence.southwest & _fence.northeast) * @min_distance_ratio
end

#run ⇒ Object 



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/tsuga/service/aggregator.rb', line 22

def run
  return if _clusters.empty?
  warn "warning: running aggregation on many clusters (#{_clusters.size})" if _clusters.size > 100

  if DENSITY_BIAS_FACTOR
    @min_density, @max_density = _clusters.collect(&:density).minmax
  end

  # build the set of pairs (n²/2)
  pairs  = []
  source = _clusters.dup
  while left = source.pop
    source.each do |right| 
      pairs << _build_pair(left, right, _fence)
    end
  end

  # pop & merge
  while pairs.any?
    best_pair = pairs.min
    break if best_pair.distance > min_distance

    # remove the closest pair
    left, right = best_pair.values
    left_id  = left.id
    right_id = right.id

    # remove pairs containing one of the items
    pairs.delete_if { |p| p.has?(left) || p.has?(right) }

    # merge clusters
    left.merge(right)
    _clusters.delete_if { |c| c.id == right_id }
    _updated_clusters.remove right
    _dropped_clusters.add    right
    _updated_clusters.add    left

    # create new pairs
    _clusters.each do |cluster|
      next if cluster.id == left_id
      pairs << _build_pair(left, cluster, _fence)
    end
  end
  nil
end

#updated_clusters ⇒ Object

after #run, this contains the clusters that were modified and need to be persisted



74
75
76
 
# File 'lib/tsuga/service/aggregator.rb', line 74

def updated_clusters
  _updated_clusters.to_a
end