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

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

 Daenyth28 сент. 2010 г., 16:22
Как определяется ваша линия? Функция на 2d плоскости?
 John Smith28 сент. 2010 г., 16:32
Что именно вам дали? Три очка? или три точки и линия?

Ответы на вопрос(5)

Решение Вопроса

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

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

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

 John Smith28 сент. 2010 г., 16:31
Это намного лучше, потому что нет риска деления на 0.
 joaquin28 сент. 2010 г., 17:08
+1 математически то же самое, но концепция более простая / визуальная / прямолинейная (мне это нравится).
 Mirror31802 авг. 2017 г., 03:10
Ошибки с плавающей точкой означают вместо проверкиarea == 0, у вас будет намного лучше проверять времяarea < 0.001
 Hossein02 окт. 2010 г., 13:02
Используя эту формулу с A: (516 520) B: (538 523) и C: (526 475), я получаю площадь -1578! Это почему?
 florin08 янв. 2014 г., 02:21
@JohnMachin: Если вы хотите перейти к простым операциям с процессором, по моей формуле вам нужно только одно сравнение, так как значение всегда будет положительным. С тестом dcp вам нужно два сравнения, так как вы не знаете знак различия.
 Rasoul30 июл. 2013 г., 18:10
Как насчет трех точек в трехмерном пространстве?
 John Machin06 окт. 2010 г., 04:53
@ Джо Кингтон: (1) Вы должны сделать толерантность <материал <терпимость. (2) Формула @ florin требует 3 умножения и 5 сложений / вычитаний, чтобы получить результат «должно быть ноль». формула @ dcp, скорректированная путем изменения== в-, требуется 2 mults и 5 вычитаний, чтобы получить результат «должно быть ноль». Я бы поставил галочку @dcp, а не @florin.
 Joe Kington28 сент. 2010 г., 16:43
Просто чтобы указать на что-то ... Это математически эквивалентно ответу @ dcp выше (если вы игнорируете/2), но проверка, если область равна 0, облегчает добавление допуска ... (т.е.stuff < err_tolerance вместоstuff1 == stuff2 как и @dcp выше)
 florin04 окт. 2010 г., 06:30
@ Хоссейн: Вы спрашиваете об абсолютном значении или о знаке? С твоими очками и моей формулой я получаю -510. Знак означает, что вы выбрали определенный порядок точек. Вы можете поменять местами A с C или B, и вы получите положительную область, даже подумав, что это тот же треугольник.

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

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 совпадают. Наклон - это изменение у, деленное на изменение х, поэтому мы имеем:

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

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

Обратите внимание, что если вы используете double, вы можете проверить по epsilon:

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;
}
 dcp28 сент. 2010 г., 16:30
@dtb - я добавил объяснение, дайте мне знать, если у вас остались вопросы.
 Boris Gorelik28 сент. 2010 г., 16:34
хороший трюк Однако проверка чисел с плавающей запятой на равенство небезопасна. Вы можете проверить абсолютную разницу по заранее определенному порогу, который зависит от разрешения (чувствительности), которого вы хотите достичь
 Mark Peters28 сент. 2010 г., 16:35
@bgbg: Где именно используются числа с плавающей точкой?
 Georg30 янв. 2015 г., 17:22
Мне нравится это, потому что это более стабильно: умножение / деление происходит после сложения / вычитания. Отсутствует только сравнение сторон: doublesEqual ((y1 - y2) * (x1 - x3), (y1 - y3) * (x1 - x2), EPSILON). Это лучше, чем тестирование с произвольным эпсилоном 1e-9, потому что ваши значения могут быть далеко от 1 (см.Сравнение значений с плавающей запятой ).
 martineau29 сент. 2010 г., 02:13
Это требует меньше вычислений, чем ответ @ florin, даже если он эквивалентен (поэтому я голосую за него).
 dcp28 сент. 2010 г., 16:42
@dtb - x1 == x2 работает нормально, рассмотрим следующие случаи: коллинеарность (-2,0, -2,1, -1,1) возвращает false, а коллинеарность (-2,0, -2,1, -2, 2) возвращает истину. Я думаю, что угловые случаи покрыты, дайте мне знать, если вы не согласны.
 Johannes Charra28 сент. 2010 г., 16:37
Разве один склон не может быть положительным, а другой отрицательным? Я думаю, что вы должны сравнить их абсолютное значение.
 Mark Peters28 сент. 2010 г., 16:39
@jellybean: я тоже так думал, но это подтвердилось. Помните, что отрицательный уклон - это другая линия (слева направо и снизу справа). Если строка идет 3, 1, 2 с 1 в середине, она все еще работает, потому что отрицательные отрицательные.
 dtb28 сент. 2010 г., 16:25
Что оно делает?
 Boris Gorelik29 сент. 2010 г., 12:47
@Mark: вы правы, здесь не плавает. С другой стороны, этот алгоритм не ограничен для поплавков, так что ...
 dtb28 сент. 2010 г., 16:34
Угловые чехлы? например x1 == x2
 kriss28 сент. 2010 г., 16:45
@jellybean: отрицательные наклоны будут давать линии, отличные от положительных, тогда нет, вы не должны сравнивать абсолютные значения, потому что вы не получите правильный ответ.
 dcp24 дек. 2015 г., 14:13
@georg - На самом деле, это сравнение абсолютногоразница между продуктами и убедившись, что разница <= 1e-9. Так литовары Сами близкие или далекие от 1 не имеют значения. Опять же, нас просто интересует, является ли абсолютная разница продуктов 1e-9 или меньше, что для наших целей означает, что мы можем предположить, что продукты равны и, следовательно, наклоны совпадают. Надеюсь, это поможет.

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

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

Удачи.

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

подробности

Ваш ответ на вопрос