多角形を三角形分割2
平面上の多角形の三角形分割を列挙するプログラムを作成してみた。先日の記事で紹介したような拡張された三角形分割ではなく、総数がカタラン数で与えられるような三角形分割である。
def catalanEach(ary) case ary.size when 2 yield [] when 3 yield [ary] when 4 yield [ [ary[0],ary[1],ary[2]],[ary[0],ary[2],ary[3]]] yield [ [ary[0],ary[1],ary[3]],[ary[1],ary[2],ary[3]]] when 5 yield [ [ary[0],ary[1],ary[2]],[ary[0],ary[2],ary[3]],[ary[0],ary[3],ary[4]]] yield [ [ary[0],ary[1],ary[2]],[ary[0],ary[2],ary[4]],[ary[2],ary[3],ary[4]]] yield [ [ary[0],ary[1],ary[3]],[ary[1],ary[2],ary[3]],[ary[0],ary[3],ary[4]]] yield [ [ary[0],ary[1],ary[4]],[ary[1],ary[2],ary[3]],[ary[1],ary[3],ary[4]]] yield [ [ary[0],ary[1],ary[4]],[ary[1],ary[2],ary[4]],[ary[2],ary[3],ary[4]]] else (2...(ary.size)).each{ |i| t = [ [ary[0],ary[1],ary[i]] ] a0 = [ ary[0] ] a1 = [ ary[1] ] (2...(ary.size)).each{ |j| if j < i a1 << ary[j] elsif j == i a1 << ary[j] a0 << ary[j] else a0 << ary[j] end } catalanEach(a0){|t0| catalanEach(a1){|t1| yield (t+t0+t1) } } } end end