Применение паскаля в геометрии

Posted by Alar under Статьи

Часть 0. Intro.

    Еще в самом детстве, когда я начал изучать Паскаль, я запомнил цитату из детской книжки примерно такого содержания: “Паскаль – универсальный язык программирования подходящий для решения самых различных задач”. Когда человек впервые сталкивается с программированием на Паскале, одна из первых его мыслей после прочтения таких строк будет “А в чем же заключается его универсальность?”. На самом деле я когда более углубленно изучил паскаль решил, что это определение абсолютно правдивое. И действительно Паскаль можно применить для решения абсолютно любых задач. В этой статье я расскажу о там как можно использовать Паскаль для решения геометрических задач. Для примера возьмем задание которое звучит так: “По координатам точки и вершин треугольника определить, принадлежит ли точка этому треугольнику”.

Часть 1. Теория.

    Начнем с того, каким образом это вообще можно сделать. Есть как минимум два варианта решения этой задачи. Их очень трудно объяснить обычным текстом, но я попробую это сделать, а для наглядности буду обращаться к рисункам. Итак. Вариант первый. Сразу предлагаю посмотреть на рисунок “Теория. Вариант 1″. Дан треугольник ABC и искомая точка X. Чтобы определить принадлежит ли точка треугольнику нужно проделать следующие действия:

1. Найти площадь треугольника ABC.
2. Найти площади треугольников ABX, BCX и ACX.
3. Сравнить. Если площадь треугольника ABC равна сумме площадей ABX, BCX и ACX, значит точка принадлежит треугольнику, иначе – нет.

    Второй вариант несколько сложнее в понимании. Смотрим рисунок “Теория. Вариант 2″. Ситуация такая же: ABC – треугольник, X – точка.

1. Находим площадь треугольника ABC.
2. Находим расстояние от точки X до каждой из вершин треугольника.
3. Выбираем наименьшее из них. (В данном случае BX)
4. Находим площадь треугольника с новой точкой вместо ближайшей. (Здесь XC)
5. Сравниваем. Если площадь первого треугольника больше площади второго, значит точка не принадлежит треугольнику, иначе – принадлежит.

    По сложности реализации оба варианта примерно одинаковы, но дело в том, что во втором варианте есть небольшой процент неточности – когда точка лежит очень близко к грани треугольника, но не принадлежит ему. Поэтому подробно рассмотрим только первый вариант.

Часть 2. Практика.

    С выбором пути решения мы определились. Но начать, я считаю, надо с того что в обоих случаях мы находим ответ через площадь. А как найти площадь по координатам точек? Ответ есть. Существует такая формула Герона.

Квадратный корень из p(p-x)(p-y)(p-z)

    Где p – полупериметр, x,y и z – длины сторон. Длину сторон же находятся по формуле длины вектора. Итак. Начнем. Эта стать предполагает, что читатель имеет общее представление о программировании на языке Паскаль. Первые строчки кода выглядят так:

program Treugolnik;
var q,w,p,ax,bx,cx,dx,ay,by,cy,dy:real;
   per1,per2,per3,per4:real;

    Переменные q,w промежуточные. В них будут храниться временные значения координат. Переменные ax,bx…cy,dy – координаты вершин треугольника и искомой точки. Переменные per1…per4 и p будут служить для хранения площадей треугольников. Здесь нет ничего сложного. Продолжим программу. Сначала напишем процедуру получения координат с клавиатуры. Она выглядит так:

procedure Zapoln;
begin
write(’Koordinaty A ‘);
readln(ax, ay);
write(’Koordinaty B ‘);
readln(bx, by);
write(’Koordinaty C ‘);
readln(cx, cy);
write(’Koordinaty D ‘);
readln(dx, dy);
end;

    Здесь надеюсь тоже все понятно. Координаты точки будут вводиться через пробел, по нажатии на Enter переход к следующей точке. Итак, мы получили координаты точек треугольников. Теперь получим их площади.


procedure Ploshad(n:integer);
  var d1,d2,d3,per:real;
begin
  d1:=sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
  d2:=sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by));
  d3:=sqrt((ax-cx)*(ax-cx)+(ay-cy)*(ay-cy));
  per:=(d1+d2+d3)/2;
  per:=sqrt(per*(per-d1)*(per-d2)*(per-d3));
  if n=1 then per1:=per else
  if n=2 then per2:=per else
  if n=3 then per3:=per else
  if n=4 then per4:=per;
end;

    sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by)) – формула нахождения длины вектора AB. sqrt(per*(per-d1)*(per-d2)*(per-d3)) – та самая формула Герона. Теперь при вызове этой процедуры мы будем указывать номер нужного треугольника. 1 – главный треугольник, 2-4 – треугольники образованные точкой. Теперь нам нужно найти площади треугольников образованных точкой. Для этого Будем временно подставлять вместо координат одной из вершин координаты точки D.

procedure Zamena(x:integer);
begin
if x=1 then
   begin
   q:=cx;
   w:=cy;
   cx:=dx;
   cy:=dy;
   end else
if x=2 then
   begin
   q:=ax;
   w:=ay;
   ax:=dx;
   ay:=dy;
   end else
if x=3 then
   begin
   q:=bx;
   w:=by;
   bx:=dx;
   by:=dy;
   end;
end;

    Этой процедуре мы передаем номер операции. Я условно принял, что нахождение площади ABD – 1, BCD – 2 и ACD – 3. В переменные q и w мы вводим временные координаты точки, чтобы потом можно было их восстановить. Далее идет собственно сама процедура сравнения.

procedure Sravn;
begin
  if per1 = p then
  Writeln(’Yes’) else
  Writeln(’No’); end;

    Здесь все до безобразия просто. Я лишь поясню, что per1 – это площадь главного треугольника, а p – сумма площадей промежуточных треугольников. Но если мы будем сравнивать по этим данным, то ответ будет всегда отрицательным, так как после всех операций где-то далеко после запятой они все-таки расходятся. Так что нам еще понадобится функция округления до сотых.

function Okrug(z:real):real;
  var a:integer;
begin
  z:=z/10*1000;    // После этого в целой части останутся первые 3 цифры числа.
  a:=round(z);     // Получаем целую часть, т.е. отбрасываем все ненужное.
  z:=a/100;    / Делим на 100 и получаем 2 знака после запятой.
  Okrug:=z;
end;

Вот. Написание всех необходимых процедур и функций закончено, теперь можно переходить к исполняемой части программы.

begin
Zapoln; // Получаем значения с клавиатуры.
Ploshad(1); // Теперь в per1 находится площадь главного треугольника.
Zamena(1); // Вместо точки C подставляем D.
Ploshad(2); // Теперь в per2 находится площадь треугольника ABD.
cx:=q; // Возвращаем точке C
cy:=w; // ее координаты.
p:=per2; // Пока сумма равна площади ABD.
Zamena(2); // Вместо точки A подставляем D.
Ploshad(3); // Теперь в per3 находится площадь треугольника BCD.
p:=p+per3; // Сумма равна площадь ABD + площадь BCD.
ax:=q; // Возвращаем точке A
ay:=w; // ее координаты.
Zamena(3); // Вместо точки B подставляем D.
Ploshad(4); // Теперь в per4 находится площадь треугольника ACD.
p:=p+per4; // Теперь p = ABD + BCD + ACD.
p:=Okrug(p); // Округляем сумму до сотых.
per1:=Okrug(per1); // Округляем площадь главного треугольника до сотых.
Sravn; // Сравниваем и выводим результат.
readln; // Ждем нажатия клавиши Enter.
end.

Часть 4. Outtro.

    Вот и все. Каждой строчке я попытался дать максимально понятное объяснение. Если сделать все как написано в этой статье, то в боевой проверке программа работает с большой точностью и не дает сбоев, за исключением ввода вместо координат текста. Но это уже не наше дело. Программа выдает правильный ответ в 100 случаях из 100, и это доказывает то, что Паскаль действительно “Универсальный язык программирования”.

автор: Aver