С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

как найти точку пересечения двух отрезков, если даны координаты начала и конца обеих
0
Лучшие ответы (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. Так вот, нужно найти...

6
silent_1991
Эксперт С++
4989 / 3046 / 149
Регистрация: 11.11.2009
Сообщений: 7,028
Завершенные тесты: 1
18.10.2010, 05:53 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
http://e-maxx.ru/algo/lines_intersection
5
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
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), то отрезки пресекаются, иначе не пересекаются.
2
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,200
Завершенные тесты: 1
18.10.2010, 17:11 #4
Когда у системы не единственное решение, то тоже могут пересекаться (на одной прямой).
0
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
19.10.2010, 05:35 #5
Я исходил из определения:
Точкой пересечения называется единственная в своих окрестностях общая точка двух линий при условии, что разделённые этой точкой части каждой из линий располагаются по разные стороны от второй линии
. Если отрезки расположены на одной прямой, то этому определению соответствует только случай, когда конец одного треугольника совпадает с концом другого, но два других конца не только различны, но и расположены на противоположных сторонах развёрнутого угла с вершиной в совпадающем конце отрезков: a1=a2 лежит между b1 и b2, a1=b2 лежит между b1 и a2, b1=a2 лежит между a1=b2, или b1=b2 лежит между a1 и a2. Эти 4 случая уже предусмотрены. Если же полное или частичное наложение отрезков считать за пересечение, то просто метод решения системы должен выявлять случай множественного решения отдельно от случая отсутствия решений.
0
Anton Nazarov
0 / 0 / 0
Регистрация: 18.04.2011
Сообщений: 2
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 / 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;
0
23.08.2015, 02:30
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) вне окружности. Найти точку пересечения одной из касательных с...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

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