Blogopolisを見ていると,計算幾何について学んでみたくなります。ということで,凸包を求めるプログラムを作ってみました。
今回は,包装アルゴリズム(package wrapping algorithm)を使っています。以前,cairoを使ってみたことがあるので,今回も利用します。
wrapping.rb
包装アルゴリズムについては,以下を参考にしました。
# -*- 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