Items tagged with polygons polygons Tagged Items Feed

Not homework (from the telly): A gallery takes a concave polygon shape with a square pillar in the centre. security cameras can do a 360 degree sweep but they can't see around corners. The cameras have to be attached to the walls. What is the fewest number of cameras such that they can see everywhere in the gallery?

I got as far as drawing it in Maple.

there is an algorithm -which supposedly finds the optimal solutuion- breaking the object into triangular shapes. that gets an answer:  4 cameras.

EDIT 11/10

this is based on Fisk's short proof. See Markiyan's wiki ref below.

1.first stand on on a corner and scan clockwise around the room. Any two corners passed creates one triangle.

Repeat for every corner


2. Pick three colours and allocate each color to each corner of each triangle.

sometimes you will end up with a triangle which has 2 corners of the same colour. This one has two blue corners


This triangle must be broken in two and add a green dot

3.finally the algorithm places cameras on the colour which occurs least.

But by experimenting with more complex shapes (convex polygons) you can cover the gallery with 3.


In Maple anyone?


Hi, i'm trying to make a function to create 2 polygons with the same number of sides, the same center but different radius. These 2 polygons have to be on the same draw. I tried by doing this function but its not working..

 If anyone could help me it would be great and sorry for my bad english i'm from France.

I am creating a plot in Maple17 which will include many line segments and polygons.  I want the axes to be equally scaled, so that line segments that are perpendicular actually look perpendicular.  When I view what I have created so far, line segments that are perpendicular do not appear to be so in a plot, even though I used the "scaling=constrained" option several times.  I created a stripped-down file that isolates the problem.  Here it is:



segp := proc(pt1, pt2)
  description "plot of line segment between two points";
  local m;
end proc:

slope := proc(pt1, pt2)
  description "slope of line segment btwn two different points";
end proc:



pa9:=[0.1864032968, 0.9824733131];

[.1864032968, .9824733131]


pa16:=[0.6816387600, 0.7316888689];

[.6816387600, .7316888689]


pd9:=[0.05940746930, 0.7316888689];

[0.5940746930e-1, .7316888689]












An angle that should be a right angle looks obtuse in the plot.  I used "scaling=constrained" in both the "display" command and the "segp" procedure.  I am using "polygonplot" to plot line segments (degenerate polygons) because the final plot will contain genuine polygons and this seemed like the easiest way to do it.  If this is a bad idea for some reason I can change it.



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



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




   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;


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

end proc:



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;



_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;


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

end proc:



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);


Edited: The variables  x  and  y  are made local.


We assume that the length of a match is 1, then the perimeter of a polygon is equal to the number of matches N. If a match can be located at arbitrary angles to each other, then at a given perimeter of the area can take on any value between zero and the area of a regular polygon (for even number of matches) . For an odd number of matches the lower bound equals to the area of an equilateral triangle of side 1. For any given area within these boundaries will be infinitely many solutions.

Page 1 of 1