 |
 |
 |
 |
|
 |
 |
125
В последнем случае общая часть отрезков находится из взаиморасположения отрезков [(х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:
точка пересечения:
d213 = (у2 - yl)*(x3 - х1) - (х2 - х1)*(у3 - у1)
d214 = (у2 - у1)*(х4 - х1) - (х2 - х1)*(у4 - у1)
d431 = (у4 - у3)*(х1 - хЗ) - (х4 - х3)*(у1 - уЗ)
d432 = (у4 - у3)*(х2 - хЗ) - (х4 - х3)*(у2 - уЗ)
if d213*d2l4 > 0 or d431*d432 > 0 then
' нет пересечения
elseifd213*d214 < 0 or d431*d432 < 0 then
gosub tchki ' расчет точки
else ' отрезки на одной прямой
gosub lin 1
end if
return
tchki: ' расчет точки пересечения
np = np+1
? «отрезок:»; k; k + 1
? «отрезок:»; I; I + 1
D = (у2 - yl)*(x4 - хЗ) - (х2 - х1)*(у4 - уЗ)
Dx = [(у2 - у1)*х1 - (х2 - х1)*у1]*(х4 - хЗ)