Navigation bar
  Print document Start Previous page
 125 of 144 
Next page End  

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 - хЗ) 
Сайт создан в системе uCoz