内点を求めるプログラム

質問

A(0.5,0)
B(0.5,0.3)
C(0,1)
D(-0.6,0)
E(-0.3,-0.2)
F(0,-0.6)
を結ぶ6角形を考える時、平面上の任意の点に対し、その点が6角形の内点か否かを判定するプログラムを作りたいです。すべての内角が90°＜θ＜180°なら簡単にできるんですけど、角Eの所が180°以上になるので、どうやって求めればいいかわかりません。どなたか教えてもらえませんか？

回答No.2

chie65536 · ベストアンサー

質問者さんへ。

ここを参考にしてみて下さい。
http://kone.vis.ne.jp/diary/diaryb09.html

No.1さんへ。

参考ＵＲＬにも書いてありますが、単純に半直線と交差する回数を数えただけでは（半直線が多角形の頂点上を通過する場合に）失敗します。

参考URL：

http://kone.vis.ne.jp/diary/diaryb09.html

回答No.3

sunasearch

この６角形に限るのでしたら、例えば、点Cから点A,点F,点Eに３本の対角線を引き４つの三角形に分割して、各三角形の内部にあるかどうかを判定すれば良いかと思います。

一般的な多角形も、三角形に分割できれば同じことです。
分割するアルゴリズムを考える必要はありますが。

回答No.1

Tacosan

調べたい点を端点とする半直線を考え, これと交差する辺の本数を数えればいいような気がしますが?