指定された点が指定された多角形の内部にあるか外部にあるかを判定したい。
多角形のすべての辺について、点から水平に延ばした半直線との交差回数を調べる。
点Aのように交差回数が奇数回ならば内部、点Bのように交差回数が偶数回又は0ならば外部とする。
点Cのように半直線が多角形の頂点上を通過する場合、二つの辺の端点(上端又は下端)と交差することになるが、このときの交差回数の数え方として、適当なものはどれか。
ここで、多角形に水平な辺はないものとし、辺の上の点は考えない。
| ア | それぞれの辺について、下端での交差は0回、上端での交差は1回とし、合計したものを交差回数とする。 |
| イ | 二つの辺それぞれを0回とし、交差回数には加えない。 |
| ウ | 二つの辺それぞれを0.5回、つまり合計で1回の交差回数とする。 |
| エ | 二つの辺それぞれを1回、つまり合計で2回の交差回数とする。 |
答え ア
【解説】
考え方としては点Cが多角形の内部にあるので交差回数が奇数回になるような数え方をする必要がある。
したがって、選択肢イやエのように0回または2回(偶数回)となるような方法は間違いである。
次に、点からの半直線が辺の端点を通るケースには、下図の点Dと点Eがある。
この点D、点Eはともに多角形の外部にあるので交差回数が偶数回となるような数え方である必要があり、これを満足するのは『それぞれの辺について、下端での交差は0回、上端での交差は1回とし、合計したものを交差回数とする。』(ア)である。
【キーワード】
・点位置決定問題
- 点位置決定問題
指定された点が領域の内部か外部にあるかを判定するという幾何学の問題です。
この問題の考えかたは領域探索などで使用されます。
もっと、「点位置決定問題」について調べてみよう。
戻る
一覧へ
次へ