Ruby/SDLで計算幾何(5) 点が多角形の中に内部にあるか判定する2

前回のコードをRubyで書くことはできました。

その前に前の日記のPolygonクラス絡みで拡張したいところやらバグやらがあったので修正します。

class GeoBase

  class Polygon
    attr_accessor :vertices, :size
    def initialize(points)
      @size = points.size  # 頂点数を追加
      @vertices = points.push points[0], points[1]
    end
  end

    def polygon(x1, *arg)
    if arg
      if arg.size % 2 == 0
        raise ArgumentError, 'num of coodinates is odd.'
      else
        arg.unshift x1
        vertices = []
        (0..(arg.size/2-1)).each do |i|  # このあたり修正
          vertices << p(arg[2*i], arg[2*i+1])
        end
      end
    else
      vertices = x1
    end
    Polygon.new vertices  
  end
  alias poly polygon
end

そしてPointクラスのメソッドinsideです。もっとスマートに書けそうなものですが･･･

class GeoBase
  class Point
    def inside(poly)
      x_inf = Point.new(65535,y)  #とりあえず
      lt= Line.new(self, x_inf)
      p = poly.vertices
      j = 0
      count = 0
      (1..poly.size).each do |i|
        lp=Line.new(p[i],p[i])
        unless (GeoUtil.ccw(lt.p1, lt.p2, p[i]) == 0)
          if (i == j + 1)
            lp.p2 = p[j]
            count += 1 if GeoUtil.intersect(lp, lt)
          else
            count += 1 if (GeoUtil.ccw(lt.p1, lt.p2, p[i]) * GeoUtil.ccw(lt.p1, lt.p2, p[j])) < 0
          end
          j = i
        end
      end
      (count&1 == 0)? false : true
    end
  end
end

では、テストをしてみます。テストデータとして下図のような、凹凸のある七角形を用意します。

class GeoBaseTest < GeoBase
  def start
    poly = poly(50,50,80,100,50,150,100,120,150,150,120,100,150,50)
    draw poly
    
    def set_p(x, y)
      p1 = p(x,y)
      draw p1
      p1
    end
    
    puts set_p(100,100).inside(poly) #=> true
    puts set_p(80,120).inside(poly)  #=> true
    puts set_p(50,100).inside(poly)  #=> false
  end
end

GeoBaseTest.start

正常に動いているようです。

ところで、点が辺上にある場合、頂点である場合はどういう答えが返ってくるかを見ていませんでした。七頂点を設定してみます。

    puts set_p(50,50).inside(poly)    #=> true
    puts set_p(80,100).inside(poly)   #=> false
    puts set_p(50,150).inside(poly)   #=> false
    puts set_p(100,120).inside(poly)  #=> true
    puts set_p(150,150).inside(poly)  #=> false
    puts set_p(120,100).inside(poly)  #=> true
    puts set_p(150,50).inside(poly)   #=> true

黒点は多角形の内部、白点は多角形の外部を表しています。

実は、一点の例外を除き、これらの頂点の判定は、各頂点を少しx軸負方向(図でいう左側方向)にずらした点の判定と同一です。これは、ccw,intersectによる判定が、線分の端点を含むことに由来しています。

では、例外の一点(50,50)は何かと言いますと、、、配列の先頭の処理に由来すると思うのですが、、、疲れましたのでまた今度です。