Как я могу определить, принадлежит ли точка определенной линии?

Question

Как узнать, принадлежит ли точка определенной линии?

Примеры приветствуются, если это возможно.

Answer 1

В простейшей форме просто вставьте координаты в линейное уравнение и проверьте равенство.

Дано:

Point p (X=4, Y=5)
Line l (Slope=1, YIntersect=1)

Подключите X и Y:

   Y = Slope * X + YIntersect
=> 5 = 1 * 4 + 1
=> 5 = 5

Так что да, точка на линии.

Если ваши линии представлены в форме (X1, Y1), (X2, Y2), то вы можете рассчитать наклон с помощью:

 Slope = (y1 - y2) / (x1-x2)

А затем получите Y-пересечение с этим:

 YIntersect = - Slope * X1 + Y1;

Редактировать: я исправил Y-пересечение (которое было X1 / Y1 ...)

Вам нужно проверить, что x1 - x2 не 0. Если это так, то проверка, находится ли точка на линии, является простой задачей проверки, равно ли значение Y в вашей точке либо x1, либо x2. Также убедитесь, что X точки не является «x1» или «x2».

Answer 2

Я только что написал функцию, которая обрабатывает несколько дополнительных требований, поскольку я использую эту проверку в приложении для рисования:

• Нечеткость - должно быть место для ошибки, так как функция используется для выбора линий, щелкая по ним.
• Строка получила EndPoint и StartPoint, а не бесконечные строки.
• Обрабатывать прямые вертикальные и горизонтальные линии, (x2 - x1) == 0 приводит к делению на ноль в других ответах.

private const double SELECTION_FUZZINESS = 3;

internal override bool ContainsPoint(Point point)
{
    LineGeometry lineGeo = geometry as LineGeometry;
    Point leftPoint;
    Point rightPoint;

    // Normalize start/end to left right to make the offset calc simpler.
    if (lineGeo.StartPoint.X <= lineGeo.EndPoint.X)
    {
        leftPoint   = lineGeo.StartPoint;
        rightPoint  = lineGeo.EndPoint;
    }
    else
    {
        leftPoint   = lineGeo.EndPoint;
        rightPoint  = lineGeo.StartPoint;
    }

    // If point is out of bounds, no need to do further checks.                  
    if (point.X + SELECTION_FUZZINESS < leftPoint.X || rightPoint.X < point.X - SELECTION_FUZZINESS)
        return false;
    else if (point.Y + SELECTION_FUZZINESS < Math.Min(leftPoint.Y, rightPoint.Y) || Math.Max(leftPoint.Y, rightPoint.Y) < point.Y - SELECTION_FUZZINESS)
        return false;

    double deltaX = rightPoint.X - leftPoint.X;
    double deltaY = rightPoint.Y - leftPoint.Y;

    // If the line is straight, the earlier boundary check is enough to determine that the point is on the line.
    // Also prevents division by zero exceptions.
    if (deltaX == 0 || deltaY == 0) 
        return true;

    double slope        = deltaY / deltaX;
    double offset       = leftPoint.Y - leftPoint.X * slope;
    double calculatedY  = point.X * slope + offset;

    // Check calculated Y matches the points Y coord with some easing.
    bool lineContains = point.Y - SELECTION_FUZZINESS <= calculatedY && calculatedY <= point.Y + SELECTION_FUZZINESS;

    return lineContains;            
}

Answer 3

Лучший способ определить, лежит ли точка R = (rx, ry) на линии, соединяющей точки P = (px, py) и Q = (qx, qy), состоит в том, чтобы проверить, является ли определитель матрицы

{{qx - px, qy - py}, {rx - px, ry - py}},

, а именно (qx - px) * (ry - py) - (qy - py) * (rx - px) близко к 0. Это решение имеет ряд связанных преимуществ перед другими опубликованными: во-первых, оно не требует особого случая для вертикальных линий, во-вторых, он не делится (обычно это медленная операция), в-третьих, он не вызывает плохого поведения с плавающей точкой, когда линия почти, но не совсем вертикальная.

Answer 4

Я думаю, что мистер Патрик Макдональд поставил почти правильный ответ, и это исправление его ответа:

public bool IsOnLine(Point endPoint1, Point endPoint2, Point checkPoint)
{
    return (((double)checkPoint.Y - endPoint1.Y)) / ((double)(checkPoint.X - endPoint1.X))
        == ((double)(endPoint2.Y - endPoint1.Y)) / ((double)(endPoint2.X - endPoint1.X));
}

и, конечно, есть много других правильных ответов, особенно мистер Джош, но я нашел, что это лучший ответ.

Спасибо за evryone.

Answer 5

Даны две точки на линии L0 и L1 и точка для проверки P.

               (L1 - L0) * (P - L0)
n = (P - L0) - --------------------- (L1 - L0)
               (L1 - L0) * (L1 - L0)

Норма вектора n - это расстояние точки P от линии через L0 и L1. Если это расстояние равно нулю или достаточно мало (в случае ошибок округления), точка лежит на прямой.

Символ * обозначает скалярное произведение.

Пример

P = (5, 5)

L0 = (0, 10)
L1 = (20, -10)

L1 - L0 = (20, -20)
P  - L0 = (5, -5)

              (20, -20) * (5, -5)
n = (5, -5) - --------------------- (20, -20)
              (20, -20) * (20, -20)

              200
  = (5, -5) - --- (20, -20)
              800

  = (5, -5) - (5, -5)

  = (0, 0)

Answer 6

y = m * x + c

Это уравнение прямой. х & у - координаты. Каждая линия характеризуется своим наклоном (м) и тем, где она пересекает ось у (с).

Таким образом, учитывая m & c для линии, вы можете определить, находится ли точка (x1, y1) на линии, проверив, выполняется ли уравнение для x = x1 и y = y1

Answer 7

Если у вас есть линия, определенная ее конечными точками

PointF pt1, pt2;

и у вас есть точка, которую вы хотите проверить

PointF checkPoint;

тогда вы можете определить функцию следующим образом:

bool IsOnLine(PointF endPoint1, PointF endPoint2, PointF checkPoint) 
{
    return (checkPoint.Y - endPoint1.Y) / (endPoint2.Y - endPoint1.Y)
        == (checkPoint.X - endPoint1.X) / (endPoint2.X - endPoint1.X);
}

и назовите его следующим образом:

if (IsOnLine(pt1, pt2, checkPoint) {
    // Is on line
}

Вам нужно будет проверить деление на ноль.

Answer 8

2D-линия обычно представлена ​​с использованием уравнения с двумя переменными x, а y здесь является хорошо известным уравнением

Теперь представьте, что ваша линия GDI + нарисована от (0,0) до (100, 100), тогда значение m = (0-100) / (0-100) = 1, таким образом, уравнение для вашей линии - 0 = 1 * (х-0) => у = х

Теперь, когда у нас есть уравнение для рассматриваемой линии, легко проверить, принадлежит ли точка этой линии. Данная точка (x3, y3) принадлежит этой линии, если она удовлетворяет уравнению линии при замене x = x3 и y = y3. Например, точка (10, 10) принадлежит этой строке, поскольку 10 = 10, но (10,12) не принадлежит этой строке, поскольку 12! = 10.

ПРИМЕЧАНИЕ: для вертикальной линии значение наклона (м) бесконечно, но для этого особого случая вы можете использовать уравнение для вертикальной линии непосредственно x = c, где c = x1 = x2.

Хотя я должен сказать, что не уверен, является ли это наиболее эффективным способом сделать это. Я постараюсь найти более эффективный способ, когда у меня будет больше времени.

Надеюсь, это поможет.

Answer 9

Уравнение строки:

y = mx + c

Таким образом, точка (a, b) находится на этой линии, если она удовлетворяет этому уравнению, т.е. b = ma + c

Answer 10

В качестве альтернативы методу slope/y-intercept я выбрал этот подход, используя Math.Atan2:

// as an extension method
public static bool Intersects(this Vector2 v, LineSegment s) {
    //  check from line segment start perspective
    var reference = Math.Atan2(s.Start.Y - s.End.Y, s.Start.X - s.End.X);
    var aTanTest = Math.Atan2(s.Start.Y - v.Y, s.Start.X - v.X);

    //  check from line segment end perspective
    if (reference == aTanTest) {
        reference = Math.Atan2(s.End.Y - s.Start.Y, s.End.X - s.Start.X);
        aTanTest = Math.Atan2(s.End.Y - v.Y, s.End.X - v.X);
    }

    return reference == aTanTest;
}

Первая проверка reference определяет arcTan от начальной точки отрезка линии до его конечной точки. Затем с точки зрения начальной точки мы определяем arcTan для вектора v.

Если эти значения равны, мы проверяем с точки зрения конечной точки.

Простой и обрабатывает горизонтальный, вертикальный и все остальное между ними.