Выпуклость многоугольника
Постановка задачи
Задача, скорее, не на программирование, а на векторную алгебру. Итак, условие. Задан многоугольник. Требуется определить, является ли он выпуклым.
Для начала определимся, что есть выпуклый многоугольник. Многоугольник называется выпуклым, если любые две точки его периметра можно соединить отрезком, каждая точка которого лежит внутри многоугольника.
Здесь слева — выпуклый многоугольник, справа — нет.
 |
 |
Одним из критериев выпуклости является следующий.
В общем случае, произведение векторов в трехмерном пространстве находится по формуле:
![\[ \left [ \bar{a},\bar{b} \right ]=\begin{vmatrix} \bar{i} & \bar{j} & \bar{k} \\ x_{1} & y_{1} & z_{1} \\ x_{2} & y_{2} & z_{2} \\ \end{vmatrix}= \left ( y_{1}z_{2}-y_{2}z_{1} \right ) \bar{i} -\left (x_{1}z_{2}-x_{2}z_{1}\right ) \bar{j} +\left (x_{1}y_{2}-x_{2}y_{1} \right) \bar{k} \]](https://tux.org.ua/wp-content/ql-cache/quicklatex.com-612650f0273e7d123a33787910337487_l3.png "Rendered by QuickLaTeX.com")
Здесь i, j, k — орты декартовой системы (вектора единичной длины, сонаправленные с осями координат).
Однако, если мы рассматриваем вектора, лежащие в одной плоскости, то для этого случая z-составляющая векторов будет нулевой. Тогда наша формула выродится в:
![\[ \left [ a, b \right ]=\left (x_{1}y_{2}-x_{2}y_{1} \right)k \]](https://tux.org.ua/wp-content/ql-cache/quicklatex.com-cb9eb8de1a03771f6fe8a61001e7987e_l3.png "Rendered by QuickLaTeX.com")
Таким образом, мы должны обойти все пары соседних сторон-векторов и посмотреть, все ли их произведения одного знака. (То есть все ли значения разности произведений 
одного знака для всех i от 1 до N-1).
Итак алгоритм:
- Задаем N — количество вершин многоугольника
- Задаем (вводим или присваиваем) все вершины многоугольника
для всех i от 1 до N. - Полагаем многоугольник выпуклым Q=true.
- Вычисляем T=xNy1-x1yN
- Вычисляем Z=T/|T|, |T| — модуль числа Т.
- Полагаем P=1
- Для всех i от 1 до N-1 при условии что Q=true вычисляем:
- xi,yi
- xi+1,yi+1
- R=xiyi+1-xi+1yi
- P=P*Z*R/|R|, здесь |R| — модуль числа R.
- Если P<0, то Q=false
- Если Q=true — многоугольник выпуклый, иначе — нет.
Вычисление координат вектора, образованного сторонами многоугольника (xi, yi), хорошо производить в отдельной процедуре.
![\[x_{i}=P_{i+1}^{x}-P_{i}^{x}\]\[y_{i}=P_{i+1}^{y}-P_{i}^{y}\]](https://tux.org.ua/wp-content/ql-cache/quicklatex.com-d1bc625ca52a10832de97e01441d9ddc_l3.png "Rendered by QuickLaTeX.com")
Для N-ой вершины N+1-ая будет, естественно, первой.
Решение задачи
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
Program Vypuklost; const N=8; type point=record x,y:real; end; var Peaks:array[1..N] of point; i:byte; Q:boolean; T,Z,P:real; v1,v2:point; function Sign(r:real):shortint; const eps=0.0000001; begin if (abs(r)<eps) then Sign:=1 else Sign:=Round(r/abs(r)); end; Procedure GetVector(i:byte;var p:point); begin if (i=N) then begin p.x:=Peaks[1].x-Peaks[N].x; p.y:=Peaks[1].y-Peaks[N].y; end else begin p.x:=Peaks[i+1].x-Peaks[i].x; p.y:=Peaks[i+1].y-Peaks[i].y; end; end; BEGIN Peaks[1].x:= 0; Peaks[1].y:= 6; Peaks[2].x:=-4; Peaks[2].y:= 5; Peaks[3].x:=-5; Peaks[3].y:= 2; {Peaks[3].x:=-1; Peaks[3].y:= 1;} {невыпуклый } Peaks[4].x:=-5; Peaks[4].y:=-1; Peaks[5].x:=-2; Peaks[5].y:=-4; Peaks[6].x:= 4; Peaks[6].y:=-3; Peaks[7].x:= 6; Peaks[7].y:= 1; Peaks[8].x:= 4; Peaks[8].y:= 5; {Peaks[8].x:= 1; Peaks[8].y:= 1;} {невыпуклый } GetVector(N,v1); GetVector(1,v2); T:=v1.x*v2.y-v2.x*v1.y; Z:=Sign(T); P:=1.0; i:=1; Q:=true; while (Q and (i<N)) do begin GetVector(i,v1); GetVector(i+1,v2); T:=v1.x*v2.y-v2.x*v1.y; P:=P*Z*Sign(T); writeln('i=',i,'; T=',T,'; P=',P); if (P<0) then Q:=false; inc(i); end; if Q then writeln('Многоугольник выпуклый.') else writeln('Многоугольник невыпуклый.'); END. |