algorithm - 三角形的三点中有多少个整数点？

Question

实际上这是 SO 用户的经典问题 Victor把它(在另一个 SO question 中，关于在面试中要问哪些任务)。

我一个小时都做不出来(叹息)那么计算三角形内整数点数的算法是什么？

编辑:假设顶点位于整数坐标处。 (否则它变成了一个问题，找到三角形内的所有点，然后减去所有 float ，只剩下整数点；一个不太优雅的问题)。

Answer 1

假设顶点位于整数坐标，您可以通过在三角形周围构造一个矩形来获得答案，如 Kyle Schultz 的 An Investigation of Pick's Theorem 中所述。 .

对于一个j x k 矩形，内部点的个数是

I = (j – 1)(k – 1).

对于下面的 5 x 3 矩形，有 8 个内部点。

_{(来源:uga.edu)}

对于具有垂直边 (j) 和水平边 (k) 的三角形，内部点的数量由下式给出

I = ((j – 1)(k – 1) - h) / 2

其中 h 是矩形内部与三角形斜边重合的点数(不是长度)。

_{(来源:uga.edu)}

对于具有垂直边或水平边的三角形，内部点数 (I) 由下式给出

_{(来源:uga.edu)}

下图中标出的j,k,h1,h2,b

_{(来源:uga.edu)}

最后，三角形没有垂直或水平边的情况可以分为两种子情况，一种是三角形周围的区域形成三个三角形，一种是周围区域形成三个三角形和一个矩形(参见下图)。

第一个子案例中的内部点数 (I) 由下式给出

_{(来源:uga.edu)}

下图中所有变量都标出

_{(来源:uga.edu)}

第二个子案例中的内部点数 (I) 由下式给出

_{(来源:uga.edu)}

下图中所有变量都标出

_{(来源:uga.edu)}