确定四边形内部或四边形上的积分坐标的数量

Question

有人能告诉我任何算法吗？我可以通过它找到四边形内部或上的积分坐标总数。四边形的坐标将作为输入，你必须告诉四边形内部或上面的坐标总数。例如，如果给出的点是(5,3)(1,1)(3,4)(6,1)，那么答案应该是14。如果你画四边形，你会发现只有14个积分坐标，比如(3,2)，(5,1)。。等等位于四边形内部和四边形上。

Answer 1

如果四边形顶点具有整数坐标，则可以使用Pick定理。

A = i + b/2 - 1

其中，A是面积，i是内部整数点的数量，b是边界(边)处的整数点数量。您可以使用任何方法找到四边形区域(例如，请参见此处)，并将每条边上的边界点数量作为GCD(dx，dy)(排除+1项以避免对顶点进行两次计数)