c++ - 计算由已知整数坐标点界定的区域面积

Question

首先，请看这张图:

考虑正方形代表笛卡尔点，星号标记 (0, 0) 点。

在图中，给定的点是(按三角顺序并在图像中用'-'标记):(0, 0); (0, 1); (0, 2); (-1, 2); (-2, 2); (-2, 1); (-3, 1); (-3, 0); (-3, -1); (-2, -1); (-2, -2); (-1, -2); (0, -2); (1, -2); (1, -1); (1, 0).

鉴于(只是!)上面的点，我如何确定灰色方 block 的面积(张贴图片中的 5 个)？ ("已指定点确定的多边形内整数坐标点的个数")

我想用 C++ 实现类似的东西。这就是我在 StackOverflow 上发布问题的原因。但是一旦有人向我解释了如何(几何方法或其他方法)，我希望我能够自己实现它。

非常感谢任何帮助!非常感谢!

Answer 1

您可以使用众所周知的algorithm for area of polygon , 按顺序由顶点定义。

A = Abs(1/2*Sum(X(i)*Y(i+1)-X(i+1)*Y(i)))

然后使用Pick theorem查找轮廓内具有整数坐标的点数:

i=A-b/2+1

其中A为面积，b为边界点数。

对于这个例子

i=12-16/2+1=5