Area of grid polygon given length of edges

Question

Input:

Table T of length N (N <= 10000) containing 32-bit integers. Each integer denotes length and direction of consecutive edge of polygon on a square grid (every vertex has integer coordinates). If integer is positive, it means edge goes up or right. If integer is negative, edge goes down or left. Edges are perpendicular to its neighbors. Edges do not intersect nor overlap with each other. Vertices do not overlap with each other.

Examplary input T:

2, -3, -1, 1, -1, 2

Represents two polygons (it doesn't matter which one we will choose):

enter image description here

Arrows denote first edge corresponding to the first 2 in T.

Output:

Integer denoting surface area of given polygon. For exemplary input, the output should be 5.

Desired time complexity: O(N)
Desired memory complexity (not counting input): O(1)

Can you present such algorithm and rationale behind it?

Talita Talita · Accepted Answer · 2015-01-18T14:00:27

Algorithm:

int area(int[] T) {
    int area = 0;
    int x = 0;
    for (int i = 0; i < T.length; i += 2) {
        x += t[i];
        area += x * t[i + 1];
    }
    return Math.abs(area);
}

Description:

Our polygon is closed in a big rectangle. Based on this we are counting areas of small rectangles which are building our shape - rectangles which are inside polygon as well as rectangles which are outside (with opposite sign).

It doesn't matter from which vertex in polygon we are starting. In the beginning we need one based line from which we will count vertical (it can be horizontal as well, it doesn't matter) translation of vertices. We are getting the first number - it will tell us, how much from the based line our first vertex is moved. The second number is translation according to second coordinate. By multiplying this pair we are getting the first rectangle in our sum.

Second rectangle is described by third and fourth point:

the third number added to the first number is a vertical translation of the vertex
the fourth number is a horizontal translation of the vertex. Multiplying this points is giving us the second rectangle.

We are continuing to do this for the rest of numbers in table. We are adding areas of rectangles. The result is an absolute value of the sum.

Area of grid polygon given length of edges

1 Answers