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

#алгоритм #c

Задаем координаты 4 точек с клавиатуры (x и y).
Как написать условие, которое определяет лежат ли хотя бы три из этих точек на одной
прямой?     

Ответы

Ответ 1

Можете воспользоваться уравнением прямой проходящей через две точки:
(x - x_1) / (x_2 - x1) = (y - y_1) / (y_2 - y_1)

Если, уравнение будет выполнятся для какой либо другой точки - она находится на этой
прямой
UPD:
Собственно для трех точек условие будет выглядеть так:
if ((x_3 - x_1) / (x_2 - x_1) == (y_3 - y_1) / (y_2 - y_1)) /*Точки 1, 2, 3 - лежат
на одной прямой */


Ответ 2

Все правильно кроме знака "==". При задании координат точек мы всегда округляем результат
до точности, предусмотренной системой компьютерной алгебры или языком программирования.
Поэтому на практике крайне редко выполняется подобное равенство. Разве что, если взять
точки (1,2); (2,4); (3,6) и т.п. Правильно задаться точностью вычислений Tol и сравнить
с ней разницу результатов:

Tol = 1e-10 //По требованиям задачи или задать как входной параметр
if abs((x_3 - x_1) / (x_2 - x_1) - (y_3 - y_1) / (y_2 - y_1)) <= Tol // Точки лежат
на прямой


Второй вариант, обычно более быстрый:

Tol2 = 1e-20 //Квадрат допустимой погрешности
if ((x_3 - x_1) / (x_2 - x_1) - (y_3 - y_1) / (y_2 - y_1)) ^ 2 <= Tol2 // Точки лежат
на прямой


Можно еще правильнее. Подсчитать коэффициенты уравнения прямой между точками 1 и
2, а далее вычислить "расстояние от точки до прямой". Алгоритм легко гуглится. Если
это расстояние меньше Tol, значит точка лежит на прямой. Однако для большинства задач
это - излишнее усложнение.


Ответ 3

Для целочисленных координат можно использовать формулу:


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


или тоже самое, но с кешированием:


void PreIsPointsOnLine(int x1, int y1, int x2, int y2, int& dx, int& dy, int& ds) {
  dx = x2 - x1;
  dy = y2 - y1;
  ds = x1 * y2 - x2 * y1;
}
bool IsPointsOnLine(int dx, int dy, int ds, int x3, int y3) {
  return (x3 * dy - y3 * dx == ds)
}


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


bool function IsPointsOnLine(int x1, int y1, int x2, int y2,
                            int x3, int y3, int x4, int y4) {
  if (IsPointsOnLine(x2, y2, x3, y3, x4, y4) ||
      IsPointsOnLine(x1, y1, x3, y3, x4, y4) ||
      IsPointsOnLine(x1, y1, x2, y2, x4, y4) ||
      IsPointsOnLine(x1, y1, x2, y2, x3, y3) ||) {
    return true;
  }
  return false;
}


Для того, чтобы не было переполнения, числа не должны быть близки к границам целочисленного
типа переменной.


Ответ 4

Вариант с погрешностью предложенный v_mil не работает. 

Если кому вдруг понадобится:

Уравнение прямой через две точки:

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

отсюда:

x*(y2-y1) + x1*(y1-y2) + y*(x2-x1) + y1*(x2-x1) = 0

таким образом для уравнения прямой Ax + By + C = 0 имеем

A = y2 - y1

B = x1 - x2

C = x1 * (y1 - y2) + y1 * (x2 - x1)

Расстояние от точки M (x, y) до прямой считаем по формуле:

d = Math.Abs(A * Mx + B * My + C) / Math.Sqrt(A^2 + B^2)

Вот это расстояние уже можно сравнивать с некой величиной погрешности.