The work consists of two independent procedures. The first procedure  IsConvex  checks the convexity of a polygon. The second procedure  IsSimple  verifies the simplicity of a polygon. Formal argument   is the list of vertices of the polygon.

Regarding the basic concepts, see  http://en.wikipedia.org/wiki/Polygon

 

IsConvex:=proc(X::listlist)

local n, Z, f, i, x, y;

n:=nops(X);

Z:=[op(X),X[1]];

f:=seq((x-Z[i,1])*(Z[i+1,2]-Z[i,2])-(y-Z[i,2])*(Z[i+1,1]-Z[i,1]),i=1..n);

   for i to n do

    if  convert([seq(is(subs(x=j[1],y=j[2],f[i])<=0), j in {op(X)} minus  {X[i],X[irem(i,n)+1]})],`or`) and      convert([seq(is(subs(x=j[1],y=j[2],f[i])>=0),

    j in {op(X)} minus {X[i],X[irem(i,n)+1]})], `or`) then break fi;

   od;

if i<=n then return false else true fi;

end proc:

 

IsSimple:=proc(X::listlist)

local n, Z, i, j, f, T, Q, x, y;

Z:=[op(X),X[1],X[2]]; n:=nops(X);

if n>nops({op(X)}) then   return false  fi;

   for i from 2 to nops(Z)-1 do

     if is((Z[i-1,1]-Z[i,1])*(Z[i+1,1]-Z[i,1])+(Z[i-1,2]-Z[i,2])*(Z[i+1,2]-Z[i,2]) =  sqrt((Z[i-1,1] -Z[i,1])^2+(Z[i-1,2]-Z[i,2])^2)*sqrt((Z[i+1,1]-Z[i,1])^2 +(Z[i+1,2]-Z[i,2])^2)) then return false fi;

   od;

f:=seq((x-Z[i,1])*(Z[i+1,2]-Z[i,2])-(y-Z[i,2])*(Z[i+1,1]-Z[i,1]),i=1..n);

_Envsignum0:= 0: 

   for i from 1 to n do

   T[i]:=[]; Q[i]:=[];

      for j from 1 to n do

      if modp(j-i,n)<>0 and modp(j-i,n)<>1 and modp(j-i,n)<>n-1 and                  not(signum(subs(x=Z[j,1],y=Z[j,2],f[i])*subs(x=Z[j+1,1],y=Z[j+1,2],f[i]))=-1 and             signum(subs(x=Z[i,1],y=Z[i,2],f[j])*subs(x=Z[i+1,1],y=Z[i+1,2],f[j]))=-1) then

      if (subs(x=Z[j,1],y=Z[j,2],f[i])=0 implies (signum((Z[j,1]-Z[i,1])*(Z[i+1,1]-Z[j,1]))=-1 or             signum((Z[j,2]-Z[i,2])*(Z[i+1,2]-Z[j,2]))=-1)) then

      T[i]:=[op(T[i]),1]; Q[i]:=[op(Q[i]),1] else  T[i]:=[op(T[i]),1]  fi; fi;   od;

       od; 

convert([seq(nops(T[i])=n-3,i=1..n), seq(nops(Q[i])=n-3,i=1..n)],`and`)  

end proc:

 

Examples:

X:=[[0,0],[1,0],[2,1],[3,0],[4,0],[2,2]]: IsConvex(X), IsSimple(X);

X:=[[0,0],[2,0],[1,1],[1,-1]]: IsConvex(X), IsSimple(X);

X:=[[0,0],[2,0],[1,1],[1,0], [-1,-1]]: IsConvex(X), IsSimple(X);

X:=[[0,0],[1,0],[1,2],[-2,2],[-2,-2],[3,-2],[3,4],[-4,4],[-4,-4],[5,-4],[5,6],[-6,6],[-6,-6],[7,-6],[7,8],[-6,8],[-6,7],[6,7],[6,-5],[-5,-5],[-5,5],[4,5],[4,-3],[-3,-3],[-3,3],[2,3],[2,-1],[-1,-1],[-1,1],[0,1]]: IsConvex(X), IsSimple(X);

X:=[seq([cos(2*Pi*k/17), sin(2*Pi*k/17)], k=0..16)]: IsConvex(X), IsSimple(X);

Testing_polygons.mws 

Edited: The variables  x  and  y  are made local.

 


Please Wait...