📐

点の垂線が線分内にあるか判定する

2023/09/14に公開

考え方

  1. 線分 ab の両端から点 c に向ってベクトルを作る
  2. 2つの斜辺の正射影を求める
  3. 一方が負なら内側にある

計算手順

a = V[560.0, 280.0]
b = V[240.0, 280.0]
c = V[400.0, 120.0]

ベクトル化。必要なのは符号なので ab は正規化しなくてもよい。

ab = b - a          # => (-320.0, 0.0)
ac = c - a          # => (-160.0, -160.0)
bc = c - b          # => (160.0, -160.0)
abn = ab.normalize  # => (-1.0, 0.0)

両方の正射影の強さを求める。

ax = ac.dot(abn)  # => 160.0
bx = bc.dot(abn)  # => -160.0

一方が負か調べる。

inside = (ax * bx).negative?  # => true

外積を使う方法

ax = ac.cross(abn.perp)  # => 160.0
bx = bc.cross(abn.perp)  # => -160.0

直線の法線を地面とし、その地面に垂線を降ろしたときにできる三角形をイメージして対辺(直立射影)を求める方法もある。法線との直線距離をイメージしている場合はこっちの方があっているかもしれない。だだ法線を求めるのが若干遠回りなような気もしないでもない。計算量的には変わらない。

間違えやすい考え方

「互いに向き合っていれば内側にいるんだから斜辺同士の内積を取ってマイナスになっているか一発で判断する」のは間違い。

たしかに c が線上にあったり c の角が鈍角(90度以上)ならそれでもよい。しかし、鋭角になると同じ方向を向いていることになるため内積はプラスを示す。そうなると範囲に含まれているのに c が近いか遠いかで判定が変わってしまう。

コード
class App < Base
  def initialize
    super

    a = window_wh * V[0.70, 0.70]  # => (560.0, 280.0)
    b = window_wh * V[0.30, 0.70]  # => (240.0, 280.0)
    c = window_wh * V[0.50, 0.30]  # => (400.0, 120.0)

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

    @mode = 0
  end

  def button_down(id)
    super

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

  def draw
    super

    a, b, c = @points
    ab = b - a
    ba = a - b
    ac = c - a
    bc = c - b
    abn = ab.normalize

    point_draw(c)
    arrow_head(a.lerp(b, 0.5), c, "c")

    vputs "a: #{a.round}"
    vputs "b: #{b.round}"
    vputs "c: #{c.round}"
    vputs
    vputs "ab: #{ab.round}"
    vputs "abn: #{abn.round}"
    vputs
    vputs "ac・abn = #{ac.dot(abn).round}"
    vputs "bc・abn = #{bc.dot(abn).round}"
    vputs
    vputs "ac×(abnの法線) = #{ac.cross(abn.perp).round}"
    vputs "bc×(abnの法線) = #{bc.cross(abn.perp).round}"
    vputs
    vputs (ac.dot(abn) * bc.dot(abn)).negative?

    vector_draw(a, b, "a", "b", arrow: false)

    line_draw(a, a + abn.perp, infinity: true)
    vector_draw(a, c, "", "", color: :blue_light)
    vector_draw(a, a + ac.project_onto_normalized(abn), "", "", color: :blue, line_width: 2)

    line_draw(b, b + abn.perp, infinity: true)
    vector_draw(b, c, "", "", color: :red_light)
    vector_draw(b, b + bc.project_onto_normalized(abn), "", "", color: :red, line_width: 2)
  end

  def window_size_default
    V[800, 400]
  end

  show
end

Discussion