2011/10/18

線分の交叉判定(てきとう)

今日のテーマは、平面上における線分の交叉性を判定する計算幾何の問題です。

地味な上にそれほど大した事はない(というかつまらない)なのですが、備忘録的な意味で残しておきます。

以下の動画は、マウスで描画したストロークのうち、交叉している領域を(半リアルタイムで)見つけ出してマーキングする様子のデモです。交叉している領域は、で囲われます。



今回は、2線分の交点座標を求めず、単に交叉性のみを判定する事によって、処理を少しだけ軽くしてある辺りがチャームポイント。動画の 1 分前後からはワンストロークにおける自分自身との交叉判定も可能である事を示しています。

最適化のために頑張った割には、デモが地味すぎて悲しいので今日はこの辺で……。

0 件のコメント:

コメントを投稿

ひとことどうぞφ(・ω・,,)