Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.64/135: Рейтинг темы: голосов - 135, средняя оценка - 4.64
387 / 279 / 53
Регистрация: 26.12.2009
Сообщений: 875
1

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

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

как найти точку пересечения двух отрезков, если даны координаты начала и конца обеих
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.10.2010, 22:20
Ответы с готовыми решениями:

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

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

Определение точки пересечения двух отрезков
#include "stdafx.h" #include <iostream> #include <cmath> using namespace std; struct line {...

Даны четыре точки на числовой оси A, B, C И D. найти длину пересечения отрезков AB И CD
Я только начал изучать, не могли бы подсказать метод построения решения этой задачи

6
Эксперт С++
5034 / 3094 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
18.10.2010, 05:53 2
Лучший ответ Сообщение было отмечено как решение

Решение

http://e-maxx.ru/algo/lines_intersection
5
4193 / 1785 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
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
2818 / 1628 / 252
Регистрация: 03.12.2007
Сообщений: 4,223
18.10.2010, 17:11 4
Когда у системы не единственное решение, то тоже могут пересекаться (на одной прямой).
0
4193 / 1785 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
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
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);
            }
        }
1 / 1 / 0
Регистрация: 21.02.2015
Сообщений: 2
23.08.2015, 02:30 7
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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;
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.08.2015, 02:30

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

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

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


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

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

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