座標点が不規則なポリゴンの内部にあるかどうかを判断するアルゴリズム
2425 ワード
テキストリンク:https://www.cnblogs.com/anningwang/p/7581545.html
参照先:https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.html
GIS(地理情報管理システム)では,座標が多角形内部にあるか否かを判断することがしばしば問題となる.一見複雑に聞こえる.W.Randolph Franklinが提案したPnPolyアルゴリズムによれば,数行のコードを区別するだけでこの問題を解決した.
多角形の座標が1つの配列に格納されていると仮定すると、まずその配列が横座標と縦座標の最大値と最小値を取得する必要があり、この4つの点から4辺型を算出し、まず目標座標点がこの4辺型内にあるかどうかを判断し、この4辺型以外であれば、後の複雑な計算をスキップしてfalseに戻ることができる.
if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
//このテストは合格できません...falseに直接戻ります.
}
次に、コアアルゴリズムのセクションを示します.
1 2 3 4 5 6 7 8 9 10
Argument
Meaning
nvert
Number of vertices in the polygon. Whether to repeat the first vertex at the end is discussed below.
vertx, verty
Arrays containing the x- and y-coordinates of the polygon's vertices.
testx, testy
X- and y-coordinate of the test point.
ええ、コードは簡単ですが、どういう意味ですか.
まず、パラメータnvertはポリゴンにいくつかの点を表す.浮動小数点数testx,testyは試験対象点の横座標と縦座標を表し,*vertx,*vertyはそれぞれ多角形の横縦座標配列を格納するヘッダアドレスを指す.
計算のたびに隣接する2つの点とテスト対象の点に関連し,2つの問題を考慮することに気づいた.
1.被試験点の縦座標testyは、今回のサイクルで試験した2つの隣接点の縦座標範囲内であるか.すなわち
verty[i]
または
verty[j]
2.測定対象のtestはi,j 2点間の接続線の下にありますか?後半の短いif statementが分からない方は、自分で紙にi,jの2点間の傾きの公式を書いてください.中学校で幾何学と不等式を解析する知識の範疇を使うのは、私たちにとっておかずの一皿です.
そして、この2つの条件が同時に満たされるたびに、私たちは戻ったブール量を逆にします.
しかし、これはいったいどういう意味ですか.
この式の意味は、多角形を勝手に描いて、勝手に点を決めて、それからこの点を通じて水平に線を引いて、まずこの横線と多角形の辺が何回交差しているかを数えて、(あるいは交差しない辺を排除して、最初の判断条件)、それからこの横線が多角形を通り抜ける回数が奇数であるかどうかを数えて、奇数であれば、では、この点はポリゴン内にあり、偶数であればポリゴンの外にあります.詳しい数学の証明はここではしませんが、読者は自分で多角形を描いて検証することができます.
参照先:https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.html
GIS(地理情報管理システム)では,座標が多角形内部にあるか否かを判断することがしばしば問題となる.一見複雑に聞こえる.W.Randolph Franklinが提案したPnPolyアルゴリズムによれば,数行のコードを区別するだけでこの問題を解決した.
多角形の座標が1つの配列に格納されていると仮定すると、まずその配列が横座標と縦座標の最大値と最小値を取得する必要があり、この4つの点から4辺型を算出し、まず目標座標点がこの4辺型内にあるかどうかを判断し、この4辺型以外であれば、後の複雑な計算をスキップしてfalseに戻ることができる.
if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
//このテストは合格できません...falseに直接戻ります.
}
次に、コアアルゴリズムのセクションを示します.
1 2 3 4 5 6 7 8 9 10
int pnpoly( int nvert, float *vertx, float *verty, float testx, float testy) { int i, j, c = 0; for (i = 0, j = nvert-1; i < nvert; j = i++) { if ( ((verty[i]>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ) c = !c; } return c; } Argument
Meaning
nvert
Number of vertices in the polygon. Whether to repeat the first vertex at the end is discussed below.
vertx, verty
Arrays containing the x- and y-coordinates of the polygon's vertices.
testx, testy
X- and y-coordinate of the test point.
ええ、コードは簡単ですが、どういう意味ですか.
まず、パラメータnvertはポリゴンにいくつかの点を表す.浮動小数点数testx,testyは試験対象点の横座標と縦座標を表し,*vertx,*vertyはそれぞれ多角形の横縦座標配列を格納するヘッダアドレスを指す.
計算のたびに隣接する2つの点とテスト対象の点に関連し,2つの問題を考慮することに気づいた.
1.被試験点の縦座標testyは、今回のサイクルで試験した2つの隣接点の縦座標範囲内であるか.すなわち
verty[i]
または
verty[j]
2.測定対象のtestはi,j 2点間の接続線の下にありますか?後半の短いif statementが分からない方は、自分で紙にi,jの2点間の傾きの公式を書いてください.中学校で幾何学と不等式を解析する知識の範疇を使うのは、私たちにとっておかずの一皿です.
そして、この2つの条件が同時に満たされるたびに、私たちは戻ったブール量を逆にします.
しかし、これはいったいどういう意味ですか.
この式の意味は、多角形を勝手に描いて、勝手に点を決めて、それからこの点を通じて水平に線を引いて、まずこの横線と多角形の辺が何回交差しているかを数えて、(あるいは交差しない辺を排除して、最初の判断条件)、それからこの横線が多角形を通り抜ける回数が奇数であるかどうかを数えて、奇数であれば、では、この点はポリゴン内にあり、偶数であればポリゴンの外にあります.詳しい数学の証明はここではしませんが、読者は自分で多角形を描いて検証することができます.