 |
 |
 |
 |
|
 |
 |
160
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.
И наконец, самый тонкий момент - это частные случаи, когда отрезки ломаной оказываются на одной
прямой линии. В этом случае отрезки либо вообще не пересекаются, либо имеют общую часть, которую
можно определить из взаимного расположения отрезков на прямой.
В последнем случае общая часть отрезков находится из взаиморасположения отрезков [(х1, у1) - (х2,
у2)] и [(х3, у3) - (х
4
, у
4
)] на прямой. В данной ситуации взаиморасположение вершин отрезков можно
выяснить, вычислив взаиморасположение между ними на прямой относительно отрезка [(х1, у1) - (х2,
у2)] по следующим формулам:
d1 = 0;
d2 = (х2 – х1)
(х2 – х1) + (у2 – у1)
(у2 - 1);
d3 = (х3 – х1)
(x2 – х1) + (у3 - у1)
(у2 - 1);
d
4
= (х
4
– х1)
(х2 – х1) + (у
4
– y1)
(y2 - 1).
Если d2 < min
(d3, d
4
) или max (d3, d
4
) < 0, то отрезки не пересекаются. В противном случае
необходимо выделить и отбросить две крайние точки, и тогда оставшиеся две точки зададут общую
часть этих отрезков.
Опираясь на эти математические факты можно приступить к составлению алгоритмов и
программы. Приведем программу, в которой установлено максимальное число точек nt = 200. Реальное
число точек устанавливается при вводе исходных данных из перечня операторов
data, записанных в
конце текста программы.
самопересечение ломаной
nt = 200
dim x(nt), y(nt)
gosub wod 'ввод данных
? «точки пересечения:»
np = 0 'число пересечении
for k = 1 to nt - 1
xl = x(k): yl = y(k)
x2 = x(k + I): y2 = y(k + 1)
for 1 = k + 1 to nt - 1
x3 = x(I): y3 = y(I)
х4 = x(I + 1): y4 = y(I + 1)
gosub pint 'пересечение
next 1
next k
if np = 0 then ? «отсутствуют»
end
pint:
точка пересечения: