Блог

Главная - Вопросы по программированию - Проверка, находятся ли 3 точки в одной строке

Проверка, находятся ли 3 точки в одной строке

#python #numpy

#псевдокод

Вопрос:

Я хочу знать фрагмент кода, который действительно может сказать мне, находятся ли 3 точки в 2D-пространстве на одной строке или нет. Псевдокода также достаточно, но Python лучше.

Комментарии:

1. Как определяется ваша строка? Функция на 2d плоскости?

2. Что именно вам дано? Три точки? или три точки и строка?

Ответ №1:

Вы можете проверить, равна ли площадь треугольника ABC 0:

 [ Ax * (By - Cy)   Bx * (Cy - Ay)   Cx * (Ay - By) ] / 2

Конечно, на самом деле вам не нужно делить на 2.

Комментарии:

1. Это намного лучше, потому что нет риска деления на 0.

2. Просто чтобы указать на что-то… Это математически эквивалентно ответу @dcp выше (если вы игнорируете /2 ), но проверка, равна ли область 0, упрощает добавление допуска … (т. Е. stuff < err_tolerance Вместо stuff1 == stuff2 того, как @dcp делает выше)

3. 1 математически то же самое, но концепция более простая / визуальная / прямая (мне это нравится).

4. @Hossein: Вы спрашиваете об абсолютном значении или о знаке? С вашими точками и моей формулой я получаю -510. Знак означает, что вы выбрали определенный порядок точек. Вы можете поменять местами A с C или B, и вы получите положительную область, даже если это один и тот же треугольник.

5. @Joe Kington: (1) Вам нужно сделать -терпимость <вещи < терпимость. (2) формула @florin требует 3 умножения и 5 сложений / вычитаний, чтобы получить результат «должно быть нулевым». формула @dcp, скорректированная путем изменения == на - , требует 2 кратных и 5 вычитаний, чтобы получить результат «должно быть нулевым». Я бы поставил галочку @dcp, а не @florin.

Ответ №2:

Это C , но вы можете адаптировать его к python:

 bool collinear(int x1, int y1, int x2, int y2, int x3, int y3) {
  return (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2);
}

По сути, мы проверяем, совпадают ли наклоны между точкой 1 и точкой 2, а также точкой 1 и точкой 3. Наклон — это изменение y, деленное на изменение x, поэтому мы имеем:

 y1 - y2     y1 - y3
-------  =  --------
x1 - x2     x1 - x3

Перекрестное умножение дает (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2) ;

Обратите внимание, что если вы используете удвоения, вы можете сверить их с эпсилоном:

 bool collinear(double x1, double y1, double x2, double y2, double x3, double y3) {
  return fabs((y1 - y2) * (x1 - x3) - (y1 - y3) * (x1 - x2)) <= 1e-9;
}

Комментарии:

1. @dtb — я добавил объяснение, дайте мне знать, если у вас все еще есть вопросы.

2. хороший трюк. Однако проверка чисел с плавающей запятой на равенство небезопасна. Вы можете проверить абсолютную разницу по отношению к заранее определенному порогу, который зависит от разрешения (чувствительности), которого вы хотите достичь

3. Разве один наклон не может быть положительным, а один отрицательным? Я думаю, вам следует сравнить их абсолютное значение.

4. @dtb — x1==x2 работает нормально, рассмотрим следующие случаи: collinear(-2,0, -2,1, -1,1) возвращает false , а collinear(-2,0, -2,1, -2,2) возвращает true . Я думаю, что угловые случаи закрыты, дайте мне знать, если вы не согласны.

5. Это требует меньше вычислений, чем ответ @florin, даже если он эквивалентен (поэтому я голосую за него).

Ответ №3:

y - y0 = a(x-x0) (1) в то время a = (y1 - y0)/(x1 - x0) как и A(x0, y0) B(x1, y1) C(x2, y2) . Посмотрите, соответствует ли C statistifies (1) . Вы просто заменяете соответствующие значения.

Подробные сведения

Ответ №4:

Прочитайте это и используйте его, чтобы найти уравнение линии через первые две точки. Следуйте инструкциям, чтобы найти m и b . Затем для вашей третьей точки вычислите mx b - y . Если результат равен нулю, третья точка находится на той же строке, что и первые две.

Ответ №5:

Правило 1: В любом линейном 2d-пространстве две точки всегда находятся на одной строке.

Возьмите 2 точки и постройте уравнение, представляющее линию через них. Затем проверьте, находится ли третья точка также в этой строке.

Удачи.