折叠数组中连续的“相同”元素

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

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

\n\n

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

\n\n

与上面问题中显示的图表中的点一起使用：

\n\n

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

\n\n

我们得到了很好的结果：

\n\n

\n