2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Относительное положение точки и прямой линии
Сообщение26.02.2014, 15:38 
В сети есть такое решение этой задачи. http://algolist.manual.ru/maths/geom/datastruct.php
Изображение
Код:
class Point {
public:
  double x;
  double у;
 
  Point(double _x = 0.0, double _y =0.0);
// Опустим ненужные элементы класса
.......

enum {LEFT,  RIGHT,  BEYOND,  BEHIND, BETWEEN, ORIGIN, DESTINATION};
//    СЛЕВА, СПРАВА, ВПЕРЕДИ, ПОЗАДИ, МЕЖДУ,   НАЧАЛО, КОНЕЦ

int Point::classify(Point &p0, Point &pl)
{
  Point p2 = *this;
  Point a = p1 - pO; // 1
  Point b = p2 - pO; // 2
  double sa = a. x * b.y - b.x * a.y; // 3
  if (sa > 0.0)
    return LEFT;
  if (sa < 0.0)
    return RIGHT;
  if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0))
    return BEHIND;
  if (a.length() < b.length())
    return BEYOND;
  if (pO == p2)
    return ORIGIN;
  if (p1 == p2)
    return DESTINATION;
  return BETWEEN;
}

Point Point::operator- (Point &p)
{
  return Point (x - р.х, у - p. у);
}

Я знаю, что чтобы определить положение точки слева или справа относительно прямой, достаточно подставить координаты этой точки в уравнение прямой и посмотреть на результат. Если он отрицателен, то точка лежит слева, если положителен, то точка лежит справа. Если же результат равен нулю, то точка принадлежит прямой. Как я понимаю, в это куске кода делается нечто похожее.

1)
Код:
Point a = p1 - pO;
Point b = p2 - pO;

Векторы $\overline{p_1}$ и $\overline{p_0}$ начинаются в начале координат и заканчиваются в точках $p_1$ и $p_0$. В результате вычитания мы получаем новый вектор $\overline{a}$. Аналогично с вектором $\overline{b}$. Я правильно понял смысл этих двух строк?
ИзображениеНачало и конец векторов рисовал специально, чтобы не накладывались друг на друга, иначе не видно направления вектора.

2)
Код:
double sa = a. x * b.y - b.x * a.y;
Я не пойму, что делает этот код. Напоминает уравнение прямой в виде
$$\frac{x - x_1}{x_2 - x_1} - \frac{y-y_1}{y_2 - y_1}=0$$
пожалуйста, помогите разобраться.

 
 
 
 Re: Относительное положение точки и прямой линии
Сообщение26.02.2014, 19:05 
Аватара пользователя
Gts
В вашей же ссылке есть книжка. Где всё расписано.
Ласло М. Вычислительная геометрия и компьютерная графика на C++

 
 
 
 Re: Относительное положение точки и прямой линии
Сообщение26.02.2014, 20:51 
Аватара пользователя
Это псевдоскалярное произведение: площадь параллелограмма натянутого на вектора, взятая со знаком плюс, если поворот векторов происходит против часовой и со знаком минус, если по часовой.
Почитайте статьи Андреевой и Егорова:
http://informatics.mccme.ru/course/view.php?id=22
в своё время они мне очень помогли разобраться в таком.

 
 
 
 Re: Относительное положение точки и прямой линии
Сообщение26.02.2014, 21:58 
И картинка для (1) правильная (если пренебречь её корявостью. :wink:), раз никто не упомянул выше.

(Оффтоп)

По поводу корректности кода с учётом того, что там числа с плавающей точкой, ничего не скажу, но подозреваю (наверно, зря).

-- Чт фев 27, 2014 01:54:24 --

Gts в сообщении #830787 писал(а):
Я не пойму, что делает этот код.
Кстати, можно ведь тоже сделать чертёж и посмотреть. Выражение простое, трудно сделать что-нибудь неправильно:
Вложение:
Screenshot-277.png
(И антикоммутативность тут тоже можно увидеть, стоит только захотеть.)

Или, если присмотреться по-другому, можно увидеть, что $a_xb_y - b_xa_y$ — это скалярное произведение $\vec a$ и $(b_y, -b_x)$. Второй вектор — это $\vec b$, повёрнутый на $-90^\circ$. Откуда и свойства этого произведения, в том числе смена знака при отражении аргументов (заданный поворот-то не отразится).

 
 
 
 Re: Относительное положение точки и прямой линии
Сообщение27.02.2014, 15:45 
Все, разобрался. Всем спасибо.

(Оффтоп)

arseniiv, а в чем Вы нарисовали картинку?

 
 
 
 Re: Относительное положение точки и прямой линии
Сообщение27.02.2014, 21:04 

(2 Gts.)

В GeoGebra.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group