给定方向列表，计算面积

Question

假设你收到了一份指示列表：

up, up, right, down, right, down, left, left

如果你按照这些指示行进，你将始终回到起点。计算刚刚创建的图形的面积。

根据上述指示形成的图形大致如下：

 ___
|   |___
|_______|

从图片中可以清晰地看到，面积为3。

我尝试使用二维数组来跟踪方向，但不确定如何从中获取面积...

例如，在我的二维数组中：

O  O
O  O  O
O  O  O

这可能不是处理此事的好方法，有什么想法吗？

- Vic

---

也许只需像其他答案中建议的那样使用测量员公式。在你的特定情况下，可能有更简单和高效的方法，但是测量员公式在这里也是非常好的选择。 - wsdookadr

这些线条会自相交吗？ - Pham Trung

@PhamTrung 假设它们不相交。 - Vic

Answer 1

由于您创建的多边形仅具有轴对齐的边缘，因此可以从垂直板块计算总面积。

假设我们有一个顶点列表V。 我们假设在此列表中进行包装，因此我们可以查询每个顶点v in V的V.next(v)。 对于最后一个顶点，结果是第一个顶点。

首先，尝试找到最左和最右的点以及到达最左点的顶点（在线性时间内）。

x = 0                       // current x-position
xMin = inf, xMax = -inf     // leftmost and rightmost point
leftVertex = null           // leftmost vertex
foreach v in V
    x = x + (v is left ? -1 : v is right ? 1 : 0)
    xMax = max(x, xMax)
    if x < xMin
        xMin = x
        leftVertex = V.next(v)

现在我们创建一个简单的数据结构：对于每个垂直板，我们保留最大堆（排序列表也可以，但我们只需要在最后重复获取最大元素）。

width = xMax - xMin
heaps = new MaxHeap[width]

我们现在开始从顶点leftVertex开始跟踪形状（即我们在第一步中找到的最左侧的顶点）。我们选择将该顶点的x/y位置设置为(0, 0)，仅仅是因为这样更加方便。

x = 0, y = 0
v = leftVertex
do
    if v is left
        x = x-1         // use left endpoint for index
        heaps[x].Add(y) // first dec, then store
    if v is right
        heaps[x].Add(y) // use left endpoint for index
        x = x+1         // first store, then inc
    if v is up
        y = y+1
    if v is down
        y = y-1

    v = V.next(v)
until v = leftVertex

你可以在 O(n log n) 的时间内构建此结构，因为向堆中添加元素的成本是对数级别的。

最后，我们需要从堆中计算面积。对于格式正确的输入，我们需要从堆中获取两个连续的 y 值并相减。

area = 0
foreach heap in heaps
    while heap not empty
        area += heap.PopMax() - heap.PopMax() // each polygon's area

return area

同样的，这需要O(n log n)的时间。

---

我将算法移植到了Java实现（见Ideone）。两次样本运行如下：

public static void main (String[] args) {
    //  _
    // | |_
    // |_ _ |
    Direction[] input = { Direction.Up, Direction.Up, 
                          Direction.Right, Direction.Down,
                          Direction.Right, Direction.Down,
                          Direction.Left, Direction.Left };

    System.out.println(computeArea(input));

    //  _
    // |_|_
    //   |_|
    Direction[] input2 = { Direction.Up, Direction.Right, 
                           Direction.Down, Direction.Down,
                           Direction.Right, Direction.Up,
                           Direction.Left, Direction.Left };

    System.out.println(computeArea(input2));
}

返回结果（如预期）：

3
2

- Vincent van der Weele

---

这个实现过于复杂了。使用鞋带公式可以实现O(n)，而且可能更容易实现。 - Sopel

@Sopel，我以前从未听说过鞋带公式算法，但它看起来确实简单得多！请将其发布为答案 :) - Vincent van der Weele

Answer 2

假设有一个起点（比如，(0,0)），并且y方向为正向上：

- 左移将(-1,0)加到上一个点。 - 右移将(+1,0)加到上一个点。 - 上移将(0,+1)加到上一个点。 - 下移将(0,-1)加到上一个点。

一系列的方向会产生一个(x,y)顶点坐标列表，从中可以计算出所得到的（隐含闭合的）多边形的面积，方法请参考如何计算二维多边形的表面积？ 编辑

下面是Python的实现和测试。前两个函数来自上面链接的答案：

def segments(p):
    return zip(p, p[1:] + [p[0]])

def area(p):
    return 0.5 * abs(sum(x0*y1 - x1*y0
                         for ((x0, y0), (x1, y1)) in segments(p)))

def mkvertices(pth):
    vert = [(0,0)]
    for (dx,dy) in pth:
        vert.append((vert[-1][0]+dx,vert[-1][1]+dy))
    return vert

left = (-1,0)
right = (+1,0)
up = (0,+1)
down = (0,-1)

#  _
# | |_
# |__|
print (area(mkvertices([up, up, right, down, right, down, left, left])))
#  _
# |_|_
#   |_|
print (area(mkvertices([up, right, down, down, right, up, left, left])))

输出：

3.0
0.0

请注意，对于包含相交线的多边形，该方法将失败，就像第二个示例一样。

- Simon

Answer 3

这可以使用Shoelace公式实现简单多边形的原地计算。

对于每个线段(a, b)，我们必须计算(b.x - a.x)*(a.y + b.y)/2。所有线段的总和是多边形的有向面积。

此外，这里只涉及长度为1的轴对齐线段。垂直线段可以忽略，因为b.x - a.x = 0。水平线段具有a.y + b.y / 2 = a.y = b.y和b.x - a.x = +-1。

因此，最终我们只需要跟踪y，添加的面积始终是+-y

这是一个示例C++代码：

#include <iostream>
#include <vector>

enum struct Direction
{
    Up, Down, Left, Right
};

int area(const std::vector<Direction>& moves)
{
    int area = 0;
    int y = 0;

    for (auto move : moves)
    {
        switch(move)
        {
            case Direction::Left:
                area += y;
                break;
            case Direction::Right:
                area -= y;
                break;
            case Direction::Up:
                y -= 1;
                break;
            case Direction::Down:
                y += 1;
                break;
        }
    }

    return area < 0 ? -area : area;
}

int main()
{
    std::vector<Direction> moves{{
        Direction::Up, 
        Direction::Up, 
        Direction::Right, 
        Direction::Down, 
        Direction::Right,
        Direction::Down, 
        Direction::Left, 
        Direction::Left
        }};

    std::cout << area(moves);

    return 0;
}

- Sopel

Answer 4

我认为在绘制形状时应该有一些限制（轴对齐、多边形图形、闭合、不相交的线段），以便能够计算面积。

使用线段来表示形状，每个线段由两个点组成，每个点都有两个坐标：x和y。

考虑到这些假设，我们可以说任何水平线段都有一个平行线段，其两个点具有相同的x维度但不同的y维度。

这两个线段之间的表面积等于它们之间的高度差。将所有水平线段的面积相加即可得到形状的总表面积。

- Muhammad Soliman

---

如果水平线段有多个平行线段（相同的x，不同的y），会怎么样？ - Vic

然后这些线段是成对出现的，因此需要计算每一对之间的面积。 - Muhammad Soliman