包装アルゴリズム

Blogopolisを見ていると，計算幾何について学んでみたくなります。ということで，凸包を求めるプログラムを作ってみました。
今回は，包装アルゴリズム(package wrapping algorithm)を使っています。以前，cairoを使ってみたことがあるので，今回も利用します。

wrapping.rb

包装アルゴリズムについては，以下を参考にしました。

• 凸包の計算と多角形の面積計算
• 『アルゴリズムC〈第2巻〉探索・文字列・計算幾何』

# -*- coding: utf-8 -*-
require 'my_canvas'

# 線分p1p2と水平な直線がなす角度を求める(0〜360)
def theta(p1, p2)
  dx = p2[0] - p1[0]; ax = dx.abs
  dy = p2[1] - p1[1]; ay = dy.abs
  t = (ax + ay == 0) ? 0 : dy.to_f / (ax + ay)
  if (dx < 0)
    t = 2 - t
  elsif (dy < 0)
    t = 4 + t
  end
  return t * 90.0
end

# 包装アルゴリズム(package wrapping algorithm)
def wrap(points)
  path = []                     # 凸包上の点
  min = 0
  points.each_with_index do |elem, i| # y座標が一番小さい点を探す
    min = i if elem[1] < points[min][1]
  end
  start = points.delete_at(min)
  path << start
  th = 0.0
  loop do 
    ths = points.map {|ele| theta(path.last, ele)}
    th = ths.select {|ele| ele > th}.min
    break if th == nil
    path << points.delete_at(ths.rindex(th))
  end
  return  path << start
end

points = [[ 3,  9], [11,  1], [ 6,  8], [ 4,  3],
          [ 5, 15], [ 8, 11], [ 1,  6], [ 7,  4],
          [ 9,  7], [14,  5], [10, 13], [16, 14],
          [15,  2], [13, 16], [ 3, 12], [12, 10]]

solved =  wrap(points)


canvas = MyCanvas.new(20, 20)

points.each do |p|
  canvas.draw_point(p, 0.1, "#FF3030")
end

pre = solved.shift
canvas.draw_point(pre, 0.1)
solved.each do |p|
  canvas.draw_line(pre, p)
  canvas.draw_point(p, 0.2, "#FF3030")
  pre = p
end

canvas.write_to_png("convex_full.png")

my_canvas.rb

描画用です。

require 'rubygems'
require 'cairo'

class MyCanvas
  WIDTH = 400; HEIGHT = 400
  
  def initialize(max_x = 20, max_y = 20)
    @max_x = max_x
    @max_y = max_y
    @surface = Cairo::ImageSurface.new(Cairo::FORMAT_ARGB32, WIDTH, HEIGHT)
    @context = Cairo::Context.new(@surface)
    @context.set_source_rgb(1, 1, 1)
    @context.scale(WIDTH / @max_x, HEIGHT / @max_y)
    @context.rectangle(0, 0, WIDTH, HEIGHT)
    @context.fill
  end

  def draw_line(p0, p1, color = "#2E8B57")
    @context.set_source_color(Cairo::Color.parse(color))
    @context.set_line_width(2.0 / (WIDTH / @max_x))
    @context.move_to(p0[0], @max_y - p0[1])
    @context.line_to(p1[0], @max_y - p1[1])
    @context.stroke()
  end

  def draw_point(p, r, color = "#2E8B57")
    @context.set_source_color(Cairo::Color.parse(color))
    @context.circle(p[0], @max_y - p[1], r)
    @context.fill
  end

  def write_to_png(fname)
    @surface.write_to_png(fname)
  end
end

実行結果