©2024 Thoth Children All rights reserved.

線分交叉判定

ー 概要 ー

複数の線分を与えられたときにそれらの中に一つでも交差(交叉)しているものがあるかないかを効率よく確認し真偽を返す.平面走査法によって実現することができ、計算時間はO(nlog(n))となる.
Facebookシェア Twitterツイート LINEで送る このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
0
条件
  • 複数の線分
効果
  • 線分に交叉があるかないかを判定
ポイント
  • 時間計算量はO(n log(n))
  • 平面走査法によって探索を行う.確認のイベントは線分の端点でのみ行う.
  • 捜査線が交わっている線分のリストを持ち、端点で追加または削除を行う
  • 追加削除のタイミングで上下の線分と交差がないか確認.

解 説

線分交叉判定は複数の線分を与えられたときにそれらの中に一つでも交叉しているものがあるかないかを効率よく確認し判定を行う. 平面走査法によって実現することができ、点数がnとしたときに計算時間はO(nlog(n))となる. 処理概要 ・線分の左端と右端が処理のタイミング.全部で2n回ある. ・特定の方向に走査することを決めたら、その方向に線分のすべての点をソートする. ・捜査線が交わっている線分のリストを常に持ち、線分のリストは交わっている点の座標でソートされている. ・左端を処理するタイミングでは新しくその線分を交わっている位置に応じて適切な位置に挿入する.このとき、リストの中で加わった線分と上下の線分との交差を確認する. ・右端を処理するタイミングでは新しくその線分を除去する.このときリストの中で除去した線分の上下同士の線分で交差を確認する.
線分交叉判定とは
線分の交差判定をする例. 左の例では1と4が交わっているため「交わっている」と判定される. 下の線分リストが更新されていく. 追加のときは追加された線分と上下の線分と交差を確認. 削除のときは削除する線分の上下で確認を行っている.
この章を学んで新たに学べる
Comments

Reasons
>>隠す