凸包のバカ正直な計算 - ずっと君のターン

凸包とは、平面グラフ上の点（ある点集合）の中で最も｢外側」にある点を直線で結んで出来る線分の集合です。つまり、凸包の直線群はその線の内側にすべての点が含まれるような、いわばその点集合の最短の「境界線」と言えるでしょう。

今回実装するアルゴリズムでは、与えられた点の組み合わせで可能な全ての線分を求めて、それぞれの線分に対して、それに含まれない点が全てその線分の片側にあるかどうかを確認。もしそうならその線分は凸包の辺の一つ、そうじゃなかったら凸包の内部に含まれるので無視、と言うやり方で凸包を求めます。

想像通りむちゃくちゃ重くて、点の数を100にしたら帰ってこなかった。

require 'geo_base'

# 「コンピュータ・ジオメトリ 計算機科学:アルゴリズムと応用」 p.4
class SlowConvexHull < GeoBase
  def setup_points
    20.times do
      (@points ||= []) << p(rand(200)+50, rand(200)+50)
    end
    @points
  end
  
  def points
    @points || setup_points
  end
  
  def sort(edges)
    sorted_edges = [edges.pop]
    until edges.empty?
      edges.each do |ll|
        if sorted_edges.last.p2 == ll.p1
          sorted_edges << edges.delete(ll)
        end
      end
    end
    sorted_edges
  end
  
  def start
    # 辺集合
    edges = []
    
    # 可能な全ての線分
    lines = []
    points.each do |pp1|
      points.each do |pp2|
        lines << l(pp1, pp2) if pp1 != pp2
      end
    end
    
    lines.each do |ll|
      valid = true
      points.select{|pp| ll.p1 != pp and ll.p2 != pp}.each do |pp|
        valid = false if ll.left? pp
      end
      edges << ll if valid
    end
    
    # 結果の辺集合を時計回りにソート
    sorted_edges = sort edges
    
    # 結果表示
    puts sorted_edges.inspect
    draw *points
    draw *sorted_edges
  end
end

SlowConvexHull.start

結果