Calculate area given list of directions

Question

Let's say you're given a list of directions:

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

If you follow the directions, you will always return to the starting location. Calculate the area of the shape that you just created.

The shape formed by the directions above would look something like:

 ___
|   |___
|_______|

Clearly, from the picture, you can see that the area is 3.

I tried to use a 2d matrix to trace the directions, but unsure how to get the area from that...

For example, in my 2d array:

O  O
O  O  O
O  O  O

This is probably not a good way of handling this, any ideas?

Answer 1

This can be implemented in place using Shoelace formula for simple polygons.

For each segment (a, b) we have to calculate (b.x - a.x)*(a.y + b.y)/2. The sum over all segments is the signed area of a polygon.

What's more, here we're dealing only with axis aligned segments of length 1. Vertical segments can be ignored because b.x - a.x = 0. Horizontal segments have a.y + b.y / 2 = a.y = b.y and b.x - a.x = +-1. So in the end we only have to keep track of y and the area added is always +-y

Here is a sample C++ code:

#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;
}

Answer 2

Since the polygon you create has axis-aligned edges only, you can calculate the total area from vertical slabs.

Let's say we are given a list of vertices V. I assume we have wrapping in this list, so we can query V.next(v) for every vertex v in V. For the last one, the result is the first.

First, try to find the leftmost and rightmost point, and the vertex where the leftmost point is reached (in linear time).

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)

Now we create a simple data structure: for every vertical slab we keep a max heap (a sorted list is fine as well, but we only need to repetitively fetch the maximum element in the end).

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

We start tracing the shape from vertex leftVertex now (the leftmost vertex we found in the first step). We now choose that this vertex has x/y-position (0, 0), just because it is convenient.

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

You can build this structure in O(n log n) time, because adding to a heap costs logarithmic time.

Finally, we need to compute the area from the heap. For a well-formed input, we need to get two contiguous y-values from the heap and subtract them.

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

return area

Again, this takes O(n log n) time.

---

I ported the algorithm to a java implementation (see Ideone). Two sample runs:

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 (as expected):

3
2

Answer 3

Assuming some starting point (say, (0,0)) and the y direction is positive upwards:

• left adds (-1,0) to the last point.
• right adds (+1,0) to the last point.
• up adds (0,+1) to the last point.
• down adds (0,-1) to the last point.

A sequence of directions would then produce a list of (x,y) vertex co-ordinates from which the area of the resulting (implied closed) polygon can be found from How do I calculate the surface area of a 2d polygon?

EDIT

Here's an implementation and test in Python. The first two functions are from the answer linked above:

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])))

Output:

3.0
0.0

Note that this approach fails for polygons that contain intersecting lines as in the second example.