我试图找到严格位于边界内的格点数.我知道Pick的定理是
A = i + b/2 - 1
其中A =多边形的面积,i是多边形内部的晶格点数,b是多边形周长上的晶格点数.
我可以使用Shoelace公式轻松找到该区域,但我不确定如何获得边界上的点.
我不确定在哪里寻找资源,所以我也很欣赏链接.
Nem*_*emo 11
真是个问题......
既然你在谈论Pick的定理,我会假设所有的顶点都有整数坐标.
您的问题减少到确定从(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)因子的坐标.
最后,小心不要在走动多边形时重复计算顶点.