在C中计算直线多边形的面积

Question

我必须为一组给定的输入值开发一个 C 程序，我们在其中通过指定起点和四个基本方向上的一系列运动来描述矩形图形的边界——就好像我们在四处走动沿其边界形成。
我们输入每个运动的方向（WESN）和长度——“W 3”表示从当前位置向西（左）移动三步。

从右上角开始，图 1 中的图形可以描述为：

"W 6, S 2, W 3, S 2, E 1, S 2, E 2, N 1, E 2, N 1, E 2, N 1, W 2, N 1, E 3, S 3, E 1, N 5".

我的问题是：

这样的形状在几何学中叫什么？
如何计算这种形状的面积？我有所有边的长度，如 W6、S4 等

谢谢。

Answer 1

这可以称为直线多边形。

计算任何多边形面积的通用算法是：

设 (xo, yo) 为起点（旧的“o”）。
将总和 S 初始化为零。
对于每个动作：
- 根据运动和旧点计算新点（xn，yn）（“n”表示新）。
- 将 xn•yo−xo•yn 添加到 S。
- 设置 xo=xn 和 yo=yn。
多边形内部的面积是|S|/2。

以上假设最后一个动作是闭合多边形，所以最后一个点就是起点。如果不是，则应保存起点的副本并用于完成与最后一个点的求和。

这里使用了sum/algorithm chux指出的

Answer 2

形状叫做polyomino。这是多边形的特例。

从点 (0,0) 开始，用面积 0 的多边形可以解决求面积的问题。接下来，在水平移动的同时按矩形扩展区域。

假设当前点为(x,y)。向东移动 d 个单位意味着在点 (x,0) -> (x,y) -> (x + d, y) -> (x + d, 0) 处添加一个矩形。矩形的面积是d * y。向西移动时需要减去矩形。

如果顺时针行走，则最终面积为正；如果路径逆时针，则最终面积为负。

这种方法产生了一个非常简单的程序：

#include <stdio.h>

int main() {
    int x = 0, y = 0, A = 0, d;
    int c;
    while ((c = getchar()) != EOF) { 
        if        (c == 'W' && scanf(" %d", &d) == 1) {
            x += d;
            A += d * y;
        } else if (c == 'E' && scanf(" %d", &d) == 1) {
            x -= d;
            A -= d * y;
        } else if (c == 'N' && scanf(" %d", &d) == 1) {
            y += d;
        } else if (c == 'S' && scanf(" %d", &d) == 1) {
            y -= d;
        }
    }
    if (A < 0) A = -A;
    printf("%d\n", A);
    return 0;
}

问题的输入给出了 33 的预期答案。

在C中计算直线多边形的面积

Calculate area of Rectilinear Polygon in C

c

math

geometry

area