1

Тема: Геометрия

Дают координаты точки и координаты начала и конца вектор. Нужно определить принадлежит ли точка лучу, определяемому вектором или нет.

2

Re: Геометрия

Как это сделать? Help please

3

Re: Геометрия

Если делать само тупо, то проверяешь что точка принадлежит прямой вектора, а теперь просто смотришь, что она лежит с той же стороны что и конец вектора относительно начала вектора.

4

Re: Геометрия

Можете показать код или объяснить поглубже?

5 Отредактировано brainail (2010-03-09 21:40:25)

Re: Геометрия

Пусть (X, Y) - сама точка.
(X1, Y1) - точка начала вектора, (X2, Y2) - точка конца вектора, луч (X1, Y1) -> (X2, Y2).
Для начала проверим что точка лежит на прямой (X1, Y1) - (X2, Y2) :
A = Y1 - Y2;
B = X2 - X1;
C = - A * X1 - B * Y1;
if (A * X + B * Y + C != 0) то можно смело говорить что тока не лежит, иначе она лежит но не понятна на какой стороне луча.

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

Проверим для начала что точка уже может лежать в отрезке вектора:
if (X >= MIN(X1, X2)) && (X <= MAX(X1, X2)) && (Y >= MIN(Y1, Y2)) && (Y <= MAX(Y1, Y2)) - то мы точно говорим что лежит,иначе возможен ещё 1 случай =>

Теперь мы проверим на отдалённость конца вектора и самой точки от начала вектора:
if (DIST(X1, Y1, X, Y) >= DIST(X1, Y1, X2, Y2)) то мы точно говорим ответ да, иначе точно ответ нет.

Если в решение требуется некоторая точность, то просто везде добавить проверки на EPS.

 A = Y1 - Y2;
 B = X2 - X1;
 C = - A * X1 - B * Y1;
 if (A * X + B * Y + C != 0) return "YES"; else return "NO";
 if (X >= MIN(X1, X2)) && (X <= MAX(X1, X2)) && (Y >= MIN(Y1, Y2)) && (Y <= MAX(Y1, Y2)) return "YES";
 if (DIST(X1, Y1, X, Y) >= DIST(X1, Y1, X2, Y2)) return "YES";
 return "NO".

6

Re: Геометрия

Мне кажется, можно немного проще:
Пусть дан вектор AB и точка P. Тогда точка лежит на прямой, содержащей AB тогда и только тогда, когда [AB,AP]=0, т.е. скалярное произведение AB и AP равно нулю. Чтобы теперь определить, лежит ли эта точка на нужном луче, надо чтобы векторы AB и AP были направлены в одну сторону, т.е. скалярное произведение AB на AP должно быть больше или равно 0.
Итого получаем такие условия:
[AB,AP]=0 && (AB,AP)>=0

7 Отредактировано brainail (2010-03-09 21:10:01)

Re: Геометрия

big_smile Вектора ....... big_smile Говорю же писал что в голову лезит! smile

8

Re: Геометрия

На самом деле еще год назад я бы делал как ты говорил smile
Просто в универе в начале семестра читали векторы и я понял что с ними все намного проще, если расшарить.

9

Re: Геометрия

Так да, и главное точность гораздо выше! smile

10

Re: Геометрия

При более низких познаниях в геометрии можно провести перпендикуляр относительно луча через его начало,и смотреть чтобы точка лежала как на прямой,так и по одну сторону от перпендикуляра.А именно если A,B,C-коэффициенты перпендикуляра,  side1=Ax2+By2+C,a side2=Axp+Byp+c,то side1*side2>0,тоесть знак у side1 и side2 одинаковый.