Scatter Charts touch point resolution algorithm is broken (fix included)

[dbquarrel]

• [x ] I've read, understood, and done my best to follow the *CONTRIBUTING guidelines.

What did you do?

I generated a large number of scatter points, and implemented the delegate message to respond to highlighting taps.

- (void)chartValueSelected:(ChartViewBase * __nonnull)chartView
                 entry:(ChartDataEntry * __nonnull )entry
          dataSetIndex:(NSInteger)dataSetIndex
             highlight:(ChartHighlight * __nonnull)highlight

The tap position was obtained by calling back via:

    CGPoint position = [_chartView getPositionWithEntry:entry axis:AxisDependencyLeft];

When points are tapped I ran a popover at the touch position and this came up in the wrong position consistently unless the touch was extremely accurate, which is hard to do on a chart with a lot of datapoints. The current implementation shows this problem becoming exponentially worse with larger numbers of touch points.

This problem is likely present in various other chart types, there are some reports about bubble charts that I saw, and fixes were attempted but people still complain about the problem. It may be the same issue as this, I'm not sure.

What did you expect to happen?

The closest entry in X and Y distance from the touch point should be returned.

What happened instead?

The closest entry in X position is returned regardless of Y position and absolute distance to the touch point.

Visual description is as follows:

Solution

The solution to this is to repair the method

@objc internal func buildHighlights(
    dataSet set: IChartDataSet,
    dataSetIndex: Int,
    xValue: Double,
    rounding: ChartDataSetRounding) -> [Highlight]

And implement a correct search algorithm for the touch point. The key issues are:

1. the method is not handed enough data to correctly calculate the proper entry being tapped
2. the algorithm used is simply not correct as it operates only in the horizontal dimension, so needs to be replaced with a correct calculation using both dimensions

In order to fix (1) it is necessary to go up the call stack and hand down both the X and Y values instead of just the X, and furthermore to forward the touch point so it can be used as an anchor point for the search.

Note:

I am not a Swift programmer and I don't know the language. Furthermore I hate the language and reading it makes my brain scream, so I may have not adopted correct coding habits for this fix. I however tried to walk it out point by point so that at least it's a framework for someone to adopt the fix and correct whatever coding habits are no good. I'm also trying to trim and reduce calculations as much as possible, as i am dealing with large datasets (20,000 to 100,000 points), which reveals a lot of performance issues in the current code base. So I suggest that the cutoffs and method stay in place.

The result of the patch is that the correct highlight is chosen and the delegate gets the correct position of the selected data point when asking back to the chart.

The same touch now generates the correct point regardless of the packing of the data.

Code

This code was implemented as a plugin subclass to ChartHighlighter. You put it in place with:

open class FixedScatterChartView: ScatterChartView
{
    open override func initialize()
    {
        super.initialize()
        self.highlighter = FixedChartHighlighter(chart: self)
    }
}

Dropin subclass that fixes the calculations.

open class FixedChartHighlighter : ChartHighlighter {
    // dbquarrel: changes here are to get the yVal as well as the xVal and pass that down
    // so we can find the closest point in both dimensions
    // dbquarrel: changes here are to add the yValue parameter to check against the data

@objc open override func getHighlights(xValue: Double, x: CGFloat, y: CGFloat) -> [Highlight]
{
    var vals = [Highlight]()
    ////// patch
    // we have to do this again though it was called in the previous function
    // because nobody gave us the yValue and we need this to calculate the min
    // distance from the entry we want to the touch point
    let val = getValsForTouch(x: x, y: y)

    guard let
        data = self.data
        else { return vals }
    
    for i in 0 ..< data.dataSetCount {
        guard let dataSet = data.getDataSetByIndex(i)
            else { continue }
        
        if !dataSet.isHighlightEnabled  {
            continue
        }
        // dbquarrel: pass along the yValue
        let highlights:[Highlight] = buildHighlights(dataSet: dataSet,
                                                     dataSetIndex: i,
                                                     xValue: xValue,
                                                     yValue: Double(val.y), // patch
                                                     touch:CGPoint(x:x,y:y), //patch
                                                     rounding: .closest)
        vals.append(contentsOf: highlights)
    }
    return vals
    }

// dbquarrel: added yValue parameter and touchpoint
@objc internal func buildHighlights(
    dataSet set: IChartDataSet,
    dataSetIndex: Int,
    xValue: Double,
    yValue: Double,
    touch: CGPoint,
    rounding: ChartDataSetRounding) -> [Highlight]
{
    var highlights = [Highlight]()
    
    guard let chart = self.chart as? BarLineScatterCandleBubbleChartDataProvider
        else { return highlights }

    // we don't want to do this because it can be an accident that we lined up
    // below another point and just happened to hit its X value, we need to check
    // vector distance
    //        var entries = set.entriesForXValue(xValue)
    //// The problem:
    // the current implementation simply looks for an X value closest to the touch
    // point without looking to see if the Y value is under or even near the touch
    // point... so in a chart with a lot of data, you will get a seemingly random
    // choice along the Y axis ... the solution to the problem is to estimate the
    // width of a finger, transform it into chart values, and then sample an index
    // range of entries inside this span. Once we have the sample of entries with
    // x values close to the x touch point, we can then search for entry that has
    // the minimum distance to the touch
    guard let dataSet = set as? ChartDataSet else { return highlights }
    let transformer = chart.getTransformer(forAxis:set.axisDependency)

    if let closest = set.entryForXValue(xValue, closestToY: Double.nan, rounding: rounding) {
        // make a box with min and max points over a search radius
        let searchRadius = CGFloat(64) // about the size of a fairly fat finger
        let touchMin = CGPoint(x:touch.x - searchRadius,y:touch.y - searchRadius)
        let touchMax = CGPoint(x:touch.x + searchRadius,y:touch.y + searchRadius)
        // span will give us information in chart coordinates
        let spanMin = transformer.valueForTouchPoint(touchMin)
        let spanMax = transformer.valueForTouchPoint(touchMax)
        
        ///// doing it like this is agnostic toward flipped coordinate systems or
        ///// charts going in reverse order, so will be safe for now
        // minX..maxX will give us a sample range to pull entries
        let minX = Double(min(spanMin.x,spanMax.x))
        let maxX = Double(max(spanMin.x,spanMax.x))
        // minY..maxY will give us cutoffs we can apply to skip square rooting
        // and point transformations, this is our search radius in the Y coord system
        let minY = Double(min(spanMin.y,spanMax.y))
        let maxY = Double(max(spanMin.y,spanMax.y))

        ///// this depends on the data being sorted, which is an assumption made
        ///// elsewhere for things to work right in scatter charts anyway
        let minIndex = dataSet.entryIndex(x:minX,closestToY:Double.nan,rounding:rounding)
        let maxIndex = dataSet.entryIndex(x:maxX,closestToY:Double.nan,rounding:rounding)
        // mark the previous best guess by X approximation as our candidate, we will return
        // this if we can't find a better matching point within the search radius... this
        // is still not ideal, maybe a better approach would be to double the search radius and
        // try again, until there is a result
        var bestX = closest.x
        var bestY = closest.y
        var bestPixel = transformer.pixelForValues(x: bestX, y: bestY)
        // distance in screen coordinates
        var bestDistance = _distance(x1:touch.x,y1:touch.y,x2:bestPixel.x,y2:bestPixel.y)
        // walk through the span and find the shortest distance to the touch
        for i in minIndex...maxIndex {
            if let e = dataSet.entryForIndex(i) {
                // if the y value is outside the search radius we can discard the entry
                // and save running squares and squareroots which are slow operations
                if (e.y >= minY && e.y <= maxY) {
                    // we have to calculate distance in screen co-ordinates because
                    // e.x and e.y can (will) be in different units
                    let test = transformer.pixelForValues(x: e.x, y: e.y)
                    let distance = _distance(x1:touch.x,y1:touch.y,x2:test.x,y2:test.y)
                    if distance < bestDistance {
                        bestDistance = distance
                        bestX = e.x
                        bestY = e.y
                        bestPixel = test
                        print("New best: ", distance, " for {",bestX,bestY,"}\n")
                    }
                }
            }
        }
        // proceed as before
        highlights.append(Highlight(x: bestX, y: bestY, xPx: bestPixel.x, yPx: bestPixel.y, dataSetIndex: dataSetIndex, axis: set.axisDependency))
    }
    return highlights
}

fileprivate func _distance(x1:CGFloat,y1:CGFloat,x2:CGFloat,y2:CGFloat) -> CGFloat {
    let d2 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
    return sqrt(d2)
}
}

[dbquarrel]

I misunderstood the scope of the problem ... thought it was just the highlighter but it's the dataset that is unable to calculate the correct points based on a touch. The dataset doesn't have access to the transformer so it means that the solution is a bit less accurate. So the fix above is only a partial fix and still generates some errors due to the dataset making some broad mistakes about the closest entry to the X and Y datapoints being asked.

Two objects need to be patched, the dataset and chart highlighter.

The method is to use the broken implementation to make a sampling span over a percentage of the X values, then iterate through them to find the closest Y value. Then the highlighter has to be patched to determine if the closest X point is within range to bother highlighting.

These two classes should drop in as fixes with the patched chart view object as above.

A better implementation is possible if the thinking here is applied deeper into the code.

// using this chart view in place of the normal scatter chart will use the patches 
open class FixedScatterChartView: ScatterChartView
{
open override func initialize()
{
    super.initialize()
    self.highlighter = FixedChartHighlighter(chart: self)
}
}

////
/// patch classes to fix incorrect selection of entry data
////
@objc public class FixedScatterChartDataSet : ScatterChartDataSet {
func Log(_ message: String = "", _ path: String = #file, _ function: String = #function) {
    print("\(message)")
}

// the superclass uses the wrong method, we will improve it
open override func entryIndex(
    x xValue: Double,
    closestToY yValue: Double,
    rounding: ChartDataSetRounding) -> Int
{
    // we don't have the transformer so we can't take a zone around the touch point ... we will have to
    // sample around the X values by some percentage of the min-max
    let radiusPercent = Double(0.04)
    let range = self.xMax - self.xMin
    let offset = radiusPercent * range
    let minIndex = max(super.entryIndex(x:xValue - offset, closestToY: yValue, rounding: .closest ), -1)
    let maxIndex = min(super.entryIndex(x:xValue + offset, closestToY: yValue, rounding: .closest ), self.entryCount-1)
    
    var bestDistance = Double.greatestFiniteMagnitude
    var bestIndex = Int(-1)
    for i in minIndex ... maxIndex {
        // we really need to be comparing square root distance... since we do not know in the
        // dataset what the mapping is from our data points to the coordinate system of the chart
        // it means we can't calculate vector distances correctly (X and Y have to be in the same
        // units, and as data points they are not... so all we can do is try to find inside the sample
        // range the closest Y value to our target value and pass that point back
        if let test = self.entryForIndex(i) {
            Log("test:\(test.x),\(test.y)")
            let testDistance = fabs(test.y - yValue)
            if (testDistance < bestDistance) {
                Log("ACCEPT: \(testDistance) < \(bestDistance)")
                bestDistance = testDistance
                bestIndex = i
            } else {
                Log("CUT: \(testDistance) > \(bestDistance)")
            }
        }
    }
    // proceed as before
    Log("DONE:::: bestIndex: \(bestIndex)")
    return bestIndex
}
}

open class FixedChartHighlighter : ChartHighlighter
{
// dbquarrel: changes here are to get the yVal as well as the xVal and pass that down
// so we can find the closest point in both dimensions
// dbquarrel: changes here are to add the yValue parameter to check against the data

@objc open override func getHighlights(xValue: Double, x: CGFloat, y: CGFloat) -> [Highlight]
{
    var vals = [Highlight]()
    ////// patch
    // we have to do this again though it was called in the previous function
    // because nobody gave us the yValue and we need this to calculate the min
    // distance from the entry we want to the touch point
    let val = getValsForTouch(x: x, y: y)
    
    guard let
        data = self.data
        else { return vals }
    
    for i in 0 ..< data.dataSetCount {
        guard let dataSet = data.getDataSetByIndex(i)
            else { continue }
        
        if !dataSet.isHighlightEnabled  {
            continue
        }
        // dbquarrel: pass along the yValue
        let highlights:[Highlight] = buildHighlights(dataSet: dataSet,
                                                     dataSetIndex: i,
                                                     xValue: xValue,
                                                     yValue: Double(val.y), // patch
            rounding: .closest)
        vals.append(contentsOf: highlights)
    }
    
    return vals
}


fileprivate func _pointDistance(p1:CGPoint,p2:CGPoint) -> Double {
    let d2 = (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)
    return Double(sqrt(d2))
}

// dbquarrel: added yValue parameter
@objc internal func buildHighlights(
    dataSet set: IChartDataSet,
    dataSetIndex: Int,
    xValue: Double,
    yValue: Double,
    rounding: ChartDataSetRounding) -> [Highlight]
{
    var highlights = [Highlight]()
    
    guard let chart = self.chart as? BarLineScatterCandleBubbleChartDataProvider
        else { return highlights }
    
    //// The problem:
    // the current implementation simply looks for an X value closest to the touch
    // point without looking to see if the Y value is under or even near the touch
    // point... so in a chart with a lot of data, you will get a seemingly random
    // choice along the Y axis ... 
    
    if let entry = set.entryForXValue(xValue, closestToY: yValue, rounding: .closest ) {
        // check to make sure the entry we are given is within some reasonable touch distance
        let transformer = chart.getTransformer(forAxis:set.axisDependency)
        let bestPixel = transformer.pixelForValues(x: entry.x, y: entry.y)
        let touchPixel = transformer.pixelForValues(x:xValue,y:yValue)
        let distance = _pointDistance(p1:bestPixel,p2:touchPixel)
        let radius = Double(32.0)
        let threshold = _pointDistance(p1:CGPoint(x:0,y:0),p2:CGPoint(x:radius,y:radius))
        if (distance < threshold) {
            highlights.append(Highlight(x: entry.x, y: entry.y, xPx: bestPixel.x, yPx: bestPixel.y, dataSetIndex: dataSetIndex, axis: set.axisDependency))
        }
    }
    return highlights
}
}

[liuxuan30]

it's too long for me to digest. Can you make a short summary? are you able to send us a pull request so we could review?

[dbquarrel]

The short summary is that the code is only checking the X axis to find the closest data point to a touch. That's not valid. You need to check for the closest point on the X and the Y axis both. The patch checks both axes.

The current algorithm simply does a binary search along the X axis. It looks for the closest point in terms of X position and then quits.

So if you have this set of data for your chart:

x=50, y=100
x=51, y=100000000000

If the user touched at x=52, y=100

It's very obvious that the closest point to 52,100 is 50,100.

But since the algorithm is only checking the X values, the point returned as closest is 51, 100000000000.

So: core problem: you are using a one dimensional search to search a two dimensional space. Thus, the result can be correct sometimes, but wrong sometimes. The closer your data is to a linear plot the more accurate the existing algorithm will be.

I neither program in Swift nor do I use git worth a damn so anything I try to put in will just screw up. All I can say is drop those classes into a project and they will fix the issue (except they were for 3.0.4 and you made a bunch of breaking changes again, to 3.3).

If you can understand what the problem is (only checking X values, and assuming that the point with the closest X value is actually closest to the touch point, without considering Y), then either the solution as written or an alternate solution can be imagined.

I will try to explain again visually using a chessboard. Consider this chess position of two queens and a bishop. .

So in this case, if you touch the black queen, and ask me what is the closest white piece to the black queen, the answer is simple. It's the white queen.

Because you need to look at the X and Y positions, and calculate the distance using both positions. then the green vector is shorter than the red vector, thus the white queen is closest. Anyone can answer this question correctly at a glance, but the math is one by calculating simple point distance from 8th grade.

distance = sqrt( (x2-x1)^2 + (y2-y1)^2 )

The closest point will have the minimum distance between the touch and the entry.

The current algorithm is one dimensional so is only considering the X axis. As a result this is what the current algorithm does, only considering X values, takes the green vector and says the white bishop is closer than the white queen.

This is the core algorithmic error. You can design your own algorithm for finding the closest point to a user's touch, but you need to use both X and Y positions to find that closest point.

Your problem: given an array of data points, find the closest point in the array to an arbitrary point T.

Brute force solution:

1. start with min_distance = infinity
2. for each point P in the array
3. --- calculate distance D between P and T
4. --- if D is less than min_distance, set min_point = P, min_distance = D
5. return min_point

If we know the array is sorted, then we can shortcut the search space by sampling only part of the array close to the X position the user touched.

So we can say this is the array of sorted X values, everyone has this, sorted from min to max

minX [----------------------------------------------------------------] maxX

Now the user touched somewhere in the screen, we find the closest entry by means of the X axis to what the user touched. The current algorithm does this, returns it and stops without checking Y values.

minX [------------------X---------------------------------------------] maxX

So we can't stop here and just return X because we are not checking the Y values like in the chessboard.

My approach is to continue, and take a sample of the entries with X values close enough to approximately be within a candidate radius (guessing the user's finger radius is about 32 pixels wide, I use that as a candidate to extract a set of candidate points from the sorted X values):

[---------------xxxXxxx-----------------------------------------]

We know they are within a finger's width in the X axis but we need to calculate the closest point still by individually checking them all for minimum distance. To do that we use the search algorithm above, to brute force search the sample space within the finger radius.

Other solutions are possible. I wanted to work with the existing code as much as possible without rewriting stuff I don't understand, in a language I don't understand (Swift).

The core though is understanding the algorithm that is being used is wrong. Hopefully this explains clearly what is wrong with the algorithm as well as explaining what I am doing to patch the existing algorithm

[pmairoldi]

Closed by #4721