Алгоритм попадания точки в кривую

#c_sharp #алгоритм

                    
Есть класс для отрисовки кривой:

class Curve
{
    // Набор точек.
    public List Points {get; set;}

    // Толщина кривой.
    public int Thinkness {get; set;}

    public void Draw(Graphics g)
    {
        using (var pen = new Pen(Color.Black, Thinkness))
        {
            g.DrawCurve(pen, Points);
        }
    }
}


Отрисовка выполняется методом Graphics.DrawCurve. Нужно добавить метод, который будет
определять, принадлежит ли произвольная точка этой кривой:

public bool Contains(Point pt);


Кто-нибудь может подсказать алгоритм, с помощью которого можно решить данную задачу?
Может быть, каким-то образом можно использовать Matrix или сам Graphics?
    

Ответы

Ответ 1

Придумал следующее решение.
В методе Draw рисуем не закругление (DrawCurve), а Path (DrawPath). Способ получения
Path и пера выносим в отдельные методы. После этого используем метод IsOutlineVisible
для получения информации о вхождении точки в Path.

class Curve
{
    // Набор точек.
    public List Points {get; set;}

    // Толщина кривой.
    public int Thinkness {get; set;}

    private GraphicsPath GetPath()
    {
        var path = new GraphicsPath();
        path.AddCurve(Points.ToArray());
        return path;
    }

    private Pen GetPen()
    {
        return new Pen(Color.Black, Thinkness);
    }

    public void Draw(Graphics g)
    {
        using (var pen = GetPen())
        using (var path = GetPath())
        {
            g.DrawPath(pen, path);
        }
    }

    public bool Contains(Point p)
    {
        using (var pen = GetPen())
        using (var path = GetPath())
        {
            return path.IsOutlineVisible(p, pen);
        }
    }
}


Ответ 2

DrawCurve использует кубический сплайн, который задается параметрически как полином
третьей степени с векторами в качестве коэффициентов. Если есть опыт решения кубических
уравнений - можно попробовать сначала восстановить формулу, а потом проверять точку
по получившейся системе из двух кубических уравнений.

Если желания лезть в математику нет - то проще всего нарисовать где-нибудь эту линию,
после чего просто проверять цвет пикселя.


Ответ 3

Нам нужны по идее две вещи: проекция точки на прямую и расстояние от точки до прямой.

class Line
{
    Point start;
    UnitVector direction;
}

Point projectCoord(Point x, Line l)
{
    return Tools.DotProduct(x - line.start, line.direction);
}

Point projection(Point x, Line l)
{
    return line.Start + line.Direction * projectCoord(x, line);
}

double signedDistance(Point p, line l)
{
    if (p == line.Start) return null;
    return Tools.CrossProduct(p - line.Start, line.direction);
}


Имея эти методы, всё по идее просто:

class Segment
{
    Line Line;
    double StartCoord, EndCoord;
}

bool belongs(Point p, Segment s, double width)
{
    return 
        IsBetween(projectCoord(p, s.Line), s.StartCoord, s.EndCoord)) &&
        Math.Abs(signedDistance(p, s.Line)) < width;
}


Вспомогательные функции:

// скалярное произведение
double DotProduct(Vector v1, Vector v2)
{
    return v1.x * v2.x + v1.y * v2.y;
}

// векторное произведение
double CrossProduct(Vector v1, Vector v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}


Ну и точка попадает в ломаную линию, если она попадает хотя бы в одну из её частей.