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?

Maybe just use the [surveyor's formula](http://en.wikipedia.org/wiki/Shoelace_formula) as suggested by others in the answers. In your particular case there might be a more simple and efficient way, but .. surveyor's formula is quite good here too. — wsdookadr, Jan 20 '15 at 05:48

score 3 · Accepted Answer · edited Nov 27 '19 at 17:16

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

this is needlessly complex. O(n) is possible using shoelace formula and is arguably easier to implement — Sopel, Nov 27 '19 at 17:20
@Sopel I never heard of the shoelace formula algorithm before but that looks a lot simpler indeed! Please post that as an answer :) — Vincent van der Weele, Nov 28 '19 at 05:12

score 2 · Answer 2 · edited May 23 '17 at 11:43

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.

score 1 · Answer 3 · answered Nov 28 '19 at 10:46

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

score 0 · Answer 4 · answered Jan 20 '15 at 13:00

I assume there should be some restrictions on the shapes you are drawing (Axis aligned, polygonal graph, closed, non intersecting lines) to be able to calculate the area.

Represent the the shape using segments, each segments consists of two points, each has two coordinates: x and y.

Taking these assumptions into consideration, we can say that any horizontal segment has one parallel segment that has the same x dimensions for its two points but different y dimensions.

The surface area between these two segments equal the hight difference between them.Summing the area for all the horizontal segments gives you the total surface area of the shape.

What if the horizontal segment has multiple parallel segments (same x, different y)? — Vic, Jan 20 '15 at 13:15
Then the segments are in pairs, so you calculate the area between every pair. — Muhammad Soliman, Jan 21 '15 at 08:49

Calculate area given list of directions

4 Answers4