HOME ПРИМЕРЫ THANKS НОВИЧКАМ ДОКИ LINKS JavaScript Mail


 
В этот день много лет назад...
29 марта. В 1998 году (26 лет назад) - Норвежцами спасен экипаж рыболовного судна "Кубанский рыбак" мурманской фирмы "Баренцфишкомпани".
 
 

Turbo Pascal Examples.
Пересечение отрезков

Графика:
Построение графика функции
Прыгающий по экрану мячик.
Качание маятника.
Вложенные цветные круги.
Броуновское движение. Использование объектов.
Матрицы и массивы:
Сортировка элементов массива.
Удаление одинаковых элементов.
Простой пример на поворот матрицы.
Сортировка методом Шелла. +функции измерения временных интервалов.
Проверка выпуклости многоугольника.
Перемоножение матриц
Вычисление определителя матрицы. Рекурсия.
Нахождение обратной матрицы.
Задача об автостоянке.
Рекурсия. Подземелье сокровищ.
Численные методы:
Задачка на определение угла между стрелками часов.
Проверка на принадлежность точки многоугольнику.
Нахождение точки пересечения двух отрезков на плоскости.
Сортировка методом Шелла. +функции измерения временных интервалов.
Сортировка методом "пузырька". Пример на динамические структуры данных. Связанные списки.
Нахождение корня функции методом половинного деления.
Вычисление арккосинуса
Нахождение суммы цифр натурального числа.
Работа с фалами:
Рекурсивное сканирование директорий.
Работа со строками:
Работа со словами в предложении с разделителями.
Простейший синтаксический анализатор для распознавания и вычисления многчлена.
Синтаксический анализатор для распознавания и вычисления многчлена.
Работа со строками: смена кодировки, удаление тегов из HTML текста, обработка
Переименование файлов из кириллицы в латиницу.
Выдача контекстной подсказки.
Частотный словарь символов.
Подсчет повторяющихся символов в строке.
Ссылочные переменные:
Моделирование стека.
Пасьянс "Косынка".
Игры:
Пасьянс "Косынка".
Игра "Питон"
Игра "Анацефал". Пример использования объектов.
Игра "Минное поле"
Большие проекты:
Электронная картотека (без исходника)


 
Пересечение отрезков
На плоскости заданы два отрезка 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;
{
returns
  1 if there is one intersection point "c"
  0 if chunks ar on parallel lines
-1 if there are no intersection points
}

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.


 

 

 

 

 

 

 


HOME