Как найти точку пересечения перпендикулярных отрезков

Метки нет (Все метки)

Привет! Помогите двоишнику, я же тупой батхэд !

Есть отрезок, заданный двумя точками P1 и P2. Есть точка P3. Так вот, нужно найти координаты точки пересечения перпендикуляра, опущенного на заданный отрезок и, собственно этого отрезка, причём, если точка не находится на отрезке – как то просигнализировать …

Нужен рабочий код. Можно использовать С++ 11/14 и Qt, в котором есть

1

static float dotProduct(const QVector2D& v1, const QVector2D& v2);

…

Миниатюры

1471 / 826 / 140

Регистрация: 12.10.2013

Сообщений: 5,456

Хлебнете вы от аналитической геометрии…
Может тут?
Подобие math.h для геометрии
Где-то на форуме была точно помню…
Гуглить вроде “ перпендикуляр на прямую, Координаты перпендикуляра на прямую”?.

Добавлено через 6 минут
Вот ответ.
Перпендикуляр из точки на прямую

Не… буст в топку

Да гуглил… Найти расстояние (длину этого перпендикуляра) от этой точки до отрезка – нет проблем, а вот координаты – хз как находить.

Мне собственно нужны даже не совсем координаты, а просто смещение от точки P1 до точки P4, то есть расстояние от начальной точки отрезка, до точки пересечения. Конечно же, зная координаты, я это расстояние найду. Но вроде бы как то можно скалярным произведением всё решить …. Помогите, dotProduct использовать можно !

Добавлено через 6 минут
То есть фактический ответом на мой вопрос будет это: (верно? Excalibur921 ? )

1
2
3
4
5
6

//Прямая задана двумя точками (x1,y1) (x2,y2). Есть третья точка (x3,y3). Из точки нужно опустить перпендикуляр и найти координаты его основания на прямой (x4,y4)
float x1, x2, x3, x4;
float y1, y2, y3, y4;
//...
x4=((x2-x1)*(y2-y1)*(y3-y1)+x1*pow(y2-y1, 2)+x3*pow(x2-x1, 2))/(pow(y2-y1, 2)+pow(x2-x1, 2));
y4=(y2-y1)*(x4-x1)/(x2-x1)+y1;

Добавлено через 1 минуту
Ну ок, а как проверить, есть ли вообще решение? Ну то есть если перпендикуляр опускается на отрезок, но не попадает в его границы (попадает по лучу, а не по отрезку) ?

1471 / 826 / 140

Регистрация: 12.10.2013

Сообщений: 5,456

То найдет координаты точки на луче вроде.

чта?
Я нахожу координаты точки пересечения перпендикуляра и отрезка. Как теперь мне определить, принадлежать ли эти координаты этому отрезку?

1471 / 826 / 140

Регистрация: 12.10.2013

Сообщений: 5,456

Найдет координаты точки перпендикуляра на луч за границами отрезка.

Может можно и проще если важна скорость, но нужно очень шарить в геометрии. Надобыло в геометрии создавать…и просить решение в символьной форме.

Ну наверно проверить принадлежность точки отрезку… вход точки в интервал между X и Y точек P1 и P2. А как еще?

Добавлено через 1 минуту
Может есть еще решение в что то типа высота треугольника…

ну это – то понятно:

1

if((x3 > x1 && x3 < x2) && ... и тд

но дело в том, что у тебя отрезок может быть направлен в отрицательную сторону, тогда у тебя x2 будет меньше x1 и по этому тут нужно сперва всё это перегонять в 1-ю четверть (всего 3 координатные четверти), делать операцию и обратно. Понимаешь? По этому я и спрашиваю готовую формулу, т.к. лень всё делать самому.

В Qt наверняка что – то есть, неужели нет?

1471 / 826 / 140

Регистрация: 12.10.2013

Сообщений: 5,456

А можно узнать угол отрезка P1 P3 даст Альфа 1 и угол отрезка P1 P2 даст Альфа 2. Повернуть отрезок P1 P3 на Альфа 2 будет как треугольник с горизонтальным основанием(без поворота). Тогда P4=(x1,y3).

Добавлено через 3 минуты

Скорей всего…
Тогда надобыло в теме Qt создавать .Или поискать либы по геометрии в Qt…А чем плоха что я кидал либу? Там и 3д есть.

Да толку то …, всё равно все сидят только здесь

Тем что её надо изучать.

Ладно, через жопу на Qt реализовал, скоростью и не пахнет, да мне она и не нужна.
Вообще странно, что нет ничего готового для таких стандартных вещей …

1471 / 826 / 140

Регистрация: 12.10.2013

Сообщений: 5,456

Я в Qt сначала неделю его ставил… Неверные переменные среды QT 4.8.0 Creator 2.4.1
потом не мог вывести синусоиду никто не подсказал 600 чел смотрели тему…
Синусоида OpenGL и слайдер
Потом ели стер этот Qt еще и с ошибками даже на удалении =).А примеры там это вообще жесть… куча мусора. Как не программист делал примеры туда.

2013 / 1342 / 382

Регистрация: 16.05.2013

Сообщений: 3,463

Записей в блоге: 6

Так там есть же ответ в последнем посте На самом деле сейчас большинство современного софта пишется на Qt, т.к. код на Qt собирается на любой современной ОС. Зря ты от него отказался

Спасибо. Но я не очень понимаю, что значит берёте три вектора.
У меня есть три пары координат (см рисунок в первом посте), вот как из них получить векторы?

А это что, сложение вектора с о скобками, в которых чего? скалярное произведение или что ?

Не могли бы вы в координаты ваши формулы перевести?

2013 / 1342 / 382

Регистрация: 16.05.2013

Сообщений: 3,463

Записей в блоге: 6

Хмм… а что это за условие?

Результирующие координаты это x и у ?

Добавлено через 2 минуты
Ааа понял, это что б как бы точка принадлежала именно отрезку, а не лучу…
Ну что ж, спасибо, но в итоге это получается намноОого громоздче, нежели

1
2

x4=((x2-x1)*(y2-y1)*(y3-y1)+x1*pow(y2-y1, 2)+x3*pow(x2-x1, 2))/(pow(y2-y1, 2)+pow(x2-x1, 2));
y4=(y2-y1)*(x4-x1)/(x2-x1)+y1;

из 3-го поста …
Всё таки векторная математика – чисто понт, в действительности – то всё идёт через обычные умножения, сложения и тд, но если решать всё с понтом, то решение получится намного сложнее

Ilot

2013 / 1342 / 382

Регистрация: 16.05.2013

Сообщений: 3,463

Записей в блоге: 6

Это еще как посмотреть:

1
2
3

k = ((x3-x1) * (x2-x1) + (y3-y1)*(y2-y1))/ (pow(x2-x1, 2) + pow(y2-y1, 2));
x = x1 + k * (x2-x1);
y = y1 + k * (y2-y1);

Ну в принципе да…
Ладно, спасибо тебе о великий Ilot

1471 / 826 / 140

Регистрация: 12.10.2013

Сообщений: 5,456

ТС у вас работает?
Решил попробовать и не работает ваш код.
вершина
отрезок
искомая

1471 / 826 / 140

Регистрация: 12.10.2013

Сообщений: 5,456

Второй метод который вы просили расписать через вектора… и который быстрей должен быть.

Второй метод Ilot.

Добавлено через 24 минуты
Получается Butt-Head, использует метод который я предложил, а модератор отметил неработающую формулу как лучший ответ… забавно… =).

Это не модератор отметил, а я Раз так, снимаю с ИЛОТА лучший ответ. Садись – два Илот .
Ставлю лучший ответ чудо мечу. (и не один, я не жадный ехехе)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

//*******************************************************

//  Нахождение точки пересечения прямых (p1,p2) и (p3,p4)

//  Результат – факт пересечения

//*******************************************************

function CrossLines(const p1,p2,p3,p4: TxPoint;

  var res: TxPoint): Boolean;

const

  Prec = 0.0001;

var

  a1, a2: Extended;

  b1, b2: Extended;

  c1, c2: Extended;

  v: Extended;

begin

  a1 := p2.y – p1.y;

  a2 := p4.y – p3.y;

  b1 := p1.x – p2.x;

  b2 := p3.x – p4.x;

  v := a1*b2 – a2*b1;

  Result := (abs(v) > Prec);

  if Result then

  begin

    c1 := p2.x*p1.y – p1.x*p2.y;

    c2 := p4.x*p3.y – p3.x*p4.y;

    res.X := –(c1*b2 – c2*b1)/v;

    res.Y := –(a1*c2 – a2*c1)/v;

  end;

end;

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

//*****************************************************

//  Проверка факта нахождения точки res между

//  концами отрезка (p1,p2).

//  Решение с помощью условных операторов и

//  коэффициентов A=(y2-y1) B=(x1-x2).

//  Выступают в качестве параметров, чтобы не тратить

//  время на их подсчет, т.к. в вызывающей стороне

//  они уже посчитаны

//*****************************************************

function CheckCrossPoint(const p1, p2, res: TxPoint;

  const A,B: Extended): Boolean;

begin

  Result :=

    (((B<0) and (p1.X < res.X) and (p2.X > res.X)) or

     ((B>0) and (p1.X > res.X) and (p2.X < res.X)) or

     ((A<0) and (p1.y > res.Y) and (p2.Y < res.Y)) or

     ((A>0) and (p1.y < res.Y) and (p2.Y > res.Y)));

end;

//*****************************************************

//  Проверить факт нахождения точки res между

//  концами отрезка (p1,p2)

//  Арифметическое решение без коэффициентов

//*****************************************************

function CheckCrossPoint(const p1, p2, res: TxPoint): Boolean;

begin

  Result :=

    (abs(p2.x–p1.x)>= abs(p2.x–res.x) + abs(p1.x–res.x)) and

    (abs(p2.y–p1.y)>= abs(p2.y–res.y) + abs(p1.y–res.y));

end;

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

//**********************************************************

// Посчитать угол пересечения векторов по коэфф-ам А и B

//**********************************************************

function CalcCrossAngle(const a1,b1: Extended;

  const a2,b2: Extended): Extended;

var

  c1, c2: Extended;

begin

  c1 := ArcTan2(a1,b1);

  c2 := ArcTan2(a2,b2);

  Result := c2–c1;

  if Result < –pi then

    Result := 2*pi + Result;

  if Result > pi then

    Result := Result – 2*pi;

end;

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

//**********************************************************

//  Тип пересечения прямых (p1,p2) и (p3,p4)

//**********************************************************

type

  TxCrossLineResult = (

    xclrEqual    = –32// эквивалентны

   ,xclrParallel = –16// параллельны

   ,xclrOk       = 0  // как минимум пересечение есть

   ,xclrFirst    = 1  // попадает в первый отрезок

   ,xclrSecond   = 2  // попадает во второй отрезок

   ,xclrBoth     = 3  // попадает в оба

   ,xclrPerpend  = 4  // перпендикулярны

   // можно найти по маске через AND, но для полноты картины

   ,xclrFirstP   = 5  // перпендикулярны и попадает в первый

   ,xclrSecondP  = 6  // перпендикулярны и попадает в второй

   ,xclrBothP    = 7  // перпендикулярны и попадает в оба

   );

//**********************************************************

//  Нахождение точки пересечения прямых (p1,p2) и (p3,p4)

//  Определяет параллельность, совпадение,

//  перпендикулярность, пересечение.

//  Определяет, каким отрезкам принадлежит.

//  Находит угол(рад.) от (p1,p2) к (p3,p4):

//    отрицательное значение – против часовой

//    положительное – по часовой

//**********************************************************

function CrossLines(const p1,p2,p3,p4: TxPoint;

  var res: TxPoint; var Angle: Extended): TxCrossLineResult;

const

  Prec = 0.0001;

var

  a1, a2: Extended;

  b1, b2: Extended;

  c1, c2: Extended;

  v: Extended;

begin

  Angle := 0;

  a1 := p2.y – p1.y;

  a2 := p4.y – p3.y;

  b1 := p1.x – p2.x;

  b2 := p3.x – p4.x;

  c1 := p2.x*p1.y – p1.x*p2.y;

  c2 := p4.x*p3.y – p3.x*p4.y;

  v := a1*b2 – a2*b1;

  if abs(v) > Prec then

  begin

    Result := xclrOk;

    res.X := –(c1*b2 – c2*b1)/v;

    res.Y := –(a1*c2 – a2*c1)/v;

    if CheckCrossPoint(p1,p2,res) then

      Result := TxCrossLineResult(Integer(Result) +

        Integer(xclrFirst));

    if CheckCrossPoint(p3,p4,res) then

      Result := TxCrossLineResult(Integer(Result) +

        Integer(xclrSecond));

    if (abs(a1*a2 + b1*b2) < Prec) then

      Result := TxCrossLineResult(Integer(Result) +

        Integer(xclrPerpend));

    Angle := CalcCrossAngle(a1,b1,a2,b2);

  end else

  begin

    Result := xclrParallel;

    if ((abs(c1*b2 – c2*b1) < Prec) and

       (abs(a1*c2 – a2*c1) < Prec))

    then

      Result := xclrEqual;

  end;

end;