Определить,лежат ли 3 точки на одной прямой на C#

Question

Необходимо определить,лежат ли какие-либо 3 точки из множества на 1 прямой. Проблема в том,что координаты точек вводятся графически,по клику мышки,и идеально на одной прямой они оказываются очень редко.В дальнейшем на этих точках нужно строить треугольники,и выходит,что треугольник сливается в одну линию,поскольку разницы в несколько пикселей на picturebox'е не видно. Для вычислений я использовала формулу,полученную из уравнения прямой и приравнивала к нулю. Толку мало. Понимаю,что необходимо ввести погрешность,но не понимаю,как ее рассчитать и как это записать в код.\ сейчас имею вот что:`

for (int i = 0; i < x.Count; i++)
         {
                 for (int j = i + 1; j < x.Count; j++)
                 {
                         for (int k = j + 1; k < x.Count; k++)
                         {
                    if (((x[k] - x[i]) * (y[j] - y[i])) - ((x[j] - x[i]) * (y[k] - y[i]))==0) 
                              {

Координаты записаны в два списка.

Answer 1

Внутри оператора if рассчитывается площадь (удвоенная) треугольника, построенного по трём точкам.

Но вместо сравнения с нулём лучше абсолютное значение этой площади сравнивать с некой малой величиной. Или не площадь, а величину, по порядку близкую к отклонению точек от прямой (вместо 1.0 подберите разумное значение):

area = abs((x[k] - x[i]) * (y[j] - y[i])) - ((x[j] - x[i]) * (y[k] - y[i]));
roughsize = max(x[k],x[i], x[j]) - min(x[k],x[i], x[j]) + 
            max(y[k],y[i], y[j]) - min(y[k],y[i], y[j])
if (area / roughsize < 1.0) ...

Answer 2

Я вижу два пути решения вашей проблемы.

Уменьшить погрешность графического ввода путем приведения координат клика к координатам более крупной сетки. Общая идея в следующем: Мы фиксируем сетку, в узлах которой могут располагаться точки треугольников с шагом, допустим в 5 пикселей (подбирается опытным путем до комфортного значения.). Визуализировать сетку не обязательно. Далее, получив координаты клика, вычисляем локальные координаты ближайшего узла сетки путем деления координаты на шаг сетки и округления до ближайшего целого. Таким образом мы делаем принудительную корректировку пользовательского ввода. Далее пользуетесь уже имеющимися способами проверки существования невырожденного треугольника используя полученные локальные координаты точек на сетке. При последующей отрисовке, не забываем умножать значения локальных координат сетки на шаг сетки, для получения координат в пикселях.
Более сложный вариант - оценить погрешность введенных данных и сделать вывод на основе этой оценки. Тут есть варианты:
- Определяем две самые удаленные друг от друга точки A и B и получаем уравнение прямой AB. Находим точку D, лежащую на пересечении перпендикуляра, проходящего через третью точку C и прямую AB. Вычисляем отношение длин CD/min(AD,DB) это и будет наша погрешность. Сравниваем погрешность с некоторой малой величиной - заданной допустимой погрешностью. Если погрешность меньше допустимой - точки на одной прямой, если больше - имеем невырожденный треугольник. Но тут надо не забыть обработать граничные случаи, например, когда две точки треугольника расположены так близко друг к другу, что их можно считать совпадающими.
- Использовать окружности некоторого минимального радиуса, который будет играть роль погрешности, с центрами в проверяемых точках и проверять пересечение прямой, проходящей через наиболее удаленные друг от друга точки с окружностью третьей точки. Тут так же требуется проверка точек на совпадение, например, путем сравнения расстояния между ними с используемым радиусом окружности.
- Определить длины всех сторон, из длины наибольшей стороны вычесть, сумму двух оставшихся и сравнить с некоторой малой величиной. Способ довольно грубый, но простой в реализации.

Вероятно математики смогут предложить еще несколько вариантов оценки погрешности, я на вскидку вспомнил только эти. С практической точки зрения, лично я предпочел бы первый вариант за его простоту, но тут уже все зависит от вашей конечной цели.

Answer 3

Берёте 3 точки, расчитываете расстояние между ними, берёте самое большое -- это будет основание треугольника, тогда отклонение средней точки от прямой будет равно высоте этого треугольника проведённой из неё (т.к. она является перпендикуляром к нашей прямой) вот формулы Задаёте в вашей программе максимально допустимое отклонение в пикселях и сравниваете его с полученным значением высоты. Если меньше, значит точки на одной прямой, если больше, то на разных

Углы необходимые для формулы на сколько я помню можете получить из класса Vector(a, b)

БЛОГ НА HUSL

Определить,лежат ли 3 точки на одной прямой на C#

Ответы (3 шт):