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

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

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

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

Данный:

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-Intersect с этим:

  YIntersect = - Slope * X1 + Y1; 

Изменить: я установил Y-Intersect (который был X1 / Y1 …)

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

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

  • Fuzziness. Должно быть место для ошибки, поскольку функция используется для выбора строк, нажимая на них.
  • Линия получила 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; } 

Наилучший способ определить, находится ли точка 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. Это решение имеет несколько связанных преимуществ над остальными: во-первых, для вертикальных линий не требуется специального случая , во-вторых, он не делит (как правило, медленную операцию), в-третьих, он не вызывает плохое поведение с плавающей запятой, когда линия почти, но не совсем вертикальная.

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

 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)); } 

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

Thankx для evryone.

Учитывая две точки на линии 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) 
 y = m * x + c 

Это уравнение линии. x & y – координаты. Каждая линия характеризуется ее наклоном (m) и где она пересекает ось y (c).

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

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

 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 } 

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

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

y-y1 = (y1-y2) / (x1-x2) (x-x1)

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

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

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

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

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

Уравнение линии:

 y = mx + c 

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

Не могли бы Вы уточнить?

О каком языке программирования вы говорите?

О какой среде вы говорите?

О каких «линиях» вы говорите? Текст? Какой смысл? XY на экране?

В качестве альтернативы методу 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 - vY, s.Start.X - vX); // 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 - vY, s.End.X - vX); } return reference == aTanTest; } 

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

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

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

  • каков самый быстрый способ найти gcd из n чисел?
  • Как найти список возможных слов из матрицы букв
  • Какая целочисленная hash-функция хороша, которая принимает целочисленный хеш-ключ?
  • Пропустить Список против двоичного дерева поиска
  • Какова временная сложность алгоритмов среднего регулярного выражения?
  • Алгоритмы выбора на отсортированной матрице
  • Обмен двумя переменными без использования временной переменной
  • Как вычислить точку на окружности круга?
  • Детали реализации оборудования с плавающей запятой
  • Есть ли алгоритм для смешивания цветов, который работает как смешивание реальных цветов?
  • Почему quicksort лучше, чем mergesort?
  • Давайте будем гением компьютера.