平面上、整数座標で与えられた線分L と凸多角形P がある。

線分とは、有限長さの直線のこと。

凸多角形とは,多角形内部の任意の2点を結ぶ線分がつねにその多角形に含まれることをいい、凸でない多角形は凹多角形という。なお、ここでいう内部とは、多角形の頂点自体、あるいはその隣り合う頂点を結ぶ線分を含むものとする。つまり、多角形の境界線も内部と見なす。

凸多角形の判定はこのようにできる。つまり、頂点と頂点を結ぶ任意の対角線は,その多角形の内部に含まれる場合、多角形が凸である。

本関数では、与えられた線分Lが、完全に凸多角形Pの内部にある場合は 1と返事、線分Lの一部でも凸多角形Pの外部にある場合は0と返事する。

線分Lは両端が整数座標で与えられるものとする。

多角形Pは頂点数Nが3以上であり、頂点の座標を表す整数の配列 Xk, Yk (ただし、 0<=k<=N-1) が与えられるものとする。

k番目の頂点 (xk, yk) は k+1番目の頂点 (xk+1, yk+1) と腺分でつなぐ。最後のN番目の頂点は最初の1番目の頂点と線分で結ぶ。多角形の線分同士は頂点でしかぶつからない。1つの頂点から線分3本以上出ることはないものとする。

<関数名>
  segmentInsidePolygon —- 線分Lが凸多角形Pの内部にあるかどうかを判定する

<形式>
  int segmentInsidePolygon(int x1, int y1, int x2, y2, int pn, int *px, int *py);

<引数>
  x1, y1, x2, y2  入力 線分Lの両端の座標 (x1,y1), (x2,y2)
  pn   入力 凸多角形Pの頂点数
  px, py 入力 凸多角形Pの頂点の座標配列

<関数値>
  1  線分Lが完全に、凸多角形Pの内部、あるいは、ちょうど凸多角形Pの線分上にある場合。
  0  線分Lが一部でも凸多角形の外部にある場合。

<注意事項>
  凸多角形になっているかどうか、本関数内ではチェックしない。
  
用例

<C言語関数本体>
  segmentInsidePolygon.c

<説明>
  関数の内部では、線分Lの両端が凸多角形Pにあるかどうかの判定を利用している。

Comments are closed.

Post Navigation