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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 145, средняя оценка - 4.94
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
#1

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

17.10.2010, 22:20. Просмотров 19462. Ответов 6
Метки нет (Все метки)

как найти точку пересечения двух отрезков, если даны координаты начала и конца обеих
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.10.2010, 22:20
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти точку пересечения двух отрезков (C++):

На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков - C++
Помогите пожалуйста понять, что от меня хотят и какой(как) разработать алгоритм для решения этой задачи. На прямой своими концами...

Координаты точки пересечения двух отрезков - C++
День добрый уважаемые читатели форума. Разбираю задачу по расчету Координаты точки пересечения двух отрезков и столкнулся с проблемой. ...

Найти точку пересечения отрезка с прямой - C++
Найти точку пересечения отрезка, заданного точками (х1;y1) и (x2;y2) с прямой, перпендикулярной данному отрезку, проходящей через точку...

Найти точку пересечения прямой с плоскостью - C++
Зарание спасибо.)

Равнобедренная трапеция - найти точку пересечения боковых сторон - C++
Равнобедренная трапеция задана координатами вершин. Найти точку пересечения боковых сторон. На С++. заранее благодарю.

Найти точку пересечения отрезка и перпендикуляра, опущенного на отрезок из точки - C++
Привет! Помогите двоишнику, я же тупой батхэд :D! Есть отрезок, заданный двумя точками P1 и P2. Есть точка P3. Так вот, нужно найти...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
18.10.2010, 05:53 #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
http://e-maxx.ru/algo/lines_intersection
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
2788 / 1602 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
18.10.2010, 17:11 #4
Когда у системы не единственное решение, то тоже могут пересекаться (на одной прямой).
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);
            }
        }
Сергей Тульский
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;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2015, 02:30
Привет! Вот еще темы с ответами:

Найти координаты точек пересечения двух кругов - C++
Помогите, пожалуйста, решить такую задачу, очень нужен код ... С клавиатуры вводятся радиусы и координаты центров двух кругов. Найти...

Как найти точки пересечения двух синусоид? - C++
Есть две синусоиды вида: y = a + b*sin(c*x + d) a,b,c,d - постоянные. x - в заданном интервале, допустим от -10 до +10. Нужно найти...

Найти точку соприкосновения двух окружностей - C++
Как можно найти точку соприкосновения двух окружностей, если заданы их координаты центра и радиус? У меня движутся две окружности навстречу...

Вычислительная геометрия (Даны координаты центра, R окружности, координаты точки вне окруж-ти. Найти точку пересечения одной из касательных с окруж-ю) - C++
Даны координаты центра (xc,yc) и радиус R окружности, координаты точки (x,y) вне окружности. Найти точку пересечения одной из касательных с...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
23.08.2015, 02:30
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru