Kitonum

20344 Reputation

26 Badges

16 years, 7 days

MaplePrimes Activity


These are Posts that have been published by Kitonum

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.

 

Well-known problem is the problem of placing eight shess queens on an 8×8 chessboard so that no two queens attack each other. In this post, we consider the same problem of placing  m  shess queens on an  n×n  chessboard. The problem has a solution if  n>3  and  m<=n .

Work consists of two procedures. The first procedure  Queens  returns the total number of solutions and saves a complete list of all solutions (global variable  S ). The second procedure  QueensPic  shows the user-defined solutions from the list  S  on the board. Formal argument  t  is the number of solutions in each row of the display. The second procedure should be used in the standard interface, rather than in the classic one, since in the latter it may not work properly.

Queens := proc (m::posint, n::posint)

local It, K, l, L, M, P;

global S, p, q;

It := proc (L)

local P, k, i, j;

M := []; k := nops(L[1]);

for i in L do

for j to n do

if convert([seq(j <> i[s, 2], s = 1 .. k)], `and`) and convert([seq(l[k+1]-i[s, 1] <> i[s, 2]-j, s = 1 .. k)], `and`) and convert([seq(l[k+1]-i[s, 1] <> j-i[s, 2], s = 1 .. k)], `and`) then M := [op(M), [op(i), [l[k+1], j]]]

fi;

od; od;

M;

end proc;

K := combinat:-choose([`$`(1 .. n)], m);

S := [];

for l in K do P := [];

L := [seq([[l[1], i]], i = 1 .. n)];

P := [op(P), op((It@@(m-1))(L))];

S := [op(S), op(P)]

od;

p := args[1]; q := args[2];

nops(S);

end proc:

 

QueensPic := proc (M, t::posint)

local m, n, HL, VL, T, A, N;

uses plottools, plots;

m := p; n := q; N := nops(args[1]);

HL := seq(line([.5, .5+k], [.5+n, .5+k], color = black, thickness = 2), k = 0 .. n);

VL := seq(line([.5+k, .5], [.5+k, .5+n], color = black, thickness = 2), k = 0 .. n);

T := [seq(textplot([seq([op(M[i, j]), Q], j = 1 .. m)], color = red, font = [TIMES, ROMAN, 24]), i = 1 .. N)];

if m <= n and 3 < n then

A := seq(display(HL, VL, T[k], axes = none, scaling = constrained), k = 1 .. N), seq(display(plot([[0, 0]]), axes = none, scaling = constrained), k = 1 .. t*ceil(N/t)-N);

Matrix(ceil(N/t), t, [A]);

display(%);

fi;

end proc:

 

Examples of work:

Queens(5, 6);  

S[70], S[140], S[210];

QueensPic([%], 3); 

                                                                            248

[[1, 5], [2, 3], [3, 6], [4, 4], [6, 1]], [[1, 3], [2, 5], [4, 1], [5, 4], [6, 2]], [[2, 1], [3, 4], [4, 2], [5, 5], [6, 3]]

 

Two solutions of classic problem:

Queens(8, 8); 

S[64..65];

QueensPic(%, 2);

                                                                                      92

[[[1, 5], [2, 8], [3, 4], [4, 1], [5, 7], [6, 2], [7, 6], [8, 3]], [[1, 6], [2, 1], [3, 5], [4, 2], [5, 8], [6, 3], [7, 7], [8, 4]]]

 

 

Queens_problem.mw

A kryptarithm - this is an example of arithmetic, in which all or some of the digits are replaced by letters. The rule must be satisfied: the different letters represent different digits, the identical letters represent the identical digits. See the link  http://en.wikipedia.org/wiki/Verbal_arithmetic.

The following procedure, called  Ksolve , solves kryptarithms in which are used four operations ...

It's interesting that every continuous piecewise linear function can be specified by one explicit equation with absolute values​​. The procedure JoggedLine carries out such conversion.

Formal arguments of the procedure: 

A - a list of the coordinates of the vertices of the polyline or the continuous piecewise linear expression defined on the entire real axis.

B (optional) - a point on the left "tail"...

Given a figure in the plane bounded by the non-selfintersecting piecewise smooth curve. Each segment in the border defined by the list in the following format (variable names  in expressions can be arbitrary):

1) If this segment is given by an explicit equation, then  [f(x), x=x1..x2)]

2) If it is given in polar coordinates, then  [f(phi), phi=phi1..phi2, polar] , phi is polar angle

3) If the segment is given parametrically, then  [[f(t), g(t)], t=t1..t2]

4) If several consecutive segments or entire border is a broken line, then it is sufficient to set vertices the broken line [ [x1,y1], [x2,y2], .., [xn,yn]]

 

The first procedure symbolically finds perimeter of the figure. Global variable  Q  saves the lengths of all segments.

Perimeter := proc (L) #  L is the list of all segments of the border

local i, var, var1, var2, e, e1, e2, P;

global Q;

for i to nops(L) do if type(L[i], listlist(algebraic)) then P[i] := seq(simplify(sqrt((L[i, j, 1]-L[i, j+1, 1])^2+(L[i, j, 2]-L[i, j+1, 2])^2)), j = 1 .. nops(L[i])-1) else

var := lhs(L[i, 2]); var1 := min(lhs(rhs(L[i, 2])), rhs(rhs(L[i, 2]))); var2 := max(lhs(rhs(L[i, 2])), rhs(rhs(L[i, 2])));

if type(L[i, 1], algebraic) then e := L[i, 1]; if nops(L[i]) = 3 then P[i] := simplify(int(sqrt(e^2+(diff(e, var))^2), var = var1 .. var2)) else

P[i] := simplify(int(sqrt(1+(diff(e, var))^2), var = var1 .. var2)) end if else

e1 := L[i, 1, 1]; e2 := L[i, 1, 2]; P[i] := abs(simplify(int(sqrt((diff(e1, var))^2+(diff(e2, var))^2), var = var1 .. var2))) end if end if end do;

Q := [seq(P[i], i = 1 .. nops(L))];

add(Q[i], i = 1 .. nops(Q));

end proc:

 

The second procedure symbolically finds the area of the figure. For correct work of the procedure, all the segments in the list L  of border must pass sequentially in clockwise or counter-clockwise direction.

Area := proc (L)

local i, var, e, e1, e2, P;

for i to nops(L) do

if type(L[i], listlist(algebraic)) then P[i] := (1/2)*add(L[i, j, 1]*L[i, j+1, 2]-L[i, j, 2]*L[i, j+1, 1], j = 1 .. nops(L[i])-1) else

var := lhs(L[i, 2]);

if type(L[i, 1], algebraic) then e := L[i, 1];

if nops(L[i]) = 3 then P[i] := (1/2)*(int(e^2, L[i, 2])) else

P[i] := (1/2)*simplify(int(var*(diff(e, var))-e, L[i, 2])) end if else

e1 := L[i, 1, 1]; e2 := L[i, 1, 2]; P[i] := (1/2)*simplify(int(e1*(diff(e2, var))-e2*(diff(e1, var)), L[i, 2])) end if end if

end do;

abs(add(P[i], i = 1 .. nops(L)));

end proc:

 

The third procedure shows this figure. To paint the interior of the boundary polyline approximation is used. Required parameters: L - a list of all segments of the border and C - the color of the interior of the figure in the format color = color of the figure. Optional parameters: N - the number of parts for the approximation of each segment (default N = 100) and Boundary is defined by a list for special design of the figure's border (the default border is drawed by a thin black line). The border of the figure can be drawn separately without filling the interior by the global variable Border.

Picture := proc (L, C, N::posint := 100, Boundary::list := [linestyle = 1])

local i, var, var1, var2, e, e1, e2, P, Q, h;

global Border;

for i to nops(L) do

if type(L[i], listlist(algebraic)) then P[i] := op(L[i]) else

var := lhs(L[i, 2]); var1 := lhs(rhs(L[i, 2])); var2 := rhs(rhs(L[i, 2])); h := (var2-var1)/N;

if type(L[i, 1], algebraic) then e := L[i, 1];

if nops(L[i]) = 3 then P[i] := seq(subs(var = var1+h*i, [e*cos(var), e*sin(var)]), i = 0 .. N) else

P[i] := seq([var1+h*i, subs(var = var1+h*i, e)], i = 0 .. N) end if else

e1 := L[i, 1, 1]; e2 := L[i, 1, 2]; P[i] := seq(subs(var = var1+h*i, [e1, e2]), i = 0 .. N) end if end if

end do;

Q := [seq(P[i], i = 1 .. nops(L))];

Border := plottools[curve]([op(Q), Q[1]], op(Boundary));

[plottools[polygon](Q, C), Border];

end proc:

 

Examples of works:

Example 1.

L := [[sqrt(-x), x = -1 .. 0], [2*cos(t), t = -(1/2)*Pi .. (1/4)*Pi, polar], [[1, 1], [1/2, 0], [0, 3/2]], [[-1+cos(t), 3/2+(1/2)*sin(t)], t = 0 .. -(1/2)*Pi]];

Perimeter(L); Q; evalf(`%%`); evalf(`%%`); Area(L); 

plots[display](Picture(L, color = grey, [color = "DarkGreen", thickness = 4]), scaling = constrained);

plots[display](Border, scaling = constrained);

Example 2.

The easiest way to use this  procedures for polygons.

 L := [[[3, -1], [-2, 2], [5, 6], [2, 3/2], [3, -1]]];

Perimeter(L), Q;

Area(L);

plots[display](Picture(L, color = pink, [color = red, thickness = 3]));

 

 

Example 3 (more complicated )

3 circles on the plane C1, C2 and C3 defined by the parametric equations  of their borders. We want to find the perimeter, area, and paint the figure  C3 minus (C1 union C2) . For details see attached file. 

C1 := {x = -sqrt(7)+4*cos(t), y = 4*sin(t)};

C2 := {x = 3*cos(s), y = 3+3*sin(s)};

C3 := {x = 4+5*cos(u), y = 5*sin(u)};

L := [[[-sqrt(7)+4*cos(t), 4*sin(t)], t = -arccos((1/4)*(7+4*sqrt(7))/(sqrt(7)+4)) .. -arctan((3*(-23+sqrt(7)*sqrt(55)))/(23*sqrt(7)+9*sqrt(55)))], [[3*cos(s), 3+3*sin(s)], s = -arctan((1/3)*(9+sqrt(7)*sqrt(55))/(-sqrt(7)+sqrt(55))) .. arctan((1/3)*(-9+4*sqrt(91))/(4+sqrt(91)))], [[4+5*cos(u), 5*sin(u)], u = arctan((3*(41+4*sqrt(91)))/(-164+9*sqrt(91)))+Pi .. arctan(3/4)-Pi]];

Perimeter(L), Q; evalf(%);

Area(L); evalf(%)

 A := plot([[rhs(C1[1]), rhs(C1[2]), t = 0 .. 2*Pi], [rhs(C2[1]), rhs(C2[2]), s = 0 .. 2*Pi], [rhs(C3[1]), rhs(C3[2]), u = 0 .. 2*Pi]], color = black);

B := Picture(L, color = green, [color = black, thickness = 4]);

plots[display](A, B, scaling = constrained);

More examples and all codes see in attached file

Plane_figure.mw

First 7 8 9 10 11 Page 9 of 11