Как рассчитать, где пересекаются два отрезка? ⇐ C++

[Anonymous]

Я применил формулу пересечения отрезков линии от GeeksForGeeks. Она отлично работает, но мне также нужно знать точку пересечения этих двух отрезков линии. Как я могу изменить код, чтобы сделать это? (С++)

Сначала идет класс Point (на самом деле это просто двухмерный вектор)

#include использование пространства имен std; структура Point { интервал х; интервал y; }; Эта функция проверяет, находятся ли две точки на одном сегменте.

// Учитывая три коллинеарные точки p, q, r, функция проверяет, // точка q лежит на отрезке 'pr' bool onSegment (точка p, точка q, точка r) { if (q.x = min(p.x, r.x) && q.y = min(p.y, r.y)) вернуть истину; вернуть ложь; } Этот поиск вращения упорядоченного триплета.

// Чтобы найти ориентацию упорядоченного триплета (p, q, r). // Функция возвращает следующие значения // 0 --> p, q и r коллинеарны // 1 --> По часовой стрелке // 2 --> Против часовой стрелки int ориентация (точка p, точка q, точка r) { // См. https://www.geeksforgeeks.org/orientati ... ed-points/. // для получения подробной информации о приведенной ниже формуле. int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); если (значение == 0) вернуть 0; // коллинеарно вернуть (значение > 0)? 1:2; // по часовой стрелке или против часовой стрелки } // Основная функция, которая возвращает true, если сегмент линии 'p1q1' // и 'p2q2' пересекаются. И, наконец, функции, проверяющие пересечение. Но где это произошло?
bool doIntersect(Точка p1, Точка q1, Точка p2, Точка q2) { // Найдите четыре ориентации, необходимые для общего и // Особые случаи int o1 = ориентация (p1, q1, p2); int o2 = ориентация (p1, q1, q2); int o3 = ориентация (p2, q2, p1); int o4 = ориентация (p2, q2, q1); // Общий случай если (o1 != o2 && o3 != o4) вернуть истину; // Особые случаи // p1, q1 и p2 коллинеарны и p2 лежит на отрезке p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) возвращает true; // p1, q1 и q2 коллинеарны и q2 лежит на отрезке p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) возвращает true; // p2, q2 и p1 коллинеарны и p1 лежит на отрезке p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) возвращает true; // p2, q2 и q1 коллинеарны и q1 лежит на отрезке p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) возвращает true; вернуть ложь; // Не падает ни в одном из вышеперечисленных случаев }