Учебно-методическое пособие. Алматы, 2017 ббк

3.3.1 Многоугольники

Многоугольник (на плоскости), геометрическая фигура, ограниченная замкнутой ломаной линией, без самопересечений. Звенья ломаной линии называются сторонами многоугольника, а их концы — вершинами многоугольника. По числу вершин различают треугольники, четырехугольники и т. д. Многоугольник называется выпуклым, если он весь лежит по одну сторону от прямой, несущей любую из его сторон, и невыпуклым — в противном случае (Рис 3.5).

Рис 3.5
Попробуем написать программу, которая определяет выпуклый многоугольник или нет. Пусть координаты вершин треугольника заданы в порядке обхода его по часовой стрелке. Основываясь на определении выпуклости многоугольника, можно было бы предложить следующее решение:

1. 
   Определить уравнение прямой, проходящей через первую сторону.
   
2. 
   Определить лежат ли все остальные вершины многоугольника правее относительно прямой (см. рис 3.1).
   
3. 
   Если «ДА», то определяем уравнение прямой, проходящей через следующую сторону и преходим на пункт 2, если «НЕТ» выходим из подпрограммы.
   

Var

Begin

x[N+1]:=x[1];

y[N+1]:=y[1];

x[N+2]:=x[2];

y[N+2]:=y[2];

Rezalt:=’YES’;

i:=1;

{организуем цикл, пока не просмотренны все стороны или получен отрицательный результат}

Begin

{определяем коэффициенты уравнения прямой, проходящей через рассматриваемую сторону}

а:= y[i+1]- y[i];

b:= x[i]- x[i+1];

c:= -x[i]*(y[i+1]- y[i])+ y[i]*(x[i+1]- x[i]);

{определяем, не лежит ли следующая вершина левее прямой, если да то результат изменяется и происходит выход из цикла}

if (a*x[i+2]+b*y[i+2]+c)>0 then Rezalt:=’NO’;

{увеличиваем счетчик на единицу, для рассмотрения следующей стороны}

i:=i+1;

End;

End;

жүктеу/скачать 483.39 Kb.

Достарыңызбен бөлісу: