给定边长的网格多边形面积

Question

输入：

Table T，长度为 N（N <= 10000），包含 32 位整数。每个整数表示正方形网格上多边形连续边的长度和方向（每个顶点都有整数坐标）。如果整数为正数，则表示边缘向上或向右。如果整数为负，则边缘向下或向左。边垂直于它的邻居。边既不相交也不重叠。顶点不相互重叠。

示例输入 T:

2, -3, -1, 1, -1, 2

表示两个多边形（选择哪个并不重要）：

箭头表示对应于 T.

中第一个 2 的第一条边

输出：

表示给定多边形表面积的整数。对于示例性输入，输出应为 5.

所需的时间复杂度：O(N)
所需的内存复杂度（不计算输入）：O(1)

您能介绍一下这样的算法及其背后的原理吗？

Answer 1

算法：

int area(int[] T) {
    int area = 0;
    int x = 0;
    for (int i = 0; i < T.length; i += 2) {
        x += t[i];
        area += x * t[i + 1];
    }
    return Math.abs(area);
}

描述：

我们的多边形封闭在一个大矩形中。基于此，我们正在计算构建形状的小矩形的面积 - 多边形内部的矩形以及外部的矩形（符号相反）。

我们从多边形的哪个顶点开始并不重要。一开始我们需要一个基线，我们将从中计算垂直（也可以是水平的，没关系）顶点的平移。我们得到第一个数字 - 它会告诉我们，我们的第一个顶点从基线移动了多少。第二个数字是根据第二个坐标的平移。通过将这对相乘，我们得到了总和中的第一个矩形。

第二个矩形由第三点和第四点描述：

第一个数加上第三个数是顶点的垂直平移
第四个数字是顶点的水平平移。将这些点相乘得到第二个矩形。

我们将继续对 table 中的其余号码执行此操作。我们正在添加矩形区域。结果是总和的绝对值。

给定边长的网格多边形面积

Area of grid polygon given length of edges

language-agnostic

algorithm

geometry