Ruby/SDLで計算幾何(1)線分が交差しているか判定する

とりあえずテキスト『アルゴリズムC第二巻』amazon:4764902567を写しました。

module GeoUtil
  module_function
  
　# 線分p0p1を基準にして、線分p0p2が
　#  反時計回りの向きにあれば+1 
　#    時計回りの向きにあれば-1
  def ccw(p0, p1, p2)
    dx1 = p1.x - p0.x; dy1 = p1.y - p0.y
    dx2 = p2.x - p0.x; dy2 = p2.y - p0.y
    return +1 if dx1*dy2 > dy1*dx2
    return -1 if dx1*dy2 < dy1*dx2
    return -1 if (dx1*dx2 < 0) || (dy1*dy2 < 0)　　#(1)
    return +1 if dx1*dx1+dy1*dy1 < dx2*dx2+dy2*dy2 #(2)
    return 0                                       #(3)
  end
  
　# 2線分が交差しているかを判定する
  def intersect(l1, l2)
    return ((ccw(l1.p1, l1.p2, l2.p1) * ccw(l1.p1, l1.p2, l2.p2)) <= 0 ) &&
           ((ccw(l2.p1, l2.p2, l1.p1) * ccw(l2.p1, l2.p2, l1.p2)) <= 0 )
  end
end

このccwについて、なぜこういう関数にしてあるのか分析します。まだ途中です。

(1)-(3)はp0,p1,p2の3点が同一直線上にある場合(もしくは3点が同一の場合)の処理をしている箇所です。

以下、p0,p1,p2の3点が同一直線上にあり、p0とp1が異なる点であるとします。(つまり、線分p0p1が存在するとします)

• (1)により値が-1となるのは、p0から見てp2がp1と異なる側にある場合、つまりp2-p0-p1の順に並んでいる場合です。
  • xについての条件とyについての条件がorで結びついているのは、直線がx軸に平行、またはy軸に平行な場合を考慮してのことです。
• (2)により値が+1となるのは、p0から見てp2がp1の向こう側にある場合、つまりp0-p1-p2の順に並んでいる場合です。
• (3)により値が0となるのは、p2が線分p0p1上にある場合、つまりp0-p2-p1の順に並んでいる場合です。これは両端点も含みます。

p0とp1が同じ点ならどうでしょうか。関数に dx1=dy1=0 を代入して追ってみますと、上の結果から類推できるような結果が出ます。実行した方が早いかもしれません。

このようなccwの仕様を、intersectにどう活かしているかは、時間がありませんので明日。