Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Три точки на одной прямой.

Автор: Elfet 28.11.2006, 20:26

У меня есть координаты двух точек. Между ними есть ребро. Как определить курсор (третья точка) лежит ли на этом ребре? Да и ещё что бы не точно на самом ребре (попасть курсором в тоненькую линию сложно) а в некоторой области ребра (недалеко от него)? smile

PS Координаты всех трех точек только целые значения.

Автор: Sartorius 28.11.2006, 21:39

A-------B------C

B лежит в области прямой AC, если|(AB {скалярно на} BC) рядом с 1.0.... smile

Автор: Elfet 28.11.2006, 21:44

Точно!

Тока -1?

Добавлено @ 21:46
Ой! smile

) Хм, А что если A-------------C-------B Вот так? Мне ещё нужно что бы между двумя этими точками.

Автор: Sartorius 28.11.2006, 22:00

Не понимаю почему -1... cos(0) = 1?(тока скалярное произведение надо поделить на произвадение длин)... а второе условие(попадание между A и C ) проверь так : |AB| < |AC|... (A-----C-----B) другой случай (B----A---C) не подойдет по cos, который будет в районе -1

Автор: Elfet 28.11.2006, 22:26

Хм, а если В---------------А? С---------В-----------А - условие |AB| < |AC| выполняется. первое тоже. Так не пойдёт smile

Автор: Sartorius 28.11.2006, 22:52

я же выше написал

Цитата

другой случай (B----A---C) не подойдет по cos, который будет в районе -1

Цитата

С---------В-----------А - условие |AB| < |AC| выполняется. первое тоже.

Ну и хорошо , тебе же это расположение тоже подходит (C и A меняются местами а B по прежнему менжду ними на ребре)

Автор: cardinal 28.11.2006, 23:26

Можно подойти к этой проблеме в 3d пространстве, а потом выкинуть лишнее вычисление.

Условия для это задачи будут вроже такими:
1. | AC x AB | <= Epsilon (этот как раз тот запас по расстоянии от отрезка)
2. AC * AB >= 0

Не проверял, но вроде так. Можно попробовать посчитать для нескольких случаев слепив векторы из координат точек и добавив z=0. По формулам можно будет понять, что останется от AC x AB...

Автор: Elfet 28.11.2006, 23:43

Цитата(Sartorius @ 28.11.2006, 23:52

)

C и A меняются местами а B по прежнему менжду ними на ребре

Мне нужно определить где С находится. На этом отрезке или нет?

Автор: cardinal 29.11.2006, 01:05

Посмотри на этот рисунок (если я где-нибудь не прав - поправьте)...

Автор: Elfet 29.11.2006, 09:16

cardinal, | AC x AB | - что это за произведение? И Что такое АС, АВ? Вектора? еz?

Автор: cardinal 29.11.2006, 14:35

Цитата(Elfet @ 29.11.2006, 07:16

)

| AC x AB | - что это за произведение?

http://en.wikipedia.org/wiki/Cross_product

Цитата(Elfet @ 29.11.2006, 07:16

)

И Что такое АС, АВ? Вектора?

Да.

Цитата(Elfet @ 29.11.2006, 07:16

)

еz?

Это вектор (0,0,1).

Автор: Elfet 30.11.2006, 14:13

Попробовал я с произведением - не совсем то что хотелось бы. Так как разная точность получается с разных концов ребра.

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

Автор: kashka 30.11.2006, 14:32

если точка лежит на прямой, ее можно представить как:

t*p1 + (1- t)p2 = p3, 0<=t<=1

находишь t, если 0<=t<=1, значит p3 лежит на отрезке прямой p1, p2

Автор: sergejzr 30.11.2006, 15:33

Elfet, я бы на твоём месте просто проврял на принадлежность к прямой. А то, что мышью трудно попасть - почти решается тем, что просто изменишь курсор, когда мышь на отрезок наедет.

Добавлено @ 15:42
хотя самое простое - вырешать уравнение прямой, y=ax+b, и смотреть совпадения точки с y=ax+b+d где d в интервале -2 до 2.
Уравнение прямой между (x1,y1) и (x2,y2)

a=(y2-y1/x2-x1)
b=y1-a*x1

=> y=(y2-y1/x2-x1)*x+(y1-a*x1)

Проверка, принадлежит ли точка к прямой: в функцию y=a*x+b подставляешь x точки. Если ответ совпадает с y точки, она на прямой

По моему 4 или 5 класс средней школы...

Добавлено @ 15:47
Да, если у тебя действительно отрезок (x1,y1) (x2,y2), а не прямая, просто дополнительно проверяй точку (x,y) на х<мах(х1,х2)&&х>min(х1,х2)&&y<max(y1,y2)&&y>min(y1,y2);

Автор: maxim1000 30.11.2006, 15:56

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

ИМХО, из предложенных вариант со скалярным произведением наиболее прост
ну, если нужно точно задавать допустимое расстояние, то нужно будет считать расстояние от курсора до прямой

Автор: sergejzr 30.11.2006, 16:20

Цитата(maxim1000 @ 30.11.2006, 14:56

)

так что равенство достигнуто не будет никогда, кроме того сравнивать действительные числа на точное равенство вообще не рекомендуется

Естественно надо или округлять, или сравнивать на интервал.

Цитата(maxim1000 @ 30.11.2006, 14:56

)

ИМХО, из предложенных вариант со скалярным произведением наиболее прост

Он в итоге - то же самое, но в другой записи.

Автор: comp 30.11.2006, 18:33

Цитата(sergejzr @ 30.11.2006, 15:33)

Добавлено @ 15:42
хотя самое простое - вырешать уравнение прямой, y=ax+b

Только надо использовать уравнение линии в виде Ax +By +C = 0. В виде y=a*x+b нельзя, т.к. оно не задает прямые, параллельные оси Oy. А вообще, проще всего найти косое произведение векторов, и если оно == 0, то точка принадлежит твоему отрезку(т.к. по смыслу, косое произведение - это площадь параллелограмма). И никаких ненужных проверок в диком количестве.

Автор: Fedor 30.11.2006, 19:43

Цитата(comp @ 30.11.2006, 18:33

)

Только надо использовать уравнение линии в виде Ax +By +C = 0. В виде y=a*x+b нельзя, т.к. оно не задает прямые, параллельные оси Oy.

э... как это??? А то что ты сказал разве не тоже самое, что написано? smile

Автор: cardinal 1.12.2006, 01:00

Цитата(comp @ 30.11.2006, 16:33

)

А вообще, проще всего найти косое произведение векторов, и если оно == 0, то точка принадлежит твоему отрезку(т.к. по смыслу, косое произведение - это площадь параллелограмма). И никаких ненужных проверок в диком количестве.

см. что я написал. smile

Автор: comp 1.12.2006, 05:58

2cardinal: Ну да, по-видимому одно и тоже я написал, только я написал ещё уравнение линии, и рассказал, что есть косое произведение;)
2Fedor: Нет, не одно и тоже.

Автор: Elfet 3.12.2006, 16:18

Вот наконец получилось smile

Нешил не мучаться с углом smile

Код


                    int p1X, p1Y, p2X, p2Y;
                    if (i.x < j.x)
                    {
                        p1X = i.x;
                        p2X = j.x;
                    }
                    else
                    {
                        p1X = j.x;
                        p2X = i.x;
                    }
                    if (i.y < j.y)
                    {
                        p1Y = i.y;
                        p2Y = j.y;
                    }
                    else
                    {
                        p1Y = j.y;
                        p2Y = i.y;
                    }
                    if (mx > p1X - PeakRadius && mx < p2X + PeakRadius && my > p1Y - PeakRadius && my < p2Y + PeakRadius)
                    {
                        double x0 = i.x;
                        double x1 = j.x;
                        double x = mx;
                        double y0 = i.y;
                        double y1 = j.y;
                        double y = my;
                        double a = (y0 - y1) * x + (x1 - x0) * y + (x0 * y1 - x1 * y0);
                        double b = Math.Sqrt(Math.Pow(x1 - x0,2) + Math.Pow(y1 - y0,2));
                        double d = Math.Abs( a / b );
                        if ( d < PeakRadius )
                        {
                            bool direct = true;
                            foreach (Peak f in j.ribs)
                                if (i.numer == f.numer) direct = false;
                            r = new Rib(i, j, direct);
                        }
                    }

Автор: Elfet 16.12.2006, 22:20

Вот что получилось: http://forum.vingrad.ru/topic-127665/kw-graph-simple.html smile