Ближайшая точка на графике как найти

asked Jan 22, 2013 at 9:34

To find the nearest point in a set of unordered points, you have to iterate through them all and keep track of the minimum distance. This has a time complexity of O(n).

You could significantly improve this by maintaining the points in a more organized data structure (such as an R-tree). There are third-party libraries available if you’d rather not implement your own. Many databases already support the R-tree for spatial indices.

If you really want to only search for the point with the nearest X-coordinate, this could be further simplified by storing the points in a sorted collection (such as a SortedList<TKey, TValue>) and performing a binary search (which SortedList<TKey, TValue>.IndexOfKey already implements).

answered Jan 22, 2013 at 19:58

/*My Fuzzy Binary Search*/
private int FindNearestId(System.Windows.Forms.DataVisualization.Charting.DataPointCollection p, uint ClickedX)
{
    int ret = 0;
    int low = 0;
    int high = p.Count - 1;
    bool bLoop = true;

    while (bLoop)
    {
        ret = (low + high) / 2;
        switch (FindNearestId_Match(p, ClickedX, ret))
        {
        case 0:
            high = ret+1;
            break;
        case 1:
            bLoop = false;
            break;
        case 2:
            low = ret-1;
            break;
        }
    }

    return ret+1;
}

private int FindNearestId_Match(System.Windows.Forms.DataVisualization.Charting.DataPointCollection p, uint ClickedX, int id)
{
    uint id0 = Convert.ToUInt32(p[id].XValue);
    uint id1 = Convert.ToUInt32(p[id+1].XValue);

    if ( (id0 <= ClickedX) && (ClickedX < id1) )
    {
        return 1;
    }
    else if ((id0 < ClickedX) && (ClickedX > id1))
    {
        return 2;
    }
    else
    {
        return 0;
    }
}

answered Jan 22, 2013 at 12:04

Soultion can be more clear.
( as above you should use log complexity for accessing item )

double x-values solution:

double FindNearestPointYValueInSeries( System::Windows::Forms::DataVisualization::Charting::Series ^pxSeries, double dSearchedPosition )
{
    int i_min = 0;
    int i_max = pxSeries->Points->Count - 1;
    int i_mean = 0;
    double d ;

    if ( i_max < 0 ) // not defined - minimum one point required
        return Double::NaN;

    while ( i_min <= i_max )
    {
        i_mean = (i_max + i_min ) / 2; // index of compared value in series
        d = pxSeries->Points[ i_mean ]->XValue; // compared value 

        if ( d > dSearchedPosition ) // greater - search in right part
            i_max = i_mean - 1;
        else if ( d < dSearchedPosition ) // lower - search in left part
            i_min = i_mean + 1;
        else // equal ?
            return d;
    }

    // delta is dSearchedPosition - pxSeries->Points[ i_mean ]->YValues[0]

    // get Y value ( on index 0 ) 
    return pxSeries->Points[ i_mean ]->YValues[0];
}

answered Nov 26, 2014 at 16:26

дежурный