Ruby練習三日目（最小包含円?）

Ruby programming

先日コッホ雪片を描くプログラムを書いて、雪片が画像の中心に描かれていないので次はその部分を作り込みたい、と日記に書いたのでその方法を考えてみた（ま、その問題はここに書く方法とは別の方法で解決しているんだけど）。考えとしては、コッホ雪片を構成する各コッホ曲線の端点を通る円の中心点を求めて、その中心点が画像の中心にくるように調整するという算段。その中心点を求めるプログラムを作ってみた。そのプログラムは、n個の点全てを含む円の中心を求めるのであって、点を全て通る円を求めるのではないのであしからず。この前作ったコッホ雪片は正n角形の頂点を各コッホ曲線の端点としているので、問題ないだろうと思う。

# n個の点全てを含む円のうち半径が最小である円の
# 中心座標と半径を求める
class SolvCircle

    LOOP_MAX = 100

    # 移動距離がこの値以下になったら処理を終了させる
    CONVRGV = 1.0e-9

    #
    #=== 円の中心座標と半径を求める
    #
    #_pt_x_ :: n個の点のx座標の配列
    #_pt_y_ :: n個の点のy座標の配列
    # 
    #返り値::配列を返す。[中心点のx座標, 中心点のy座標, 円の半径]
    #
    def solv_circle(pt_x, pt_y)
        mv_rate  = 0.5 # 移動係数
        max_dist = 0.0 # 中心点から最遠点までの距離
        xsv      = 0.0 # 中心点のx座標
        ysv      = 0.0 # 中心点のy座標
        cx       = 0.0 # 仮中心点のx座標
        cy       = 0.0 # 仮中心点のy座標
        k        = 0
        cvgflg   = false

        while (cvgflg == false)

            LOOP_MAX.times { |t|
                # 最遠点を求める
                max_dist = 0.0
                pt_x.length.times { |i|
                    dist = distance(cx, cy, pt_x[i], pt_y[i])
                    if (dist > max_dist)
                        max_dist = dist
                        k        = i
                    end
                }

                # 仮の中心点を計算
                cx += (pt_x[k] - xsv) * mv_rate
                cy += (pt_y[k] - ysv) * mv_rate

                # 移動距離が境界値を下回っていればループを抜ける
                if (distance(cx, cy, xsv, ysv) <= CONVRGV)
                    cx     = xsv
                    cy     = ysv
                    cvgflg = true
                    break
                end

                xsv = cx
                ysv = cy
            }

            mv_rate /= 2.0

        end

        return [cx, cy, max_dist]
    end

    #
    #=== 二点の距離を求める
    #
    def distance(x1, y1, x2, y2)
        dx = x2 - x1
        dy = y2 - y1
        Math.sqrt(dx * dx + dy * dy)
    end
end
感想
  • 変数のスコープで少しつまずいた。上記のコードでいうと、max_dist や k がそう。始めて定義されるところがブロックの中だったので、そのブロックの外で使おうとした場合に "undefined local variable or method" というエラーが発生。気をつけねば。
  • 円の座標を求める場合、CONVRGV を小さくしないと精度が下がる。当たり前か。どこまで小さくすればよいのかは、そのプログラムの性質によるよね。そもそも、このロジックでいいのかという話もあるし。
  • このアルゴリズムの名前って何？
参考