tkenichi の日記

毒舌皮肉系恥さらし日記

多角形を三角形分割2

f:id:tkenichi:20131207161434j:plain

平面上の多角形の三角形分割を列挙するプログラムを作成してみた。先日の記事で紹介したような拡張された三角形分割ではなく、総数がカタラン数で与えられるような三角形分割である。

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