 |
 |
 |
 |
|
 |
 |
124
отрезок пересечения:
[0.2, 0] - [0.8, 0]
Для систематического конструирования алгоритмов и программы необходима разработка
сценария диалога и описание метода решения поставленной геометрической задачи.
Сценарий
точек: <n>
координаты точек:
<k>: <x> <у>
……..
точки пересечения:
отрезок: <k> - <k+l> *
отрезок: <1> - <1+1>
точка: <х> <у>
………
отсутствуют
Метод решения данной задачи может быть основан на вычислении точек пересечения от-
резков (х1, у1) - (x2, у2) и (х3, y3) - (х
4
, y
4
) как точек пересечения линий, проходящих через заданные
отрезки, с помощью системы уравнений:
(y2 – y1 )
( x – x1) - (x2 – x1)
(y – у1) = 0;
(у
4
– у3)
(x – x3) - (x
4
– x3)
(у – y3) = 0.
Решение этих уравнений может быть проведено вычислением определителей D, D
x
, D
y
приведенной системы уравнений:
(у2 – у1)
х
- (х2 – х1)
у = (у2 – y1)
х1 - (x2 – x1)
y1;
(у
4
– y3)
х - (х
4
– х3)
у
= (у
4
– у3)
х3- (x
4
– x3)
y3,
для которой будет справедлив следующий набор расчетных формул:
х = D
x
/D;
у = D
y
/D;
D = (у2 - у1)
(х
4
- x3) - (x2 - x1)
(y
4
- y3);
D
x
=
(y2 - y
l
)
x
l
- (х2 – x1)
y1
- (x
4
– х3) - (x2 – x1)
[(y
4
– y3)
x3 - (х
4
– х3)
y3
;
D
y
= (у2 - у1)
(у
4
– у3)
х3 - (x
4
- x3)
у3
- [(у2 – y1)
x1 - (х2 – x1)
y1]
(y
4
– y3).
Факт пересечения пар отрезков может быть установлен из этих же уравнений подстановкой
в правые части координат точек альтернативного отрезка и сравнением значений этих выражений.
А именно отрезок [(х3, у3) - (х
4
, у
4
)] пересекает линию, проходящую через отрезок [(x1,
y1)
- (х2,
у2)], если эти выражения имеют разные знаки:
(у2 - у1)
(х3 – x1) - (х2 – х1)
(y3 – у1)
(у2 - у1)
(х
4
– x1) - (х2 – x1)
(y
4
– y1)
0.
Соответственно, отрезок [(х1, у1) - (х2, у2)] пересекает линию, проходящую через отрезок
[(х3, у3) - (х
4
, у
4
)], если аналогичные выражения имеют разные знаки:
(у
4
– у3)
(х1 – х3) - (х
4
– х3)
(у1 – у3)
(у
4
– у3)
(х2 – х3) - (х
4
– х3)
(у2 – у3)
0.
И наконец, самый тонкий момент - это частные случаи, когда отрезки ломаной оказывают-
ся на одной прямой линии. В этом случае отрезки либо вообще не пересекаются, либо имеют об-
щую часть, которую можно определить из взаимного расположения отрезков на прямой.