Форум программистов, компьютерный форум CyberForum.ru

Найти точку пересечения двух отрезков - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 145, средняя оценка - 4.94
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
17.10.2010, 22:20     Найти точку пересечения двух отрезков #1
как найти точку пересечения двух отрезков, если даны координаты начала и конца обеих
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
18.10.2010, 05:53     Найти точку пересечения двух отрезков #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
http://e-maxx.ru/algo/lines_intersection
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.10.2010, 07:36     Найти точку пересечения двух отрезков #3
По имеющимся точкам выводим параметрические уравнения обоих отрезков:
C++
1
2
x=a1.x+t1*(b1.x-a1.x)
y=a1.y+t1*(b1.y-a1.y)
и
C++
1
2
x=a2.x+t2*(b2.x-a2.x)
y=a2.y+t2*(b2.y-a2.y)
, объединяем их в систему:
C++
1
2
a1.x+t1*(b1.x-a1.x)=a2.x+t2*(b2.x-a1.x)
a1.y+t1*(b1.y-a1.y)=a2.y+t2*(b2.y-a2.y)
, переносим параметры влево, а свободные члены вправо:
C++
1
2
t1*(b1.x-a1.x)+t2*(a2.x-b1.x)=a2.x-a1.x
t1*(b1.y-a1.y)+t2*(a2.y-b1.y)=a2.y-a1.y
, решаем относительно t1, t2, если (t1>=0)&(t1<=1)&(t2>=0)&(t2<=1), то отрезки пресекаются, иначе не пересекаются. Если точки заданы не на плоскости, а в пространстве, то по имеющимся точкам выводим параметрические уравнения обоих отрезков:
C++
1
2
3
x=a1.x+t1*(b1.x-a1.x)
y=a1.y+t1*(b1.y-a1.y)
z=a1.z+t1*(b1.z-a1.z)
и
C++
1
2
3
x=a2.x+t2*(b2.x-a2.x)
y=a2.y+t2*(b2.y-a2.y)
z=a2.z+t2*(b2.z-a2.z)
, объединяем их в переопределённую систему из трёх уравнений с двумя неизвестными:
C++
1
2
3
a1.x+t1*(b1.x-a1.x)=a2.x+t2*(b2.x-a1.x)
a1.y+t1*(b1.y-a1.y)=a2.y+t2*(b2.y-a2.y)
a1.z+t1*(b1.z-a1.z)=a2.z+t2*(b2.z-a2.z)
, переносим параметры влево, а свободные члены вправо:
C++
1
2
3
t1*(b1.x-a1.x)+t2*(a2.x-b1.x)=a2.x-a1.x
t1*(b1.y-a1.y)+t2*(a2.y-b1.y)=a2.y-a1.y
t1*(b1.z-a1.z)+t2*(a2.z-b1.z)=a2.z-a1.z
, решаем относительно t1, t2, если (t1>=0)&(t1<=1)&(t2>=0)&(t2<=1), то отрезки пресекаются, иначе не пересекаются.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
18.10.2010, 17:11     Найти точку пересечения двух отрезков #4
Когда у системы не единственное решение, то тоже могут пересекаться (на одной прямой).
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
19.10.2010, 05:35     Найти точку пересечения двух отрезков #5
Я исходил из определения:
Точкой пересечения называется единственная в своих окрестностях общая точка двух линий при условии, что разделённые этой точкой части каждой из линий располагаются по разные стороны от второй линии
. Если отрезки расположены на одной прямой, то этому определению соответствует только случай, когда конец одного треугольника совпадает с концом другого, но два других конца не только различны, но и расположены на противоположных сторонах развёрнутого угла с вершиной в совпадающем конце отрезков: a1=a2 лежит между b1 и b2, a1=b2 лежит между b1 и a2, b1=a2 лежит между a1=b2, или b1=b2 лежит между a1 и a2. Эти 4 случая уже предусмотрены. Если же полное или частичное наложение отрезков считать за пересечение, то просто метод решения системы должен выявлять случай множественного решения отдельно от случая отсутствия решений.
Anton Nazarov
Сообщений: n/a
21.04.2011, 19:03     Найти точку пересечения двух отрезков #6
Есть готовая функция на C# для нахождения точки пересечения двух отрезков, заданных точками, один из которых горизонтальный или вертикальный, может кому пригодится. http://pastie.org/1819393

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 // нахождение точки пересечения отрезка, заданного точками p1 p2 c вертикальным/горизонтальным отрезком, заданным точками p3 p4
        public Point Crossing(Point p1, Point p2, Point p3, Point p4)
        {
            if (p3.X == p4.X)   // вертикаль
            {
                double y = p1.Y + ((p2.Y - p1.Y) * (p3.X - p1.X)) / (p2.X - p1.X);
                if (y > Math.Max(p3.Y, p4.Y) || y < Math.Min(p3.Y, p4.Y) || y > Math.Max(p1.Y, p2.Y) || y < Math.Min(p1.Y, p2.Y))   // если за пределами отрезков
                    return new Point(0, 0);
                else
                    return new Point(p3.X, (int)y);
            }
            else            // горизонталь
            {
                double x = p1.X + ((p2.X - p1.X) * (p3.Y - p1.Y)) / (p2.Y - p1.Y);
                if (x > Math.Max(p3.X, p4.X) || x < Math.Min(p3.X, p4.X) || x > Math.Max(p1.X, p2.X) || x < Math.Min(p1.X, p2.X))   // если за пределами отрезков
                    return new Point(0, 0);
                else
                    return new Point((int)x, p3.Y);
            }
        }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2015, 02:30     Найти точку пересечения двух отрезков
Еще ссылки по теме:

C++ Равнобедренная трапеция - найти точку пересечения боковых сторон
C++ Как найти точки пересечения двух синусоид?
Найти точку пересечения отрезка и перпендикуляра, опущенного на отрезок из точки C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Сергей Тульский
0 / 0 / 0
Регистрация: 21.02.2015
Сообщений: 2
23.08.2015, 02:30     Найти точку пересечения двух отрезков #7
type
edge = record
start_edge: record {Начальная Точка}
x,y: real;
end;
end_edge: record {Конечная точка}
x,y:real;
end;
end;
function Cross_Section(Edg1,Edg2: Edge): Boolean;
var a1,a2,
b1,b2,
c1,c2,
d,x,y,
al,mlt1,mlt2,mlt3,
max_min_minX,
min_max_maxX,
max_min_minY,
min_max_maxY: real;
flag1,flag2,flag3,flag4,flag5,flag6,flag7: Boolean;
begin
a1:=Edg1.StartEdge.y - Edg1.EndEdge.y;
b1:=Edg1.EndEdge.x - Edg1.StartEdge.x;
c1:=Edg1.StartEdge.x*Edg1.EndEdge.y - Edg1.EndEdge.x*Edg1.StartEdge.y;
a2:=Edg2.StartEdge.y - Edg2.EndEdge.y;
b2:=Edg2.EndEdge.x - Edg2.StartEdge.x;
c2:=Edg2.StartEdge.x*Edg2.EndEdge.y - Edg2.EndEdge.x*Edg2.StartEdge.y;
If a2<>0 then
al:=a1/a2
else
if b2<>0 then
al:=b1/b2
else
if c2<>0 then
al:=c1/c2;
mlt1:=al*a2;
mlt2:=al*b2;
mlt3:=al*c2;
If ((a1 = mlt1) and (b1 = mlt2) and (c1 = mlt3)) then
Result:=True
Else
begin
If (a1 = al*a2) and (b1 = al * b2) and (c1 <> al * c2) then
Result:=False
Else
begin
d:=a1*b2 - a2*b1;
x:=((-1*c1)*b2 - (-1*c2)*b1)/d;
y:=(a1*(-1*c2) - a2*(-1*c1))/d;
max_min_minX:=max(min(Edg1.StartEdge.x,Edg1.EndEdge.x),
min(Edg2.StartEdge.x,Edg2.EndEdge.x));
min_max_maxX:=min(max(Edg1.StartEdge.x,Edg1.EndEdge.x),
max(Edg2.StartEdge.x,Edg2.EndEdge.x));
max_min_minY:=max(min(Edg1.StartEdge.y,Edg1.EndEdge.y),
min(Edg2.StartEdge.y,Edg2.EndEdge.y));
min_max_maxY:=min(max(Edg1.StartEdge.y,Edg1.EndEdge.y),
max(Edg2.StartEdge.y,Edg2.EndEdge.y));
flag1:=round(max_min_minX) <= round(x);
flag2:=round(min_max_maxX) >= round(x);
flag3:=round(max_min_minY) <= round(y);
flag4:=round(min_max_maxY) >= round(y);
flag5:=flag1 and flag2;
flag6:=flag3 and flag4;
flag7:=flag5 and flag6;
If flag7 Then
Result:=True
Else
Result:=False;
end;
end;
end;
Yandex
Объявления
23.08.2015, 02:30     Найти точку пересечения двух отрезков
Ответ Создать тему
Опции темы

Текущее время: 01:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru