How to compute the area of an irregular shape?

Question

I have a room object defined by a collection of looping line segments that I need to calculate the area for. The classes can be described as follows (in pseudo-code):

class Point {
    float x; 
    float y;
    ...
    float distanceFrom(Point p);
}

class Segment {
    Point start;
    Point end;
    ...
    float length();
}

class Room {
    List<Segment> walls;
    ...
    float area();
}

The walls of a room can never intersect anywhere but at the endpoints of the segments and any "sub-loops" created will also be separated into a new room. The solution does not need to be perfectly accurate (10% margin of error is acceptable) and is also not computed very often (<1/s).

Answer 1

You can use Gauss' shoelace formula:

You need to take the x coordinate of every point, multiply them by the next point's y coordinate, then subtract the current point's y coordinate multiplied by the next point's x coordinate from the result and add them to the total area. After you did this for every point, halve the total area to get the actual area of the polygon. If the current point's the last one, then the next is the first.

A = 0

for (i = 0; i < points.length; i++) do

    A += points[i].x * points[(i + 1) % points.length].y - points[i].y * points[(i + 1) % points.length].x

end

A /= 2

Answer 2

We could also use a Monte Carlo method.

Draw a rectangle around the arbitrary shape. Take a uniformly distributted PRNG source eg. mersenne twister, then bound the output by rectangle's X,Y lengths using modulo function. Count the no. of random-points that land inside your shape. Divide by the total amount of points generated. Multiply that quotient by the rectangle's area. With each iteration you will converge to the true area. The algorithm is ridiculously parrallelizable and can used to calculate arbitrary dimensional shape 'volumes', as long as you can determine if an R^N coordinate falls within shape's R^N boundary.

.

Here someone is using this method find circle area then uses that to calculate pi https://www.youtube.com/watch?v=VJTFfIqO4TU

Answer 3

Another approach: Don't.

Instead:

while (Segments.Count > 3)
{
    Segment A = Segments[Segments.Count - 2];
    Segment B = Segments[Segments.Count - 1];
    Segment C = new Segment(B.End, A.Start);
    Triangle T = new Triangle(A, B, C);
    Segments[Segments.Count - 2] = C;
    Segments.RemoveAt(Segments.Count - 1);
    if (B is inside the new shape Segments)
        Area -= T.Area;
    else
        Area += T.Area;
}
Area += new Triangle(Segments[0], Segments[1], Segments[2]).Area;

Basically, lop off a triangle. The area of a triangle is simple and in doing so we reduced the segment count of the remainder by one. Repeat until what's left is a triangle.