厳密に境界の内側にある格子点の数を見つけようとしています。ピックの定理は
A = i + b/2 - 1
ここで、A =ポリゴンの面積、iはポリゴンの内側にある格子点の数、bはポリゴンの周囲にある格子点の数です。
靴ひもの式を使用して領域を簡単に見つけることができますが、境界上の点を取得する方法がわかりません。
これに関するリソースをどこで探すべきかよくわからないので、リンクもいただければ幸いです。
なんて素敵な質問...
ピックの定理について話しているので、すべての頂点が整数座標を持っていると仮定します。
あなたの質問は、(x 1、y 1)から(x 2、y 2)までの線分にある格子点の数を決定することになります。答えは整数による平行移動の下で同じままであるため、これは、任意のxおよびyについて、(0、0)から(x、y)までの線分上にある格子点の数を決定することになります。
x = 0またはy = 0の場合、答えは1Dで自明です(つまり、x +1またはy + 1)。
それ以外の場合、答えはgcd(x、y)+ 1です。(a)(0,0)と(x、y)の間の格子点は、「最小」格子点の倍数でなければならないことを示すことで、これを証明します。(b)格子点は、(x、y)の因数である座標を持たなければならないこと。
最後に、ポリゴンを歩き回るときに頂点を二重に数えないように注意してください。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加