はじめに
前回に引き続き,
前回の復習
最初に,
- 2つの凸多角形の交差部分は,
同じく凸多角形になる - 2つの凸多角形の交差計算には,
第3回~第5回で解説した平面走査法を応用できる - 走査線と交わる線分は,
left_ edge_ c1, right_ edge_ c1, left_ edge_ c2, right_ edge_ c2のたかだか4個である (図1) - イベント点となるのは,
入力の凸多角形の頂点のみである - left_
edge_ c1, right_ edge_ c1, left_ edge_ c2, right_ edge_ c2の4辺の各終点のうち, もっとも上にある点が次のイベント点になる
交差計算のデモプログラム
それでは早速,
このリンクをクリックしてください。Java Web Start形式のプログラムが起動します。これは,
ウィンドウの中には,
画面上部の
2つの凸多角形をいろいろな配置に変えて,
走査線の開始位置
では最初の問題として,
この位置は,