関数judge_inside マニュアル

(The documentation of function judge_inside)
Last Update: 2021/12/1


◆機能・用途(Purpose)

指定した点が多角形の内部の点か外部の点かを判定する。
Judge if a specified point is inside or outside of a polygon.

◆形式(Format)

#include <geometry.h>
inline int judge_inside
(const double x,const double y,const int Nedges,double edges[][2])


◆引数(Arguments)

x 判定を行いたい点の\(x\)座標。
The \(x\)-coordinate of the point to judge.
y 判定を行いたい点の\(y\)座標。
The \(y\)-coordinate of the point to judge.
Nedges 多角形の頂点の数。
The number of the edges of the polygon.
edges 多角形の頂点のリスト。 頂点の個数を\(N\), \(n\)番目の頂点の座標を\((x_n,y_n)\) (\(n=1,2,\cdots,N\)) として、関数呼び出し前に配列要素を edges[0][0]\(=x_N\), edges[0][1]\(=y_N\), edges[n][0]\(=x_n\), edges[n][1]\(=y_n\) と設定しておくこと。 なお、頂点は反時計回りに与えること。
List of the edges of the polygon. Components of this array must be set before calling this function as edges[0][0]\(=x_N\), edges[0][1]\(=y_N\), edges[n][0]\(=x_n\), and edges[n][1]\(=y_n\), where \(N\) is the number of edges, \(n=1,2,\cdots,N\), and \((x_n,y_n)\) is the coordinate of the \(n\)-th edge for each \(n\). The edges must be specified counterclockwise in order.


◆戻り値(Return value)

\((x,y)\)が多角形の内部の点ならば1、外部の点ならば\(-1\)、 ちょうど多角形の辺上の点ならば0を返す。
The function returns 1 if \((x,y)\) is inside the polygon, \(-1\) if outside the polygon, and 0 if just on a side of the polygon.

◆使用例(Example)

double edges[][2]={{1.0,1.0},{3.0,1.0},{4.0,2.0},{2.0,4.0}};
int judge=judge_inside(2,2,4,edges);
printf("(2,2) is ");
if(judge>0){
    printf("inside ");
}else if(judge<0){
    printf("outside of ");
}else{
    printf("just on a side of ");
}
printf("the square (1,1)-(3,1)-(4,2)-(2,4).\n");

この例では\((2,2)\)は四角形(1,1)-(3,1)-(4,2)-(2,4)の内部に位置するので 「(2,2) is inside the square (1,1)-(3,1)-(4,2)-(2,4).」 と表示される。
Because \((2,2)\) is inside the square (1,1)-(3,1)-(4,2)-(2,4), this program will display “(2,2) is inside the square (1,1)-(3,1)-(4,2)-(2,4).”.

◆アルゴリズム(Algorithm)

多角形の頂点の個数を\(N\), \(n\)番目の頂点の座標を\((x_n,y_n)\) (\(n=1,2,\cdots,N\)), 判定を行いたい点を\((x,y)\)とする。 \((x_0,y_0)=(x_N,y_N)\)として\(n\)の範囲を0まで拡張する。 \((x,y)\)から\((x_n,y_n)\)への方位角を\(\theta_n\)とする。 ここで\(\theta_n\)は\(x\)軸方向から反時計回りに測るものとする。 \(n=1,2,\cdots,N\)について \(n-1\)番目の頂点と\(n\)番目の頂点の間の方位角の増分 \(\Delta\theta_n\equiv\theta_n-\theta_{n-1}\)を計算する。 但し、\(|\Delta\theta_n|\leqq\pi\)となるように \(2\pi\)の整数倍の不確定性を調整する。
Let \(N\) be the number of edges of the polygon, \((x_n,y_n)\) be the coordinate of the \(n\)-th edge (\(n=1,2,\cdots,N\)), and \((x,y)\) be the coordinate of the point to judge. The range of \(n\) is extended to zero by defining \((x_0,y_0)=(x_N,y_N)\). Let \(\theta_n\) be the azimuth from \((x,y)\) to \((x_n,y_n)\), measured counterclockwise from the \(x\)-axis. For \(n=1,2,\cdots,N\), \(\Delta\theta_n\equiv\theta_n-\theta_{n-1}\) is computed, which is the increment of the azimuth from \(n-1\)-th to \(n\)-th edges. The ambiguity of \(2\pi\) is removed by requiring \(|\Delta\theta_n|\leqq\pi\).
このように定義した\(\Delta\theta_n\)を用いて以下の手順で判定を行う。 まず、ある\(n\)についてちょうど \(\Delta\theta_n=\pi\)または\(\Delta\theta_n=-\pi\)となった場合には \((x,y)\)が\((x_{n-1},y_{n-1})\)と\((x_n,y_n)\)を結ぶ線分上に 位置するということであるので その時点で\((x,y)\)は多角形の辺上にあると判断してこの時点で戻り値0を返す。 どの\(n\)についても\(\Delta\theta_n=\pm\pi\)とならない場合、 \(S\equiv\sum_{n=1}^N\Delta\theta_n\)を計算する。 この\(S\)は\((x,y)\)から各頂点への方位角の増分の総和であるので \((x,y)\)が多角形の内部にあれば\(S=2\pi\)、外部にあれば\(S=0\)となる。 このことを用いて内部と外部の判定を行う。
Using \(\Delta\theta_n\) defined in this way, the judge is achieved as follows. If \(\Delta\theta_n=\pi\) or \(\Delta\theta_n=-\pi\) hold for a certain \(n\), \((x,y)\) is just on the line connecting \((x_{n-1},y_{n-1})\) and \((x_n,y_n)\) so that the function returns zero at this stage. If \(\Delta\theta_n\neq\pm\pi\) for all \(n\), the summation \(S\equiv\sum_{n=1}^N\Delta\theta_n\). Because this \(S\) value is the summation of the azimuth increments for all the edges, \(S=2\pi\) if \((x,y)\) is inside the polygon and \(S=0\) if \((x,y)\) is outside of the polygon. Thus the judge is achieved using the \(S\) value.