class Tsuga::Service::Aggregator

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

Constants

DENSITY_BIAS_FACTOR

FIXME: a sensible value would be ~0.4 in theory, but this biasing seems to have little impact. remove?

Attributes

_clusters[R]
_dropped_clusters[R]
_fence[R]
_updated_clusters[R]

Public Class Methods

new(clusters:nil, ratio:nil, fence:nil) click to toggle source
  • 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

# 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

Public Instance Methods

dropped_clusters() click to toggle source

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

# File lib/tsuga/service/aggregator.rb, line 69
def dropped_clusters
  _dropped_clusters.to_a
end
min_distance() click to toggle source

fraction of the diagonal of the fence tile

# File lib/tsuga/service/aggregator.rb, line 79
def min_distance
  @min_distance ||= (_fence.southwest & _fence.northeast) * @min_distance_ratio
end
run() click to toggle source
# 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() click to toggle source

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

# File lib/tsuga/service/aggregator.rb, line 74
def updated_clusters
  _updated_clusters.to_a
end

Private Instance Methods

_build_pair(c1, c2, fence) click to toggle source

factory for pairs, switches between fenced/unfenced and conditionnaly adds density bias

# File lib/tsuga/service/aggregator.rb, line 93
def _build_pair(c1, c2, fence)
  pair = fence.nil? ? Pair.new(c1, c2) : FencedPair.new(c1, c2, fence)

  if DENSITY_BIAS_FACTOR && (@max_density != @min_density)
    # the least dense cluster pairs have a density_bias value close to 0, the densest closer to 1
    density_bias = (c1.density + c2.density - 2 * @min_density) / (2 * (@max_density - @min_density))
    # this makes dense clusters appear closer, and vice-versa
    pair.distance = pair.distance * (1 + DENSITY_BIAS_FACTOR * (1 - density_bias) - 0.5 * DENSITY_BIAS_FACTOR)
  end
  pair
end
_default_fence() click to toggle source
# File lib/tsuga/service/aggregator.rb, line 105
def _default_fence
  return if _clusters.empty?
  Tsuga::Model::Tile.including(_clusters.first, depth:_clusters.first.depth)
end