凸包の高速な計算

(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

結果

点が100個でも余裕で表示できるようになった。
ときどき凸包の外に点が表示されるのでなんかバグがあると思うけど、放置。