项目第二十八天 iOS-Chart源码分析-2 Filter

02 August 2015

结构

  • 动画 : Animation/
  • 图表 : Charts/
  • 组件 : Components/
  • 数据 : Data/
  • 过滤 : Filters/
  • 高亮 : Highlight/
  • 渲染 : Renderers/
  • 工具 : Utils/

Filters 过滤器

过滤器 Filters/

基类： └── ChartDataBaseFilter.swift 逼近器： ├── ChartDataApproximatorFilter.swift

名词解释

approximator

n. 接近者，近似者, 逼近器

Douglas-Peucker-Algorithm

道格拉斯-普克算法

道格拉斯-普克算法(Douglas–Peucker algorithm，亦称为拉默-道格拉斯-普克算法、迭代适应点算法、分裂与合并算法)是将曲线近似表示为一系列点，并减少点的数量的一种算法。该算法的原始类型分别由乌尔斯·拉默（Urs Ramer）于1972年以及大卫·道格拉斯（David Douglas）和托马斯·普克（Thomas Peucker）于1973年提出[1]，并在之后的数十年中由其他学者予以完善[2]。

https://zh.wikipedia.org/wiki/%E9%81%93%E6%A0%BC%E6%8B%89%E6%96%AF-%E6%99%AE%E5%85%8B%E7%AE%97%E6%B3%95

https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

tolerance

公差(gong chai)

几何参数的公差有尺寸公差、形状公差、位置公差等。

①尺寸公差。指允许尺寸的变动量，等于最大极限尺寸与最小极限尺寸代数差的绝对值。
②形状公差。指单一实际要素的形状所允许的变动全量，包括直线度、平面度、圆度、圆柱度、线轮廓度和面轮廓度6个项目。
③位置公差。指关联实际要素的位置对基准所允许的变动全量，它限制零件的两个或两个以上的点、线、面之间的相互位置关系，包括平行度、垂直度、倾斜度、同轴度、对称度、位置度、圆跳动和全跳动8个项目。公差表示了零件的制造精度要求，反映了其加工难易程度。

ChartDataApproximatorFilter

枚举

@objc
public enum ApproximatorType: Int
{
    case None            // 无
    case RamerDouglasPeucker // 拉默-道格拉斯-普克
}

属性

/// the type of filtering algorithm to use
/// 逼近算法类型
public var type = ApproximatorType.None



/// the tolerance to be filtered with
/// When using the Douglas-Peucker-Algorithm, the tolerance is an angle in degrees, that will trigger the filtering
/// 公差的作用
/// 当使用 道格拉斯-普克 算法时，tolerance 作为一个角度,触发逼近
public var tolerance = Double(0.0)



/// 绽放比例
public var scaleRatio = Double(1.0)
/// delta 比例
public var deltaRatio = Double(1.0)

构造方法

public override init()
{
    super.init()
}



/// Initializes the approximator with the given type and tolerance. 
/// If toleranec <= 0, no filtering will be done.
/// 根据tolerance初始化逼近器
/// 如果 tolerance <= 0, 逼近完成
public init(type: ApproximatorType, tolerance: Double)
{
    super.init()



<span class="nf">setup</span><span class="p">(</span><span class="n">type</span><span class="p">,</span> <span class="nv">tolerance</span><span class="p">:</span> <span class="n">tolerance</span><span class="p">)</span>




}

成员方法

/// Sets type and tolerance.
/// If tolerance <= 0, no filtering will be done.
/// 如果 公差 <= 0, 不再逼近
public func setup(type: ApproximatorType, tolerance: Double)
{
    self.type = type
    self.tolerance = tolerance
}



/// Sets the ratios for x- and y-axis, as well as the ratio of the scale levels
/// 设置xy轴的比例，也就是缩放比例
public func setRatios(deltaRatio: Double, scaleRatio: Double)
{
    self.deltaRatio = deltaRatio
    self.scaleRatio = scaleRatio
}



/// Filters according to type. Uses the pre set set tolerance
/// 逼近器取决于 type, 根据之前的set设置tolerance
///
/// :param: points the points to filter
/// 参数： 将要被逼近的点
public override func filter(points: [ChartDataEntry]) -> [ChartDataEntry]
{
    return filter(points, tolerance: tolerance)
}



/// Filters according to type.
///
/// :param: points the points to filter
/// :param: tolerance the angle in degrees that will trigger the filtering
public func filter(points: [ChartDataEntry], tolerance: Double) -> [ChartDataEntry]
{
    if (tolerance <= 0)
    {
        return points
    }



<span class="k">switch</span> <span class="p">(</span><span class="n">type</span><span class="p">)</span>
<span class="p">{</span>
    <span class="k">case</span> <span class="o">.</span><span class="kt">RamerDouglasPeucker</span><span class="p">:</span>
        <span class="k">return</span> <span class="nf">reduceWithDouglasPeuker</span><span class="p">(</span><span class="n">points</span><span class="p">,</span> <span class="nv">epsilon</span><span class="p">:</span> <span class="n">tolerance</span><span class="p">)</span>
    <span class="k">case</span> <span class="o">.</span><span class="kt">None</span><span class="p">:</span>
        <span class="k">return</span> <span class="n">points</span>
<span class="p">}</span>




}



/// uses the douglas peuker algorithm to reduce the given arraylist of entries
/// 使用douglas peuker algorithm 归纳（降低）给定的 实体
private func reduceWithDouglasPeuker(entries: [ChartDataEntry], epsilon: Double) -> [ChartDataEntry]
{
    // if a shape has 2 or less points it cannot be reduced
    // 如果少于2个点，将不能归纳
    if (epsilon <= 0 || entries.count < 3)
    {
        return entries
    }



<span class="k">var</span> <span class="nv">keep</span> <span class="o">=</span> <span class="p">[</span><span class="kt">Bool</span><span class="p">](</span><span class="nv">count</span><span class="p">:</span> <span class="n">entries</span><span class="o">.</span><span class="n">count</span><span class="p">,</span> <span class="nv">repeatedValue</span><span class="p">:</span> <span class="kc">false</span><span class="p">)</span>

<span class="c1">// first and last always stay</span>
<span class="c1">// 保留头和尾</span>
<span class="n">keep</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="kc">true</span>
<span class="n">keep</span><span class="p">[</span><span class="n">entries</span><span class="o">.</span><span class="n">count</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="kc">true</span>

<span class="c1">// first and last entry are entry point to recursion</span>
<span class="c1">// 头和尾作为递归入口</span>
<span class="nf">algorithmDouglasPeucker</span><span class="p">(</span><span class="n">entries</span><span class="p">,</span> <span class="nv">epsilon</span><span class="p">:</span> <span class="n">epsilon</span><span class="p">,</span> <span class="nv">start</span><span class="p">:</span> <span class="mi">0</span><span class="p">,</span> <span class="nv">end</span><span class="p">:</span> <span class="n">entries</span><span class="o">.</span><span class="n">count</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="nv">keep</span><span class="p">:</span> <span class="o">&amp;</span><span class="n">keep</span><span class="p">)</span>

<span class="c1">// create a new array with series, only take the kept ones</span>
<span class="k">var</span> <span class="nv">reducedEntries</span> <span class="o">=</span> <span class="p">[</span><span class="kt">ChartDataEntry</span><span class="p">]()</span>
<span class="k">for</span> <span class="p">(</span><span class="k">var</span> <span class="nv">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">entries</span><span class="o">.</span><span class="n">count</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">keep</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
    <span class="p">{</span>
        <span class="k">let</span> <span class="nv">curEntry</span> <span class="o">=</span> <span class="n">entries</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
        <span class="n">reducedEntries</span><span class="o">.</span><span class="nf">append</span><span class="p">(</span><span class="kt">ChartDataEntry</span><span class="p">(</span><span class="nv">value</span><span class="p">:</span> <span class="n">curEntry</span><span class="o">.</span><span class="n">value</span><span class="p">,</span> <span class="nv">xIndex</span><span class="p">:</span> <span class="n">curEntry</span><span class="o">.</span><span class="n">xIndex</span><span class="p">))</span>
    <span class="p">}</span>
<span class="p">}</span>

<span class="k">return</span> <span class="n">reducedEntries</span>




}



/// apply the Douglas-Peucker-Reduction to an ArrayList of Entry with a given epsilon (tolerance)
///
/// :param: entries
/// :param: epsilon as y-value
/// :param: start
/// :param: end
private func algorithmDouglasPeucker(entries: [ChartDataEntry], epsilon: Double, start: Int, end: Int, inout keep: [Bool])
{
    if (end <= start + 1)
    {
        // recursion finished
        return
    }



<span class="c1">// find the greatest distance between start and endpoint</span>
<span class="k">var</span> <span class="nv">maxDistIndex</span> <span class="o">=</span> <span class="kt">Int</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="k">var</span> <span class="nv">distMax</span> <span class="o">=</span> <span class="kt">Double</span><span class="p">(</span><span class="mf">0.0</span><span class="p">)</span>

<span class="k">var</span> <span class="nv">firstEntry</span> <span class="o">=</span> <span class="n">entries</span><span class="p">[</span><span class="n">start</span><span class="p">]</span>
<span class="k">var</span> <span class="nv">lastEntry</span> <span class="o">=</span> <span class="n">entries</span><span class="p">[</span><span class="n">end</span><span class="p">]</span>

<span class="k">for</span> <span class="p">(</span><span class="k">var</span> <span class="nv">i</span> <span class="o">=</span> <span class="n">start</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">end</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
    <span class="k">var</span> <span class="nv">dist</span> <span class="o">=</span> <span class="nf">calcAngleBetweenLines</span><span class="p">(</span><span class="n">firstEntry</span><span class="p">,</span> <span class="nv">end1</span><span class="p">:</span> <span class="n">lastEntry</span><span class="p">,</span> <span class="nv">start2</span><span class="p">:</span> <span class="n">firstEntry</span><span class="p">,</span> <span class="nv">end2</span><span class="p">:</span> <span class="n">entries</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>

    <span class="c1">// keep the point with the greatest distance</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">dist</span> <span class="o">&gt;</span> <span class="n">distMax</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">distMax</span> <span class="o">=</span> <span class="n">dist</span>
        <span class="n">maxDistIndex</span> <span class="o">=</span> <span class="n">i</span>
    <span class="p">}</span>
<span class="p">}</span>

<span class="k">if</span> <span class="p">(</span><span class="n">distMax</span> <span class="o">&gt;</span> <span class="n">epsilon</span><span class="p">)</span>
<span class="p">{</span>
    <span class="c1">// keep max dist point</span>
    <span class="n">keep</span><span class="p">[</span><span class="n">maxDistIndex</span><span class="p">]</span> <span class="o">=</span> <span class="kc">true</span>

    <span class="c1">// recursive call</span>
    <span class="nf">algorithmDouglasPeucker</span><span class="p">(</span><span class="n">entries</span><span class="p">,</span> <span class="nv">epsilon</span><span class="p">:</span> <span class="n">epsilon</span><span class="p">,</span> <span class="nv">start</span><span class="p">:</span> <span class="n">start</span><span class="p">,</span> <span class="nv">end</span><span class="p">:</span> <span class="n">maxDistIndex</span><span class="p">,</span> <span class="nv">keep</span><span class="p">:</span> <span class="o">&amp;</span><span class="n">keep</span><span class="p">)</span>
    <span class="nf">algorithmDouglasPeucker</span><span class="p">(</span><span class="n">entries</span><span class="p">,</span> <span class="nv">epsilon</span><span class="p">:</span> <span class="n">epsilon</span><span class="p">,</span> <span class="nv">start</span><span class="p">:</span> <span class="n">maxDistIndex</span><span class="p">,</span> <span class="nv">end</span><span class="p">:</span> <span class="n">end</span><span class="p">,</span> <span class="nv">keep</span><span class="p">:</span> <span class="o">&amp;</span><span class="n">keep</span><span class="p">)</span>
<span class="p">}</span> <span class="c1">// else don't keep the point...</span>




}



/// calculate the distance between a line between two entries and an entry (point)
///
/// :param: startEntry line startpoint
/// :param: endEntry line endpoint
/// :param: entryPoint the point to which the distance is measured from the line
private func calcPointToLineDistance(startEntry: ChartDataEntry, endEntry: ChartDataEntry, entryPoint: ChartDataEntry) -> Double
{
    var xDiffEndStart = Double(endEntry.xIndex) - Double(startEntry.xIndex)
    var xDiffEntryStart = Double(entryPoint.xIndex) - Double(startEntry.xIndex)



<span class="k">var</span> <span class="nv">normalLength</span> <span class="o">=</span> <span class="nf">sqrt</span><span class="p">((</span><span class="n">xDiffEndStart</span><span class="p">)</span>
    <span class="o">*</span> <span class="p">(</span><span class="n">xDiffEndStart</span><span class="p">)</span>
    <span class="o">+</span> <span class="p">(</span><span class="n">endEntry</span><span class="o">.</span><span class="n">value</span> <span class="o">-</span> <span class="n">startEntry</span><span class="o">.</span><span class="n">value</span><span class="p">)</span>
    <span class="o">*</span> <span class="p">(</span><span class="n">endEntry</span><span class="o">.</span><span class="n">value</span> <span class="o">-</span> <span class="n">startEntry</span><span class="o">.</span><span class="n">value</span><span class="p">))</span>

<span class="k">return</span> <span class="kt">Double</span><span class="p">(</span><span class="nf">fabs</span><span class="p">((</span><span class="n">xDiffEntryStart</span><span class="p">)</span>
    <span class="o">*</span> <span class="p">(</span><span class="n">endEntry</span><span class="o">.</span><span class="n">value</span> <span class="o">-</span> <span class="n">startEntry</span><span class="o">.</span><span class="n">value</span><span class="p">)</span>
    <span class="o">-</span> <span class="p">(</span><span class="n">entryPoint</span><span class="o">.</span><span class="n">value</span> <span class="o">-</span> <span class="n">startEntry</span><span class="o">.</span><span class="n">value</span><span class="p">)</span>
    <span class="o">*</span> <span class="p">(</span><span class="n">xDiffEndStart</span><span class="p">)))</span> <span class="o">/</span> <span class="kt">Double</span><span class="p">(</span><span class="n">normalLength</span><span class="p">)</span>




}



/// Calculates the angle between two given lines. The provided entries mark the starting and end points of the lines.
private func calcAngleBetweenLines(start1: ChartDataEntry, end1: ChartDataEntry, start2: ChartDataEntry, end2: ChartDataEntry) -> Double
{
    var angle1 = calcAngleWithRatios(start1, p2: end1)
    var angle2 = calcAngleWithRatios(start2, p2: end2)



<span class="k">return</span> <span class="nf">fabs</span><span class="p">(</span><span class="n">angle1</span> <span class="o">-</span> <span class="n">angle2</span><span class="p">)</span>




}



/// calculates the angle between two entries (points) in the chart taking ratios into consideration
private func calcAngleWithRatios(p1: ChartDataEntry, p2: ChartDataEntry) -> Double
{
    var dx = Double(p2.xIndex)  Double(deltaRatio) - Double(p1.xIndex)  Double(deltaRatio)
    var dy = p2.value  scaleRatio - p1.value  scaleRatio
    return atan2(Double(dy), dx) * ChartUtils.Math.RAD2DEG
}



// calculates the angle between two entries (points) in the chart
private func calcAngle(p1: ChartDataEntry, p2: ChartDataEntry) -> Double
{
    var dx = p2.xIndex - p1.xIndex
    var dy = p2.value - p1.value
    return atan2(Double(dy), Double(dx)) * ChartUtils.Math.RAD2DEG
}

blog comments powered by Disqus