Войти
ПрограммированиеФорумГрафика

Сторона точки по отношению к прямой

Страницы: 1 2 3 Следующая »
#0
12:45, 29 июня 2020

Нужно найти сторону точки по отношению к прямой, интернет выдал такой алгоритм:

// C++ Program to Determine Direction of Point 
// from line segment 
#include <iostream> 
using namespace std; 

// structure for point in cartesian plane. 
struct point { 
  long x, y; 
}; 

// constant integers for directions 
const int RIGHT = 1, LEFT = -1, ZERO = 0; 

long directionOfPoint(point A, point B, point P, long& result) 
{ 
    cout << "A.x: " << A.x << endl;
    cout << "A.y: " << A.y << endl;
    cout << "B.x: " << B.x << endl;
    cout << "B.y: " << B.y << endl;
    cout << "P.x: " << P.x << endl;
    cout << "P.y: " << P.y << endl;
    
    B.x -= A.x; 
    B.y -= A.y; 
    P.x -= A.x; 
    P.y -= A.y; 

    long cross_product = B.x * P.y - B.y * P.x; 

    result = cross_product;
      
    if (cross_product > 0) 
        return RIGHT; 

    if (cross_product < 0) 
        return LEFT; 

    return ZERO; 
} 

// Driver code 
int main() 
{ 
  long value = 0;
    
  point A, B, P; 

  A.x = 0; 
  A.y = 0; 
  B.x = 10; 
  B.y = 10; 
  P.x = 5; 
  P.y = 1; 

  long direction = directionOfPoint(A, B, P, value); 
  cout << "value:" << value << endl; 
  
  if (direction == 1) 
    cout << "Right Direction" << endl; 
  else if (direction == -1) 
    cout << "Left Direction" << endl; 
  else
    cout << "Point is on the Line" << endl; 

    cout << "------------------------" << endl; 
    
  A.x = 0; 
  A.y = 0; 
  B.x = 10; 
  B.y = 10; 
  P.x = 5; 
  P.y = 9; 

  direction = directionOfPoint(A, B, P, value); 
  cout << "value:" << value << endl; 
  
  if (direction == 1) 
    cout << "Right Direction" << endl; 
  else if (direction == -1) 
    cout << "Left Direction" << endl; 
  else
    cout << "Point is on the Line" << endl; 
    
  cout << "------------------------" << endl; 
  
  A.x = 0; 
  A.y = 10; 
  B.x = 10; 
  B.y = 0; 
  P.x = 5; 
  P.y = 1; 

  direction = directionOfPoint(A, B, P, value); 
  cout << "value:" << value << endl; 
  
  if (direction == 1) 
    cout << "Right Direction" << endl; 
  else if (direction == -1) 
    cout << "Left Direction" << endl; 
  else
    cout << "Point is on the Line" << endl; 

    cout << "------------------------" << endl; 
    
  A.x = 0; 
  A.y = 10; 
  B.x = 10; 
  B.y = 0; 
  P.x = 5; 
  P.y = 9; 

  direction = directionOfPoint(A, B, P, value); 
  cout << "value:" << value << endl; 
  
  if (direction == 1) 
    cout << "Right Direction" << endl; 
  else if (direction == -1) 
    cout << "Left Direction" << endl; 
  else
    cout << "Point is on the Line" << endl; 

  return 0; 
} 
A.x: 0
A.y: 0
B.x: 10
B.y: 10
P.x: 5
P.y: 1
value:-40
Left Direction
------------------------
A.x: 0
A.y: 0
B.x: 10
B.y: 10
P.x: 5
P.y: 9
value:40
Right Direction
------------------------
A.x: 0
A.y: 10
B.x: 10
B.y: 0
P.x: 5
P.y: 1
value:-40
Left Direction
------------------------
A.x: 0
A.y: 10
B.x: 10
B.y: 0
P.x: 5
P.y: 9
value:40
Right Direction

Первые два результата явно не правильные (если смотреть относительно начала координат [0, 0]), почему? Или сторона точки зависит от направления самой линии?


#1
13:00, 29 июня 2020

a.x*b.y - a.y*b.x;
det > 0 a cw b; det < 0 a ccw b;
Это или что тебе нужно?

#2
(Правка: 13:16) 13:02, 29 июня 2020

lookid
> a.x*b.y - a.y*b.x;

Не понял, в твоей формуле точка вообще отсутствует.

Линия в системе координат [0, X] x [0, Y] делит плоскость на двое и нужно найти сторону точки относительно линии если смотреть на точку от начала координат [0; 0]
Ожидаемый результат:

A.x: 0
A.y: 0
B.x: 10
B.y: 10
P.x: 5
P.y: 1
Right Direction
------------------------
A.x: 0
A.y: 0
B.x: 10
B.y: 10
P.x: 5
P.y: 9
Left Direction
------------------------
A.x: 0
A.y: 10
B.x: 10
B.y: 0
P.x: 5
P.y: 1
Left Direction
------------------------
A.x: 0
A.y: 10
B.x: 10
B.y: 0
P.x: 5
P.y: 9
Right Direction

#3
13:56, 29 июня 2020

мож ты не понял чего?

Изображение

зеленая стрелка - это cross product

> если смотреть относительно начала координат [0, 0]
смотреть надо относительно точки A

#4
14:03, 29 июня 2020

BingoBongo
Да похоже что LEFT = down, RIGHT = up;
По моему надо таки учитывать направление линии чтобы точно определить сторону точки.

#5
14:08, 29 июня 2020

gamedevfor
Это cross product в 2D.

#6
(Правка: 14:14) 14:14, 29 июня 2020

gamedevfor
Ты перемещаешь свои точки так, чтобы A попала в начало координат, затем поворачиваешь B и P вокруг A так, чтобы B лежала на положительной половине оси y. Теперь можно смотреть слева P или справа.

#7
14:17, 29 июня 2020

BingoBongo
Проще глянуть направление линии, чем искать еще углы поворота.

#8
14:23, 29 июня 2020

gamedevfor
Я имел ввиду мысленно, если надо понять, корректность знака cross product'а.

#9
(Правка: 15:27) 15:23, 29 июня 2020

gamedevfor
> Линия в системе координат [0, X] x [0, Y] делит плоскость на двое и нужно найти
> сторону точки относительно линии если смотреть на точку от начала координат [0; 0]

Вот прямая через (0, 0) и (x, y) и вот некая точка А:

+ Показать

(если нарисовано неправильно, нарисуй для наглядности правильный вариант)

У тебя есть два вектора, на которые натягивается параллелограмм. Площадь параллелограмма равна модулю "векторного произведения в 2D" этих двух векторов; а по какую сторону от прямой он лежит (и точка А лежит), определится знаком этого произведения, плюс или минус. Или ноль, если точка на прямой.

Формулу "векторного" перемножения векторов в 2d lookid написал:
a.x * b.y - a.y * b.x;

#10
20:23, 29 июня 2020

gamedevfor
> Или сторона точки зависит от направления самой линии?

Разумеется зависит. Под "право" ведь подразумевается когда X>0, если ось Y направлена вверх.

#11
(Правка: 21:23) 20:52, 29 июня 2020

gamedevfor
> Нужно найти сторону точки по отношению к прямой
Хочу воткнутся в задачу, но никак непонятна формулировка. Нужно определить с какой стороны от точки находиться линия, или точка от линии? И как в первом случае определять стороны точки?

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

point_side_at_line | Сторона точки по отношению к прямой

gamedevfor
> long cross_product = B.x * P.y - B.y * P.x;
Это выражение находит исключительно "положение точки относительно линии" или "сторону линии", а не то что в нуль посте.

#12
(Правка: 21:19) 21:12, 29 июня 2020

Нужно было как то так:

const long RIGHT = 1, LEFT = -1, ZERO = 0; 

long directionOfPoint(point A, point B, point P, long& result) 
{     
    B.x -= A.x; 
    B.y -= A.y; 
    P.x -= A.x; 
    P.y -= A.y; 

    long cross_product = B.x * P.y - B.y * P.x; 

    result = cross_product;
      
    if (cross_product != 0)
    {
        double k = static_cast<double>(B.y - A.y) / static_cast<double>(B.x - A.x);
        if (k > 0.0)
        {
            if (cross_product < 0) 
                return RIGHT; 
            else
                return LEFT; 
        }
        else
        {
            if (cross_product < 0) 
                return LEFT; 
            else
                return RIGHT; 
        };
    };
    
    return ZERO; 
} 

Вопрос закрыт.

#13
(Правка: 21:57) 21:14, 29 июня 2020

gamedevfor
Только хотел написать подобный код, как ты опередил)

#14
21:17, 29 июня 2020

АкронимЛета
> Только хотел написать такой код, как ты опередил)

Главное было понять причину, почему так.

Страницы: 1 2 3 Следующая »
ПрограммированиеФорумГрафика