Class: RubyVor::VDDT::Computation

Inherits:
Object
  • Object
show all
Defined in:
lib/ruby_vor/computation.rb,
ext/ruby_vor_c.c

Constant Summary collapse

DIST_PROC = 
lambda{|a,b| a.distance_from(b)}
NO_NEIGHBOR_RESPONSES = 
[:raise, :use_all, :ignore]

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Computation

Create a computation from an existing set of raw data.



10
11
12
13
14
15
16
17
18
19
20
 
# File 'lib/ruby_vor/computation.rb', line 10

def initialize
  @points = []
  
  @voronoi_diagram_raw = []
  @delaunay_triangulation_raw = []
  
  @nn_graph = nil
  @mst = nil

  @no_neighbor_response = :use_all
end

Instance Attribute Details

#delaunay_triangulation_raw ⇒ Object (readonly)

Returns the value of attribute delaunay_triangulation_raw.



4
5
6
 
# File 'lib/ruby_vor/computation.rb', line 4

def delaunay_triangulation_raw
  @delaunay_triangulation_raw
end

#no_neighbor_response ⇒ Object

Returns the value of attribute no_neighbor_response.



4
5
6
 
# File 'lib/ruby_vor/computation.rb', line 4

def no_neighbor_response
  @no_neighbor_response
end

#points ⇒ Object (readonly)

Returns the value of attribute points.



4
5
6
 
# File 'lib/ruby_vor/computation.rb', line 4

def points
  @points
end

#voronoi_diagram_raw ⇒ Object (readonly)

Returns the value of attribute voronoi_diagram_raw.



4
5
6
 
# File 'lib/ruby_vor/computation.rb', line 4

def voronoi_diagram_raw
  @voronoi_diagram_raw
end

Class Method Details

.from_points ⇒ Object

Instance Method Details

#cluster_by_distance(max_distance, dist_proc = DIST_PROC) ⇒ Object

Uses the nearest-neighbors information encapsulated by the Delaunay triangulation as a seed for clustering: We take the edges (there are O(n) of them, because defined by the triangulation and delete any edge above a certain distance.

This method allows the caller to pass in a lambda for customizing distance calculations. For instance, to use a GeoRuby::SimpleFeatures::Point, one would:

> cluster_by_distance(50 lambda{|a,b| a.spherical_distance(b, 3958.754)}) # this rejects edges greater than 50 miles, using spherical distance as a measure



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
67
68
69
70
71
72
73
74
 
# File 'lib/ruby_vor/computation.rb', line 38

def cluster_by_distance(max_distance, dist_proc=DIST_PROC)
  clusters = []
  nodes    = (0..points.length-1).to_a
  visited  = [false] * points.length
  graph    = []
  v = 0
  
  nn_graph.each_with_index do |neighbors,nv|
    graph[nv] = neighbors.select do |neighbor|
      dist_proc[points[nv], points[neighbor]] < max_distance
    end
  end
  
  until nodes.empty?
    v = nodes.pop
    
    next if visited[v]

    cluster = []
    visited[v] = true
    cluster.push(v)

    children = graph[v]
    until children.nil? || children.empty?
      cnode = children.pop
      next if cnode.nil? || visited[cnode]

      visited[cnode] = true
      cluster.push(cnode)
      children.concat(graph[cnode])
    end

    clusters.push(cluster)
  end

  clusters
end

#cluster_by_size(sizes = [], dist_proc = DIST_PROC) ⇒ Object 



76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/ruby_vor/computation.rb', line 76

def cluster_by_size(sizes=[], dist_proc=DIST_PROC)
  # * Take MST, and
  #   1. For n in sizes (taken in descending order), delete the n most expensive edges from MST
  #     * TODO: use a MaxHeap?
  #   2. Determine remaining connectivity using BFS as above?
  #   3. Some other more efficient connectivity test?
  #   4. Return {n1 => cluster, n2 => cluster} for all n.
  
  sized_clusters = sizes.inject({}) {|h,s| h[s] = []; h}
  
  
  mst = minimum_spanning_tree(dist_proc).to_a
  mst.sort!{|a,b|a.last <=> b.last}

  sizes = sizes.sort
  last_size = 0

  while current_size = sizes.shift
    current_size -= 1
    
    # Remove edge count delta
    delta = current_size - last_size
    mst.slice!(-delta,delta)

    graph    = (1..points.length).to_a.map{|v| []}
    visited  = [nil] * points.length
    clusters = []

    mst.each do |edge,weight|
      graph[edge[1]].push(edge[0])
      graph[edge[0]].push(edge[1])
    end

    for node in 0..points.length-1
      next if visited[node]

      cluster = [node]
      visited[node] = true

      neighbors = graph[node]
      while v = neighbors.pop
        next if visited[v]

        cluster.push(v)
        visited[v] = true
        neighbors.concat(graph[v])
      end

      clusters.push(cluster)
    end

    sized_clusters[current_size + 1] = clusters
    last_size = current_size
  end
  
  sized_clusters
end

#minimum_spanning_tree ⇒ Object

#nn_graph ⇒ Object