计算给定方向列表的面积

Question

假设您获得了一份路线列表：

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

如果您按照指示行事，您总会return到达起始位置。计算您刚刚创建的形状的面积。

由上面的方向形成的形状看起来像：

 ___
|   |___
|_______|

很明显，从图中可以看出面积是3。

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

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

O  O
O  O  O
O  O  O

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

Answer 1

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

left 将 (-1,0) 添加到最后一个点。
right 将 (+1,0) 添加到最后一个点。
up 将 (0,+1) 添加到最后一个点。
向下将 (0,-1) 添加到最后一个点。

然后，一系列方向将生成一个 (x,y) 顶点坐标列表，从中可以从 How do I calculate the surface area of a 2d polygon?

中找到生成的（隐含闭合的）多边形的面积

编辑

这是 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

请注意，对于第二个示例中包含相交线的多边形，此方法会失败。

Answer 2

由于您创建的多边形只有与轴对齐的边，因此您可以根据垂直板计算总面积。

假设我们得到了一个顶点列表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-position(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));
}

Returns（如预期）：

3
2

Answer 3

我假设您绘制的形状（轴对齐、多边形图形、闭合、非相交线）应该有一些限制才能计算面积。

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

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

这两个线段之间的表面积等于 them.Summing 所有水平线段的面积等于形状的总表面积。

Answer 4

这可以使用简单多边形的 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;
}

计算给定方向列表的面积

Calculate area given list of directions

algorithm