ruby - 折叠数组中连续的 'same' 个元素

Question

目标

给定一个元素数组和确定两个元素是否“相同”的条件，返回一个新数组，其中删除了连续“相同”元素的运行以仅保留端点。例如:

a = [ {k:'a',v:1}, {k:'b',v:1}, {k:'c',v:1},
      {k:'d',v:2}, {k:'e',v:2},
      {k:'f',v:3}, {k:'g',v:3}, {k:'h',v:3}, {k:'i',v:3}, {k:'j',v:3},
      {k:'k',v:2},
      {k:'l',v:4}, {k:'m',v:4}, {k:'n',v:4}, {k:'o',v:4} ]
b = a.collapse_consecutive{ |h| h[:v] }
#=> [ {k:'a',v:1}, {k:'c',v:1},
#=>   {k:'d',v:2}, {k:'e',v:2},
#=>   {k:'f',v:3}, {k:'j',v:3},
#=>   {k:'k',v:2},
#=>   {k:'l',v:4}, {k:'o',v:4} ]

动机

在折线图上绘制 n 个点时，一系列连续的相同值结果对图形没有影响，端点除外。在下图中，黑色样本对最终图形没有影响。我正在存储精细采样的图表，理想情况下希望删除所有不相关的样本。

对于这个问题，我将问题简化为仅删除水平部分上的黑点，因为识别沿着成角度的线性部分落下的点 (a) 更难并且 (b) 更罕见(在我的例子中)。

目前的进展

到目前为止，我想出的最好的解决方案是依赖于数组索引的解决方案:

class Array
  def collapse_consecutive
    select.with_index{ |o,i|
      i==0 || yield(self[i-1])!=yield(o) ||
      !self[i+1] || yield(self[i+1])!=yield(o)
    end
  end
end

这行得通，但在 Ruby 中依赖数组索引通常是“代码味道”:表明有更优雅的实现可用。

Answer 1

这是一个简化任何二维线的通用解决方案，在删除它之前，可以自定义一个角度应该有多大的阈值。假定 X 和 Y 值使用相同的比例显示。

# Assumes that points is an array of two-valued arrays representing
# [x,y] pairs; removes points whose angle is less than the threshold
def simplify_line(points,inflection_threshold_degrees=1)
  points.reject.with_index do |p1,i|
    if i>0 && (p0=points[i-1]) && (p2=points[i+1])
      # http://stackoverflow.com/a/7505937/405017
      p0p1 = (p1[0]-p0[0])**2 + (p1[1]-p0[1])**2
      p2p1 = (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2
      p0p2 = (p2[0]-p0[0])**2 + (p2[1]-p0[1])**2
      angle = Math.acos( (p2p1+p0p1-p0p2) / Math.sqrt(4*p2p1*p0p1) )*180/Math::PI
      (180 - angle).abs < inflection_threshold_degrees
    end
  end
end

与上述问题中显示的图表中的点一起使用:

pts = [ [  0,40],[ 20,80],[ 40,90],[ 60,80],[ 80,80],[100,60],[120,60],
        [140,60],[160,60],[180,60],[200,80],[220,80],[240,80],[260,60],
        [280,40],[300,33],[320,27],[340,20],[360,20] ]

我们得到了很好的结果: