線分同士の交差判定方法

目的

次の線分 ab と cd が交差しているか判定したいとする。

手順

まずは cd の線を頭から消す。これ重要。そして直線 ab を、空中と地下を分ける地表と考える。続いて a からはさみで線分 cd の両端をつかむ。a からとしたけど b からつかんでもよい。

そして地表に対して a から出たはさみの両端の刃がそれぞれ空中にあるのか、地面に埋まっているのかを見る。どちらにあるかは、地表に対して外積を求めると「縦」の長さがわかる。正確には「正規化した地表ベクトル ab に対しての外積」を求めると、地表に対して垂直かつ、地表を0としたときの正負を含んだ長さがわかる。はさみの刃が空中だと長さは正になり、地面に埋まっていると負になる。

上の図だと一方は空中にあり一方は地面に埋まっている。言いかえると「正と負」の関係になっている。ここで頭から消し去っていた線分 cd の線をもとに戻すと「正と負」の関係だから線分 cd は ab に跨がっていると言える。もしベクトル cd の方向が逆で dc だったとしたら「負と正」になってこれも跨がっていると言える。

次の配置だとどうだろう？

上の図では、はさみの刃が両方空中にあるので「正と正」の関係になるので跨がっていないと言える。目視でもそれはわかる。

反対に上の図では、はさみの刃が両方地面に埋まっているので「負と負」の関係になりこれも跨がっていないと言える。

地表の線分が短かい場合

続いて次の配置はどうだろう？

一応、地表の直線を跨がってはいるんだけど線分として見れば跨がっていない。もし地表が直線ってことでいいんならここで終わっていい。でも地表を線分と考える場合は見方を次のように変える。

今度は直線 cd をなんとかして地表と考える。そしてイメージするのに邪魔なので ab の線を頭から消す。地表の開始点 c からはさみで線分 ab の両端をつかむ。ここでは d からつかんでもよい。そして時計の2時ぐらいの方向に太陽があると考えれば cd が地表に見えてくる。すると a も b も地面に埋まっているように見える。つまり「負と負」なので跨がってないのがわかる。

次に b だけ空中に出してみる。

これは「正と負」なので跨がっている。

これはどちらも空中なので「正と正」で跨がっていない。

考え方のまとめ

「ab を地表と見たとき ac ad が地表を跨いでいる」かつ、

「cd を地表と見たとき ca cb が地表を跨いでいる」ときに、

線分 ab cd は交差していると言える。

計算方法

a = V[280.0, 90.6]
b = V[600.0, 38.4]
c = V[400.0, 32.0]
d = V[480.0, 102.4]

ab = b - a
cd = d - c
ac = c - a
ad = d - a
ca = a - c
cb = b - c

ac.cross(ab) * ad.cross(ab)  # => -177529408.00000006
ca.cross(cd) * cb.cross(cd)  # => -178229248.00000003

両方負であれば交差している。

補足. 正規化する必要はない

地面までの長さがリアルに出た方が動作確認しやすいかなと考えて地表ベクトルを正規化したが「判定に必要なのは符号だけ」なので正規化する必要はない。

参照

• C# : 線分交差基本に忠実編
• 内積外積、位置判定、交差判定、交点計算
• 2Dの線分と線分の当たり判定

コード

class App < Base
  def initialize
    super

    self.width, self.height = V[800, 128]

    a = window_wh * V[0.35, 0.70]  # => (280.0, 89.6)
    b = window_wh * V[0.75, 0.30]  # => (600.0, 38.4)
    c = window_wh * V[0.50, 0.25]  # => (400.0, 32.0)
    d = window_wh * V[0.60, 0.80]  # => (480.0, 102.4)

    @points.concat([a, b, c, d])

    @mode = 0
  end

  def button_down(id)
    super

    if id == Gosu::KB_Z
      @mode = @mode.next.modulo(3)
    end
  end

  def draw
    super

    a, b, c, d = @points
    ab = b - a
    cd = d - c
    ac = c - a
    ad = d - a
    bc = c - b
    bd = d - b
    ca = a - c
    cb = b - c

    if @mode == 0
      vector_draw(a, b, "a", "b")
      vector_draw(c, d, "c", "d")
      vputs "a: #{a.round}"
      vputs "b: #{b.round}"
      vputs "c: #{c.round}"
      vputs "d: #{d.round}"
    end

    if @mode == 1
      vputs "ac×ab = #{ac.cross(ab.normalize).round(2)}"
      vputs "ad×ab = #{ad.cross(ab.normalize).round(2)}"
      vputs "ac×ab * ad×ab = #{(ac.cross(ab.normalize) * ad.cross(ab.normalize)).round(2)}"
      vector_draw(a, b, "a", "b")
      vector_draw(a, c, " ", "c")
      vector_draw(a, d, " ", "d")
      line_draw(c, d, color: :grey)
    end

    if @mode == 2
      vputs "ca×cd = #{ca.cross(cd.normalize).round(2)}"
      vputs "cb×cd = #{cb.cross(cd.normalize).round(2)}"
      vputs "ca×cd * cb×cd = #{(ca.cross(cd.normalize) * cb.cross(cd.normalize)).round(2)}"
      vector_draw(c, d, "c", "d")
      vector_draw(c, a, " ", "a")
      vector_draw(c, b, " ", "b")
      line_draw(a, b, color: :grey)
    end
  end

  show
end