计算给定方向列表的区域

Question

假设你有一份方向清单:

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

如果您按照说明操作,您将始终返回起始位置.计算刚刚创建的形状的面积.

由上述方向形成的形状如下所示:

 ___
|   |___
|_______|

显然,从图片中可以看出该区域为3.

我试图使用2d矩阵来追踪方向,但不确定如何从中获取该区域......

例如,在我的2d数组中:

O  O
O  O  O
O  O  O

这可能不是处理这个问题的好方法,任何想法？

Answer 1

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

假设我们有一个顶点列表V。我假设我们已经包装在这个列表中，所以我们可以查询V.next(v)每个 vertex v in 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