Пересечение отрезков
На плоскости заданы два отрезка a и b, a - точками A1(A1x,A1y) и A2(A2x,A2y),
а b - точками B1(B1x,B1y) и B2(B2x,B2y). Найти и напечатать возможную точку их
пересечения C(Cx,Cy).
Задача в основном на геометрию, программирования особого здесь нет.
Рассмотрим первый отрезок a. Уравнение прямой, на которой он лежит можно
записать так:
xa = A1x + ta (A2x - A1x)
ya = A1y + ta (A2y - A1y)
Здесь, A1x,A1y,A2x,A2y - суть константы,
xa,ya - суть точки отрезка, при ta пробегающем значения от [0,1]
Аналогично для отрезка b:
xb = B1x + tb (B2x - B1x)
yb = B1y + tb (B2y - B1y)
Таким образом, приравнивая соответствующие координаты, получаем задачу нахождения параметров ta,tb, при которых бы
выполнялись равенства:
A1x + ta (A2x - A1x) = B1x + tb (B2x - B1x)
A1y + ta (A2y - A1y) = B1y + tb (B2y - B1y)
После разрешения системы относительно ta,tb получаем:
ta (A1x - A2x) + tb (B2x - B1x) = A1x - B1x
ta (A1y - A2y) + tb (B2y - B1y) = A1y - B1y
А это есть система из двух линейных урвавнений относительно ta,tb.
Известно, что система:
a1 x + b1 y = c1
a2 x + b2 y = c2
имеет следующее решение:
x = dx/d
y = dy/d,
где d - определитель матрицы,
d = a1b2 - a2b1,
dx = c1b2 - c2b1,
dy = a1c2 - a2c1.
В нашей системе относительно ta,tb:
a1 = A1x - A2x
b1 = B2x - B1x
c1 = A1x - B1x
a2 = A1y - A2y
b2 = B2y - B1y
c2 = A1y - B1y
откуда легко находится d,dx,dy.
Если d отличен от нуля, то система имеет единственное решение. Правда, следует помнить, что искомые ta,tb - параметрически задают
отрезки только если они лежат в диапазоне [0,1], в противном случае точка пересечения прямых, на которых лежат отрезки, находится вне этих самых отрезков.
Если d равен нулю, а хотя бы один из dx,dy отличен от нуля, то отрезки лежат на параллельных прямых, или как говорят математики,
они коллинеарны. Если же все три d,dx,dy равны нулю, то это значит, что отрезки лежат на одной и той же прямой, где опять возможны три
случая - либо отрезки не перекрываются, либо перекрываются в одной точке, либо перекрываются в бесконечном множестве точек.
Несколько слов о программе. Исходные данные в виде восьми координат считываются из файла input.txt. Вместо сравнения d с нулем (if (d=0) ...) используется сравнение с малым числом Eps. Сделано это для того, чтобы не делить на очень малые числа. В вещественных представлениях числа 0 зачастую присутствуют что-нибудь вроде 1Е-12, и формального равенства с нулем нет, но фактически это самый что ни на есть 0.
const eps = 0.000001;
type point = object
x,y:real;
procedure setPoint(xp,yp:real);
end;
procedure point.setPoint(xp,yp:real);
begin
x:=xp;
y:=yp;
end;
var a1,a2,b1,b2,c:point;
d,da,db:real;
var
x1,y1,x2,y2: real;
buf: text;
procedure readPoints;
begin
assign(buf, 'input.txt'); reset(buf);
readln(buf, x1, y1, x2, y2);
a1.setPoint(x1,y1);
a2.setPoint(x2,y2);
readln(buf, x1, y1, x2, y2);
b1.setPoint(x1,y1);
b2.setPoint(x2,y2);
close(buf);
end;
function checkIntersection:shortint;
var d,da,db,ta,tb: real;
begin
d :=(a1.x-a2.x)*(b2.y-b1.y) - (a1.y-a2.y)*(b2.x-b1.x);
da:=(a1.x-b1.x)*(b2.y-b1.y) - (a1.y-b1.y)*(b2.x-b1.x);
db:=(a1.x-a2.x)*(a1.y-b1.y) - (a1.y-a2.y)*(a1.x-b1.x);
writeln('d=',d:12:4,' da=',da:12:4,' db=',db:12:4);
if (abs(d)<eps) then
checkIntersection := 0
else
begin
ta:=da/d;
tb:=db/d;
if (0<=ta) and (ta<=1)
and (0<=tb) and (tb<=1)
then
begin
c.setPoint(a1.x+ta*(a2.x-a1.x),a1.y+ta*(a2.y-a1.y));
checkIntersection := 1
end
else checkIntersection := -1;
end;
end;
begin
readPoints;
writeln;
case checkIntersection of
-1: write('otrezki ne peresekayutca');
0: write('otrezki na paeallelnyh pryamyh');
1: write('tochka peresecheniya: (',c.x:0:3, ',',c.y:0:3,')');
end;
end.
|
