Выпуклость многоугольника

tux 2012.10.08 Программирование https://tux.org.ua/?p=862 5598 0

Постановка задачи

Задача, скорее, не на программирование, а на векторную алгебру. Итак, условие. Задан многоугольник. Требуется определить, является ли он выпуклым.

Для начала определимся, что есть выпуклый многоугольник. Многоугольник называется выпуклым, если любые две точки его периметра можно соединить отрезком, каждая точка которого лежит внутри многоугольника.

Здесь слева — выпуклый многоугольник, справа — нет.

Одним из критериев выпуклости является следующий.

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

В общем случае, произведение векторов в трехмерном пространстве находится по формуле:

$\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}$

Здесь i, j, k — орты декартовой системы (вектора единичной длины, сонаправленные с осями координат).
Однако, если мы рассматриваем вектора, лежащие в одной плоскости, то для этого случая z-составляющая векторов будет нулевой. Тогда наша формула выродится в:

$\left [ a, b \right ]=\left (x_{1}y_{2}-x_{2}y_{1} \right)k$

Таким образом, мы должны обойти все пары соседних сторон-векторов и посмотреть, все ли их произведения одного знака. (То есть все ли значения разности произведений $\left (x_{i}y_{i+1}-x_{i+1}y_{i} \right)$ одного знака для всех i от 1 до N-1).

Итак алгоритм:

Задаем N — количество вершин многоугольника
Задаем (вводим или присваиваем) все вершины многоугольника $P_{i}^{x}, P_{i}^{y}$ для всех i от 1 до N.
Полагаем многоугольник выпуклым Q=true.
Вычисляем T=x_Ny₁-x₁y_N
Вычисляем Z=T/|T|, |T| — модуль числа Т.
Полагаем P=1
Для всех i от 1 до N-1 при условии что Q=true вычисляем:
1. x_i,y_i
2. x_i+1,y_i+1
3. R=x_iy_i+1-x_i+1y_i
4. P=P*Z*R/|R|, здесь |R| — модуль числа R.
5. Если P<0, то Q=false
6. Если Q=true — многоугольник выпуклый, иначе — нет.

Вычисление координат вектора, образованного сторонами многоугольника (x_i, y_i), хорошо производить в отдельной процедуре.

$x_{i}=P_{i+1}^{x}-P_{i}^{x}\]\[y_{i}=P_{i+1}^{y}-P_{i}^{y}$

Для N-ой вершины N+1-ая будет, естественно, первой.

Решение задачи

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.

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;

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.

выпуклый многоугольник, программирование

Построение выпуклой оболочки

Площадь многоугольника

#:

Выпуклость многоугольника

Постановка задачи

Решение задачи

Похожие материалы:

Оставить комментарий