algorithm - 计算给定方向列表的面积

Question

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

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

如果您遵循指示，您将始终回到起始位置。计算您刚刚创建的形状的面积。

由上面的方向形成的形状看起来像这样:

 ___
|   |___
|_______|

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

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

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

O  O
O  O  O
O  O  O

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

Answer 1

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

假设我们得到了一个顶点列表 V。我假设我们在此列表中进行了环绕，因此我们可以查询 V.next(v) 以获取 V 中的每个顶点 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