凸包の高速な計算
(amazon:476490277X p.8)
逐次添加法。
点列をx座標順に並び替えて、最初の3つの点の凸包(3点からなる三角形)から初めて、1点ずつ追加しながら凸包を更新して行く。
詳しくはこのpdfの12ページ当たりを参考。
require 'geo_base' # 「コンピュータ・ジオメトリ 計算機科学:アルゴリズムと応用」 p.8 class ConvexHull < GeoBase def setup_points 100.times do (@points ||= []) << p(rand(200)+50, rand(200)+50) end @points end def points @points || setup_points end def signed_dimension(a, b, c) ((a.x - c.x) * (b.y - c.y) + (b.x - c.x) * (c.y - a.y)) / 2 end def clockwise?(list) return false if list.size < 3 signed_dimension(*(list[-3..-1])) < 0 end # GeoBaseクラスを変更して、startメソッドの代わりにクラス名を # 小文字にした名前のメソッドが最初に呼ばれるようになりました def convex_hull # 点列をx座標順にソート points.sort! {|p1, p2| p1.x <=> p2.x} # 上部凸包 upper_list = [points[0], points[1]] (3...points.size).each do |i| upper_list << points[i] while 3 <= upper_list.size and not clockwise?(upper_list) upper_list.delete_at -2 end end # 下部凸包 lower_list = [points[-1], points[-2]] (3..points.size).each do |i| lower_list << points[-i] while 3 <= lower_list.size and not clockwise?(lower_list) lower_list.delete_at -2 end end # 上部凸包と下部凸包を連結 lower_list.pop lower_list.unshift list = upper_list + lower_list # 結果表示 draw *points draw *lines(list, true) end end ConvexHull.start