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

@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()

	setup(type, tolerance: tolerance)
}

/// 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
	}

	switch (type)
	{
		case .RamerDouglasPeucker:
			return reduceWithDouglasPeuker(points, epsilon: tolerance)
		case .None:
			return points
	}
}

/// 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
	}

	var keep = [Bool](count: entries.count, repeatedValue: false)

	// first and last always stay
	// 保留头和尾
	keep[0] = true
	keep[entries.count - 1] = true

	// first and last entry are entry point to recursion
	// 头和尾作为递归入口
	algorithmDouglasPeucker(entries, epsilon: epsilon, start: 0, end: entries.count - 1, keep: &keep)

	// create a new array with series, only take the kept ones
	var reducedEntries = [ChartDataEntry]()
	for (var i = 0; i < entries.count; i++)
	{
		if (keep[i])
		{
			let curEntry = entries[i]
			reducedEntries.append(ChartDataEntry(value: curEntry.value, xIndex: curEntry.xIndex))
		}
	}

	return reducedEntries
}

/// 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
	}

	// find the greatest distance between start and endpoint
	var maxDistIndex = Int(0)
	var distMax = Double(0.0)

	var firstEntry = entries[start]
	var lastEntry = entries[end]

	for (var i = start + 1; i < end; i++)
	{
		var dist = calcAngleBetweenLines(firstEntry, end1: lastEntry, start2: firstEntry, end2: entries[i])

		// keep the point with the greatest distance
		if (dist > distMax)
		{
			distMax = dist
			maxDistIndex = i
		}
	}

	if (distMax > epsilon)
	{
		// keep max dist point
		keep[maxDistIndex] = true

		// recursive call
		algorithmDouglasPeucker(entries, epsilon: epsilon, start: start, end: maxDistIndex, keep: &keep)
		algorithmDouglasPeucker(entries, epsilon: epsilon, start: maxDistIndex, end: end, keep: &keep)
	} // else don't keep the point...
}

/// 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)

	var normalLength = sqrt((xDiffEndStart)
		* (xDiffEndStart)
		+ (endEntry.value - startEntry.value)
		* (endEntry.value - startEntry.value))

	return Double(fabs((xDiffEntryStart)
		* (endEntry.value - startEntry.value)
		- (entryPoint.value - startEntry.value)
		* (xDiffEndStart))) / Double(normalLength)
}

/// 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)

	return fabs(angle1 - angle2)
}

/// 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
}