HLFX.Ru Forum
профиль •  правила •  регистрация •  календарь •  народ •  FAQ •  поиск •  новое •  сутки •  главная •  выход  
HLFX.Ru Forum HLFX.Ru Forum > Наш форум > Технические вопросы > Найти точку пересечения 2х отрезков
  Предыдущая тема   Следующая тема
Автор
Тема Новая тема    Ответить
FiEctro
Кот Арсис

Дата регистрации: Aug 2006
Проживает: код
Сообщений: 12832
Возраст: 32

Рейтинг



Найти точку пересечения 2х отрезков

Скажу сразу, я не силён в аналитической геометрии, поэтому за решением пошёл сразу в интернет.

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

C++ Source Code:
1
Vector2 GetIntersection(Vector2 p1, Vector2 p2, Vector2 p3, Vector2 p4)
2
{
3
  float d1 = Vector3.Cross(p1 - p3, p4 - p3).z;
4
  float d2 = Vector3.Cross(p2 - p3, p4 - p3).z;
5
  if (d1 - d2 == 0) return Vector2.negativeInfinity;
6
  return (d1 * p2 - d2 * p1) / (d1 - d2);
7
}


Но мне нужно чтобы отрезки были именно конечными и не единичными т.е. могли иметь любую длину но не бесконечные.

Находил нечто подобное:
https://www.interestprograms.ru/sou...e-dvuh-otrezkov

Но тоже толком не работает как положено. Выдаёт пересечение только в очень редких случаях.

C++ Source Code:
1
public static Vector2 GetIntersection(Vector2 r1, Vector2 r2, Vector2 p1, Vector2 p2)
2
{
3
  // Параметрическое уравнение отрезка
4
  // x = x0 + vt
5
  // y = y0 + wt
6
  // где v = x1 - x0
7
  //     w = y1 - y0
8
  // при 0 <= t <= 1
9
 
10
 
11
  // Оповещение о событиях пересечения или не пересечения.
12
  //info = new Info();
13
 
14
  // Координаты направления вектора синего отрезка
15
  float v = r2.x - r1.x;
16
  float w = r2.y - r1.y;
17
 
18
  // Координаты направления вектора красного отрезка
19
  float v2 = p2.x - p1.x;
20
  float w2 = p2.y - p1.y;
21
 
22
  // ===== Частные случаи не пересечения =====
23
 
24
  // Отрезки должны быть определены
25
  if (v == 0 && w == 0 && v2 == 0 && w2 == 0)
26
  {
27
    //info.Id = 10;
28
    //info.Message = "Отрезки неопределённы";
29
 
30
    return Vector2.negativeInfinity;
31
  }
32
  else if (v == 0 && w == 0)
33
  {
34
    //info.Id = 11;
35
    //info.Message = "Синий отрезка неопределён";
36
 
37
    return Vector2.negativeInfinity;
38
  }
39
  else if (v2 == 0 && w2 == 0)
40
  {
41
    //info.Id = 12;
42
    //info.Message = "Красный отрезка неопределён";
43
 
44
    return Vector2.negativeInfinity;
45
  }
46
 
47
  // Для вычисления параллельности отрезка
48
  // необходимо сравнить направления их векторов.
49
 
50
  // Вычисляем длины векторов
51
  float lenBlue = Mathf.Sqrt(v * v + w * w);
52
  float lenRed = Mathf.Sqrt(v2 * v2 + w2 * w2);
53
 
54
  // Нормализация векторов - создание единичного вектора направления
55
  float x = v / lenBlue;
56
  float y = w / lenBlue;
57
  float x2 = v2 / lenRed;
58
  float y2 = w2 / lenRed;
59
 
60
 
61
  float epsilon = 0.000001f;
62
 
63
  // Проверка на совпадение
64
  if (r1.x == p1.x && r1.y == p1.y && r2.x == p2.x && r2.y == p2.y)
65
  {
66
    //info.Id = 20;
67
    //info.Message = "Отрезки совпадают";
68
 
69
    return Vector2.negativeInfinity;
70
  }
71
 
72
  // Проверка на параллельность с определенной точностью.
73
  if (Mathf.Abs(x - x2) < epsilon && Mathf.Abs(y - y2) < epsilon)
74
  {
75
    //info.Id = 21;
76
    //info.Message = "Отрезки параллельны";
77
    return Vector2.negativeInfinity;
78
  }
79
 
80
 
81
  float t2 = (-w * p1.x + w * r1.x + v * p1.y - v * r1.y) / (w * v2 - v * w2);
82
 
83
  // t = (p1.X - r1.X + v2t2) / v - (у.1)
84
  float t = (p1.x - r1.x + v2 * t2) / v;
85
 
86
  // Если один из параметров меньше 0 и больше 1, значит пересечения нет.
87
  if (t < 0 || t > 1 || t2 < 0 || t2 > 1)
88
  {
89
    //info.Id = 20;
90
    //info.Message = "Пересечения нет";
91
 
92
 
93
    return Vector2.negativeInfinity;
94
  }
95
 
96
  // Координаты точки пересечения
97
  float xx = p1.x + v2 * t2;
98
  float yy = p1.y + w2 * t2;
99
 
100
 
101
  //info.Id = 0;
102
  //info.Message = "Пересечение есть";
103
 
104
  return new Vector2(xx, yy);
105
 
106
}

__________________
Иван Топорышкин пошел на охоту,
С ним пудель пошел, перепрыгнув забор,
Иван, как бревно провалился в болото,
А пудель в реке утонул, как топор.

Отредактировано FiEctro 02-01-2024 в 19:18

Сообщить модератору | | IP: Записан
Сообщение: 218574

Старое сообщение 02-01-2024 19:01
- За что?
 XaeroX
Crystice Softworks

Дата регистрации: Oct 2005
Проживает: Торонто
Сообщений: 34491
Нанёс повреждений: 514 ед.
Возраст: 37

Рейтинг



Награды
 
[1 награда]


FiEctro
Решение любой задачи по геометрии начинается с хорошего чертежа.

__________________
Правдой дорожить, лжи не потакать,
Дальних не судить, ближним помогать,
С тишиной сойтись на исходе дня
Научи меня, Родина моя!

Сообщить модератору | | IP: Записан
Сообщение: 218576

Старое сообщение 02-01-2024 20:24
-
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 32132
Нанёс повреждений: 392 ед.

Рейтинг



FiEctro найди сперва пересечение луча с плоскостью. А потом уже делай проверки как бы ограничить эту плоскость.
Я бы посоветовал ограничивающие объемы, но имхо для 2д это какой-то оверкилл.
Ну или переформулируй задачу, может тебе нужно совсем другое.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Сообщить модератору | | IP: Записан
Сообщение: 218577

Старое сообщение 02-01-2024 20:35
-
FiEctro
Кот Арсис

Дата регистрации: Aug 2006
Проживает: код
Сообщений: 12832
Возраст: 32

Рейтинг



Есть луч в 3хмерном пространстве мне нужно получить координаты пересечения этим лучом границ экрана.

Цитата:
XaeroX писал:
Решение любой задачи по геометрии начинается с хорошего чертежа.


А толку если я формул не знаю.

__________________
Иван Топорышкин пошел на охоту,
С ним пудель пошел, перепрыгнув забор,
Иван, как бревно провалился в болото,
А пудель в реке утонул, как топор.

Отредактировано FiEctro 02-01-2024 в 21:04

Сообщить модератору | | IP: Записан
Сообщение: 218578

Старое сообщение 02-01-2024 21:03
- За что?
 XaeroX
Crystice Softworks

Дата регистрации: Oct 2005
Проживает: Торонто
Сообщений: 34491
Нанёс повреждений: 514 ед.
Возраст: 37

Рейтинг



Награды
 
[1 награда]


Цитата:
FiEctro писал:
А толку если я формул не знаю.

Выше шанс, что те, кто знают формулы, помогут. Потому что чертежи рисовать - всем влом, не одному тебе.

Добавлено 02-01-2024 в 19:08:

Цитата:
FiEctro писал:
Есть луч в 3хмерном пространстве мне нужно получить координаты пересечения этим лучом границ экрана.

Так я не понял, вопрос о пересечении двух двумерных отрезков, или о пересечении трёхмерного луча с фрустумом?

Добавлено 02-01-2024 в 19:54:

Цитата:
FiEctro писал:
Находил нечто подобное:
https://www.interestprograms.ru/sou...e-dvuh-otrezkov

Вот по этой ссылке всё неплохо расписано. Что именно не работает?
Допустим, у тебя есть отрезки AB и CD. Координаты точек A, B, C и D, соответственно, (Ax, Ay), (Bx, By), (Cx, Cy) и (Dx, Dy).
Сначала находим параметрические уравнения прямых, на которых лежат отрезки. В общем виде уравнение такое:
M = P*t + M0
Где M0(x0, y0) начальная точка, P - направляющий вектор, t - параметр.
Нам нужно найти значение параметров в точке пересечения отрезков, и если 0<= t <=1, то отрезки пересекаются.
Уравнения будут такие:
M1 = (B-A)*t1 + A
M2 = (D-C)*t2 + C
Точка пересечения это M1 = M2. Тогда:
(B-A)*t1 + A = (D-C)*t2 + C
Решаем систему линейных уравнений, находим t1 и t2. Отрезки пересекаются, если 0<= t1 <=1 и 0<= t2 <=1. Если уравнения оказываются линейно зависимыми, то t найти нельзя и пересечения нет. Работает и для двумерного, и для трёхмерного случая (в последнем случае система будет из трёх уравнений, по x, y и z).

__________________
Правдой дорожить, лжи не потакать,
Дальних не судить, ближним помогать,
С тишиной сойтись на исходе дня
Научи меня, Родина моя!

Сообщить модератору | | IP: Записан
Сообщение: 218581

Старое сообщение 03-01-2024 00:54
-
FiEctro
Кот Арсис

Дата регистрации: Aug 2006
Проживает: код
Сообщений: 12832
Возраст: 32

Рейтинг



Цитата:
Дядя Миша писал:
FiEctro найди сперва пересечение луча с плоскостью. А потом уже делай проверки как бы ограничить эту плоскость.
Я бы посоветовал ограничивающие объемы, но имхо для 2д это какой-то оверкилл.
Ну или переформулируй задачу, может тебе нужно совсем другое.


Я первоначально так и хотел, но потом понял что с этим слишком много лишних телодвижений. Сначала считать пересечения с плоскостью, потом как то ещё думать как их ограничивать, потом ещё вычленять нужные координаты, нафиг надо этот геморой.

Цитата:
XaeroX писал:
Так я не понял, вопрос о пересечении двух двумерных отрезков, или о пересечении трёхмерного луча с фрустумом?


Да разницы никакой, и так и так 4 отрезка получается. Действительно я вчера тоже переделал на получение координат границ экрана путём пересечения фрустума с плоскостью, до этого пытался конвертировать отрезки в экранное пространство, и что то оно не очень хорошо работало.

Цитата:
XaeroX писал:
Вот по этой ссылке всё неплохо расписано. Что именно не работает?


Да такое ощущение что половина случаев когда они точно должны пересекаться, он не видит и выдаёт что они не пересекаются. Но как говорил выше, сейчас попробую переделать и заменить экранные координаты на координаты с фрустума. Так думаю должно всё работать, а там посмотрим.

Цитата:
XaeroX писал:
Допустим, у тебя есть отрезки AB и CD. Координаты точек A, B, C и D, соответственно, (Ax, Ay), (Bx, By), (Cx, Cy) и (Dx, Dy).
Сначала находим параметрические уравнения прямых, на которых лежат отрезки. В общем виде уравнение такое:
M = P*t + M0
Где M0(x0, y0) начальная точка, P - направляющий вектор, t - параметр.
Нам нужно найти значение параметров в точке пересечения отрезков, и если 0<= t <=1, то отрезки пересекаются.
Уравнения будут такие:
M1 = (B-A)*t1 + A
M2 = (D-C)*t2 + C
Точка пересечения это M1 = M2. Тогда:
(B-A)*t1 + A = (D-C)*t2 + C
Решаем систему линейных уравнений, находим t1 и t2. Отрезки пересекаются, если 0<= t1 <=1 и 0<= t2 <=1. Если уравнения оказываются линейно зависимыми, то t найти нельзя и пересечения нет. Работает и для двумерного, и для трёхмерного случая (в последнем случае система будет из трёх уравнений, по x, y и z).


Уже более менее понятнее, спасибо. Хотя вроде мало чем отличается от того что по ссылке. Ладно попробую, тогда можно будет думать что дальше.

Добавлено 03-01-2024 в 14:38:

Да, вроде это работает. Похоже я накосячил просто с входными данными.
Делаю это так:
C++ Source Code:
1
private static bool SegmentsIntersection(Vector2 p1, Vector2 p2, Vector2 p3, Vector2 p4, out Vector2 intersection)
2
{
3
  intersection = new Vector2();
4
 
5
  float d = (p2.x - p1.x) * (p4.y - p3.y) - (p2.y - p1.y) * (p4.x - p3.x);
6
  if (d == 0.0f) return false; // Параллельные линии
7
 
8
  float u = ((p3.x - p1.x) * (p4.y - p3.y) - (p3.y - p1.y) * (p4.x - p3.x)) / d;
9
  float v = ((p3.x - p1.x) * (p2.y - p1.y) - (p3.y - p1.y) * (p2.x - p1.x)) / d;
10
 
11
  if (u < 0.0f || u > 1.0f || v < 0.0f || v > 1.0f) return false; // Пересечение вне отрезков
12
 
13
  intersection.x = p1.x + u * (p2.x - p1.x);
14
  intersection.y = p1.y + u * (p2.y - p1.y);
15
 
16
  return true;
17
}

__________________
Иван Топорышкин пошел на охоту,
С ним пудель пошел, перепрыгнув забор,
Иван, как бревно провалился в болото,
А пудель в реке утонул, как топор.

Отредактировано FiEctro 03-01-2024 в 11:52

Сообщить модератору | | IP: Записан
Сообщение: 218585

Старое сообщение 03-01-2024 11:38
- За что?
Тема: (Опционально)
Ваш ответ:



Переводчик транслита


[проверить длину сообщения]
Опции: Автоматическое формирование ссылок: автоматически добавлять [url] и [/url] вокруг интернет адресов.
Уведомление по E-Mail: отправить вам уведомление, если кто-то ответил в тему (только для зарегистрированных пользователей).
Отключить смайлики в сообщении: не преобразовывать текстовые смайлики в картинки.
Показать подпись: добавить вашу подпись в конец сообщения (только зарегистрированные пользователи могут иметь подписи).

Временная зона GMT. Текущее время 06:51. Новая тема    Ответить
  Предыдущая тема   Следующая тема
HLFX.Ru Forum HLFX.Ru Forum > Наш форум > Технические вопросы > Найти точку пересечения 2х отрезков
Версия для печати | Отправить тему по E-Mail | Подписаться на эту тему

Быстрый переход:
Оцените эту тему:

Правила Форума:
Вы not можете создавать новые темы
Вы not можете отвечать в темы
Вы not можете прикреплять вложения
Вы not можете редактировать ваши сообщения
HTML Код ВЫКЛ
vB Код ВКЛ
Смайлики ВКЛ
[IMG] Код ВКЛ
 

< Обратная связь - HLFX.ru >

На основе vBulletin
Авторское право © 2000 - 2002, Jelsoft Enterprises Limited.
Дизайн и программирование: Crystice Softworks © 2005 - 2024