C226 Suppose you are given an nvertex convex polygon P Descr

C-22.6 Suppose you are given an n-vertex convex polygon, P. Describe an O(n)-time method for computing the area of P.

Solution

For an N - sided polygon, we can find the area by the determinent of the sides:

for e.g: (2,5),(-4,3),(5,1) are the vertices of an polygon., so the area of the polygon can be calculated as :

1/2 *[ [ ( x1 * y2) + ..(x_n * y_n) ]-[(y₁ * x₂) +(y_n*x₁)]

Now, taking the worst case scenario into account

we can have pseudocode as below:

var n=get(\'no of sides\')

var x[n],y[n] -> Array to hold the x and y co - ordinates of sides

var sum =0;

for i=1 to n :

var j=i+1;

if(j>n):

j=1;

end

sum=sum+ ( (x[i] * y[j]) - (y[i]*x[j])

end

print sum/2;

As we are only going to take the worst case complexity we are going to the complexity of the loop which yields as n as that is the maximum number of iterations.