Triangulations of a convex polygon
Triangulations of a convex polygon
Keehong Song
Pusan National University,South Korea
khsong@mathematica.co.kr
Pusan National University,South Korea
khsong@mathematica.co.kr
This is a Mathematica Notebook which finds and visualizes the triangulations of a convex polygon. As an example, 5-polygon has 5 triangulation as follows. In general, n-polygon has the triangulations of the n-2 Catalan number, that is, .References:Grimaldi, R. Discrete and Combinatorial Mathematics, 3rd ed., Addison-Wesley,1994.
1
n-1
2(n-2) |
n-2 |
Counting binary tree
Counting binary tree
Thenumberofbinarytreeswithnnodesis
1
n+1
2n |
n |
catalanNumber[n_]:=Binomial[2n,n]/(n+1)
In[1]:=
Generating binary tree
Generating binary tree
Generating binary trees for traversal to find edges to be used in triangulations of a convex polygon, where the number of different binary trees is the Catalan number.
catalanTree[{}]:={{}}catalanTree[{a_}]:={{a}}catalanTree[l_List]:= Module[{m=Rest[l],i,elem1st=First[l]}, Join@@Map[Insert[#,{elem1st},{2}]&, Table[Distribute[ catalanTree[Take[m,i]], catalanTree[Take[m,{i+1,Length[m]}]],List], {i,0,Length[m]}],{2}]]
In[2]:=
Finding all the binary trees made out of the nodes,{1,2,3,4}, when parenthesis seen as the tree structure.
catalanTree[{1,2,3,4}]
In[5]:=
{{{},{1},{{},{2},{{},{3},{4}}}},{{},{1},{{},{2},{{4},{3},{}}}},{{},{1},{{3},{2},{4}}},{{},{1},{{{},{3},{4}},{2},{}}},{{},{1},{{{4},{3},{}},{2},{}}},{{2},{1},{{},{3},{4}}},{{2},{1},{{4},{3},{}}},{{{},{2},{3}},{1},{4}},{{{3},{2},{}},{1},{4}},{{{},{2},{{},{3},{4}}},{1},{}},{{{},{2},{{4},{3},{}}},{1},{}},{{{3},{2},{4}},{1},{}},{{{{},{3},{4}},{2},{}},{1},{}},{{{{4},{3},{}},{2},{}},{1},{}}}
Out[5]=
By flattening the tree structure above, we get the order in which a group of cars can go in and out of the narrow-alley parking lot in an orderly fashion.
Flatten/@%
In[6]:=
{{1,2,3,4},{1,2,4,3},{1,3,2,4},{1,3,4,2},{1,4,3,2},{2,1,3,4},{2,1,4,3},{2,3,1,4},{3,2,1,4},{2,3,4,1},{2,4,3,1},{3,2,4,1},{3,4,2,1},{4,3,2,1}}
Out[6]=
Length[%]==catalanNumber[4]
In[7]:=
True
Out[7]=
Finding edges involved in a triangulation of a convex polygon
Finding edges involved in a triangulation of a convex polygon
Depth first traversal is used to find the edges which conduce to the triangulations of a convex polygon.
There are three types of nodes in a given node of a tree:
1. both left and right children exist
2. only right child exists
3. only left child exists
These three types determines the patterns of the edges of a triangulation
There are three types of nodes in a given node of a tree:
1. both left and right children exist
2. only right child exists
3. only left child exists
These three types determines the patterns of the edges of a triangulation
NodeQ=Function[c,c=!={}];search[{lc_?NodeQ,{parent_},rc_?NodeQ},{l_,r_}]:=(AppendTo[storage,#]&)/@ {l,l+Length[Flatten[lc]]+1}, {l+Length[Flatten[lc]]+1,r};search[lc,{l,l+Length[Flatten[lc]]+1}];search[rc,{l+Length[Flatten[lc]]+1,r}];search[{lc_?NodeQ,{parent_},{}},{l_,r_}]:= (AppendTo[storage,{l+1,r}];search[lc,{l+1,r}]);search[{{},{parent_},rc_?NodeQ},{l_,r_}]:= (AppendTo[storage,{l,v〚r〛}];search[rc,{l,v〚r〛}]);triangleEdges[n_]:=Block{storage=branches={},v,m,trees}, v=RotateRight[Range[n+2],1]; trees=catalanTree[Range[n]]; Tablesearch[trees〚m〛,{2,1}]; AppendTo[branches,storage]; storage={}, {m,1,catalanNumber[n]}; branches
In[8]:=
We want to make sure that there is no duplicates in the set of edges for triangulations.
zigzag=triangleEdges[5];
In[13]:=
Length@Union[Sort/@zigzag]==Length[zigzag]
In[14]:=
True
Out[14]=
The following routine 'triangulation' does the physical triangulation by placing the line segments to the necessary positions in an n-gon.
triangulation[n_Integer,pairs_List]:= Module[{x=N[2Pi/n],poly,vertices,edges}, vertices=Chop@Table[N[{Cos[xi],Sin[xi]}],{i,n}]; poly=Line/@Partition[Append[vertices,First[vertices]],2,1]; edges=Line/@(vertices[[#]]&/@pairs); labels=MapIndexed[Text[Style[First[#2],10],#1]&,vertices*1.1];(*AddedbyRohitNamjoshi*) Show[Graphics[{poly,edges,labels}],(*ModifiedbyRohitNamjoshi*) DisplayFunction->Identity,AspectRatio->Automatic] ]
In[15]:=
Making the visualization process as a single function
Making the visualization process as a single function
In making a single function out of the process of visualizing triangulation, a minor trouble is met due to a limitation of the built-in 'Partition' function: it throws away the remainding parts after partitioning the given set to a size. Appending the remainder at the end of the partition result solves the problem.
showTriangulation[n_Integer,gons_]:= Module[{pic}, (*Ifthesizeistoosmall,donotpartition*) pic=If[n>=5, Append[Partition[gons,15],Take[gons,-Mod[catalanNumber[n-2],15]]],gons]; Show[GraphicsGrid[pic],DisplayFunction->$DisplayFunction]]
In[16]:=
An example for the case of 5-polygon
An example for the case of 5-polygon
The number of triangulations of a n-polygon is, .
1
n-1
2(n-2) |
n-2 |
size=5;edges=triangleEdges[size-2];tripic=triangulation[size,#]&/@edges;showTriangulation[size,tripic]
In[30]:=
Out[33]=
tripic//Length
In[34]:=
5
Out[34]=
catalanNumber[size-2]
In[35]:=
5
Out[35]=
Now we know that all the triangulations are accounted for.
edges
In[36]:=
{{{2,5},{2,4}},{{2,5},{3,5}},{{2,4},{4,1}},{{3,1},{3,5}},{{3,1},{4,1}}}
Out[36]=