数学と情報処理のどちらにも関わる問題です（といっても大難問ではありませ

質問

数学と情報処理のどちらにも関わる問題です（といっても大難問ではありません）。平面上の閉曲線のデータが離散的に与えられているとします。結局は多角形ということになりますが。三角形はそのもっともシンプルな例ですね。とりあえず、外側に凸ということだけは仮定されています。
n個の構成点のデータとしては、時計まわりか反時計まわりかを決めて
1 x1,y1
2 x2,y2
3 x3,y3
.......
n xn,yn
という風になりますね。よくある話かと思いますが、１つの辺のデータの両端の座標 (xi,yi),(xi+1,yi+1)を元にその単位法線ベクトルが計算できます。法線ベクトルは多角形の内向きと外向きの2方向となりますが、外向きか内向きはどのようにして判断できるでしょうか。とりあえず外向きだけが必要なのですが。両端の点だけではだめでほかの構成点を使えばできると思いますが、具体的にどのような感じのアルゴリズムになるでしょうか。反時計まわりのデータだったら進行方向に向かって別の点は必ず左側にあるとか。簡単で確実な方法が知りたいのですが。
よろしくお願いします。

回答No.1

178-tall · ベストアンサー

>法線ベクトルは多角形の内向きと外向きの2方向となりますが、外向きか内向きはどのようにして判断できるでしょうか。

「外に凸」なら、各辺の凸領域側はわかるわけですね。

たとえば辺 [X(k), Y(k)] → [X(k+1), Y(k+1)] の進行方向右側が凸領域の場合。
辺ベクトル [X(k+1)-X(k), Y(k+1)-Y(k)] = [Rk, Sk] の外に向かう法線ベクトルは [-Sk, Rk] … 。