Class: GitFit::Dedup::Trajectory

Inherits:
Object
  • Object
show all
Defined in:
lib/git_fit/dedup/trajectory.rb

Constant Summary collapse

SAMPLE_RATE =

take every Nth point

10
PROXIMITY_M =

points within 50m count as same

50
DP_EPSILON =

~10m in lat/lng degrees

0.0001
CONTAINED_THRESHOLD =

70% overlap → equivalent/contained

0.7
PARTIAL_THRESHOLD =

30% → partial boundary

0.3
MAX_EXPECTED_COST =

DTW normalization denominator

1000.0
PLACEHOLDER_POLYLINE = 
'gqqrFurkeU??'

Instance Method Summary collapse

Constructor Details

#initialize(db) ⇒ Trajectory

Returns a new instance of Trajectory.



16
17
18
19
 
# File 'lib/git_fit/dedup/trajectory.rb', line 16

def initialize(db)
  @db = db
  @cache = {}
end

Instance Method Details

#containment_relation(traj_a, traj_b, _radius = PROXIMITY_M, threshold = CONTAINED_THRESHOLD) ⇒ Object 



126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/git_fit/dedup/trajectory.rb', line 126

def containment_relation(traj_a, traj_b, _radius = PROXIMITY_M, threshold = CONTAINED_THRESHOLD)
  return nil if traj_a.nil? || traj_b.nil? || traj_a.size < 2 || traj_b.size < 2

  sampled_a = traj_a.each_slice(SAMPLE_RATE).map(&:first)
  sampled_b = traj_b.each_slice(SAMPLE_RATE).map(&:first)
  return nil if sampled_a.empty? || sampled_b.empty?

  a_in_b = sampled_a.count { |p| near(p, sampled_b) } / sampled_a.size.to_f
  b_in_a = sampled_b.count { |p| near(p, sampled_a) } / sampled_b.size.to_f

  if a_in_b >= threshold && b_in_a >= threshold
    :equivalent
  elsif a_in_b >= threshold
    :contained_a
  elsif b_in_a >= threshold
    :contained_b
  elsif a_in_b > PARTIAL_THRESHOLD || b_in_a > PARTIAL_THRESHOLD
    :partial
  elsif a_in_b > 0 || b_in_a > 0
    :cross
  else
    :disjoint
  end
end

#douglas_peucker(points, epsilon = DP_EPSILON) ⇒ Object 



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
 
# File 'lib/git_fit/dedup/trajectory.rb', line 39

def douglas_peucker(points, epsilon = DP_EPSILON)
  return points if points.size <= 2

  coords = points.map { |p| point_coordinates(p) }.compact
  return points if coords.size <= 2

  stack = [[0, coords.size - 1]]
  keep = Set.new([0, coords.size - 1])

  while stack.any?
    start_idx, end_idx = stack.pop
    dmax = 0.0
    idx = start_idx

    ((start_idx + 1)...end_idx).each do |i|
      d = perpendicular_distance(coords[i], coords[start_idx], coords[end_idx])
      if d > dmax
        dmax = d
        idx = i
      end
    end

    next unless dmax > epsilon
    keep.add(idx)
    stack.push([start_idx, idx])
    stack.push([idx, end_idx])
  end

  coords.select.with_index { |_, i| keep.include?(i) }
end

#dtw_similarity(traj_a, traj_b) ⇒ Object 



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/git_fit/dedup/trajectory.rb', line 70

def dtw_similarity(traj_a, traj_b)
  return nil if traj_a.nil? || traj_b.nil? || traj_a.size < 2 || traj_b.size < 2

  a = traj_a.map { |p| point_coordinates(p) }.compact
  b = traj_b.map { |p| point_coordinates(p) }.compact
  return nil if a.size < 2 || b.size < 2

  n = a.size
  m = b.size
  dtw = Array.new(n + 1) { Array.new(m + 1, Float::INFINITY) }
  dtw[0][0] = 0

  (1..n).each do |i|
    (1..m).each do |j|
      cost = haversine(a[i - 1][0], a[i - 1][1], b[j - 1][0], b[j - 1][1])
      dtw[i][j] = cost + [dtw[i - 1][j], dtw[i][j - 1], dtw[i - 1][j - 1]].min
    end
  end

  avg_cost = dtw[n][m] / [n, m].max
  [1.0 - avg_cost / MAX_EXPECTED_COST, 0.0].max
end

#duplicate?(run_id_a, run_id_b) ⇒ Boolean

Returns:

  • (Boolean) 


21
22
23
24
25
26
27
28
29
30
31
32
33
 
# File 'lib/git_fit/dedup/trajectory.rb', line 21

def duplicate?(run_id_a, run_id_b)
  pts_a = cached_points(run_id_a)
  pts_b = cached_points(run_id_b)
  return nil unless pts_a && pts_b && pts_a.size >= 2 && pts_b.size >= 2

  shorter = pts_a.size <= pts_b.size ? pts_a : pts_b
  longer = pts_a.size > pts_b.size ? pts_a : pts_b

  sampled = shorter.each_slice(SAMPLE_RATE).map(&:first)
  matches = sampled.count { |pt| near(pt, longer) }
  ratio = matches.to_f / sampled.size
  ratio >= 0.3
end

#hausdorff_distance(traj_a, traj_b) ⇒ Object 



93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/git_fit/dedup/trajectory.rb', line 93

def hausdorff_distance(traj_a, traj_b)
  return nil if traj_a.nil? || traj_b.nil? || traj_a.size < 2 || traj_b.size < 2

  a_coords = traj_a.map { |p| point_coordinates(p) }.compact
  b_coords = traj_b.map { |p| point_coordinates(p) }.compact
  return nil if a_coords.size < 2 || b_coords.size < 2

  max_min_a = a_coords.map { |p| min_distance_to_set(p, b_coords) }.max || 0.0
  max_min_b = b_coords.map { |p| min_distance_to_set(p, a_coords) }.max || 0.0
  [max_min_a, max_min_b].max
end

#normalized_hausdorff_score(traj_a, traj_b) ⇒ Object 



105
106
107
108
109
 
# File 'lib/git_fit/dedup/trajectory.rb', line 105

def normalized_hausdorff_score(traj_a, traj_b)
  dist = hausdorff_distance(traj_a, traj_b)
  return nil if dist.nil?
  [1.0 - dist / 2000.0, 0.0].max
end

#overlap_score(traj_a, traj_b, _radius = PROXIMITY_M) ⇒ Object 



111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/git_fit/dedup/trajectory.rb', line 111

def overlap_score(traj_a, traj_b, _radius = PROXIMITY_M)
  return nil if traj_a.nil? || traj_b.nil? || traj_a.size < 2 || traj_b.size < 2

  sampled_a = traj_a.each_slice(SAMPLE_RATE).map(&:first)
  sampled_b = traj_b.each_slice(SAMPLE_RATE).map(&:first)
  return nil if sampled_a.empty? || sampled_b.empty?

  a_in_b = sampled_a.count { |p| near(p, sampled_b) }
  b_in_a = sampled_b.count { |p| near(p, sampled_a) }

  ratio_a = a_in_b.to_f / sampled_a.size
  ratio_b = b_in_a.to_f / sampled_b.size
  (ratio_a + ratio_b) / 2.0
end

#points(run_id) ⇒ Object 



35
36
37
 
# File 'lib/git_fit/dedup/trajectory.rb', line 35

def points(run_id)
  cached_points(run_id)
end