我正在尝试找到严格位于边界内的格点数。我知道皮克定理是
A = i + b/2 - 1
其中A表示多边形面积，i表示位于多边形内部的格点数目，b表示多边形周长上的格点数目。
使用Shoelace公式可以很容易地求出多边形的面积，但我不确定如何获取边界上的点。
我不太确定在哪里可以找到相关资源，所以我也希望提供相关链接。
2个回答
12
多美好的问题啊...
因为您提到了Pick定理，我会假设所有顶点都有整数坐标。
您的问题归结为确定从(x1, y1)到(x2, y2)的线段上有多少个格点。由于答案在整数平移下保持不变，因此我们可以将其简化为确定任意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)的因子坐标来证明这一点。
最后，在绕行多边形时要小心不要重复计算顶点。
- Nemo
0
为了扩展Nemo的回答，对于多边形的每一条边AB，格点的数量等于gcd(x2 - x1, y2 - y1) + 1，其中A=(x1, y1)，B=(x2, y2)。
- Rexcirus
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接