计算多边形中格点数的算法

Question

我试图找到严格位于边界内的格点数。我知道匹克定理是

A = i + b/2 - 1

其中 A = 多边形的面积，i 是位于多边形内部的格点数，b 是多边形周边的格点数。

我可以使用 Shoelace 公式轻松找到该区域，但我不确定如何获取边界上的点。

我不太确定在哪里可以找到这方面的资源，所以我也希望能提供链接。

Answer 1

多么漂亮的问题...

既然你在谈论匹克定理，我假设所有的顶点都有整数坐标。

您的问题简化为确定从 (x₁, y₁) 到 (x₂) 的线段上有多少格点, y₂).由于通过整数转换后答案保持不变，这就简化为确定对于任意 x 和 y，从 (0, 0) 到 (x, y) 的线段上有多少格点。

如果 x=0 或 y=0，答案是一维且平凡(即 x+1 或 y+1)。

否则，答案是 gcd(x,y) + 1。您通过显示 (a) (0,0) 和 (x,y) 之间的任何格点必须是“最小”的倍数来证明这一点格点； (b) 任何格点的坐标都必须是 (x,y) 的因数。

最后，当您在多边形周围走动时，请注意不要重复计算顶点。