17
\$\begingroup\$

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

\$\endgroup\$
  • 7
    \$\begingroup\$ It would make more sense for Room to contain a list of Points, and then get the segments by connecting each point together and then loop it back around. Otherwise, with your current setup, it's very east to get incorrect values (e.g. unclosed room, room with wall in middle, etc.). This would be the best option. \$\endgroup\$ – MCMastery Nov 17 '17 at 18:11
  • \$\begingroup\$ Another option is top triangulate the shape and calculate the areas of each triangle. The hard part is the triangulation. Doable, but not always pretty. The shoelace answer is still way better. \$\endgroup\$ – Draco18s Nov 18 '17 at 1:25
  • \$\begingroup\$ @MCMastery That solution won't work, as it requires Rooms to always be complete, and that may not be the case if I have the player build the Rooms using Segments. Also, a closed-room function is easy to define (just loop through the Segments and make sure they create a room). \$\endgroup\$ – user39208 Nov 18 '17 at 10:23
31
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ I always used that to calculate the cross product of two vectors never knew it was called shoelace algorithm \$\endgroup\$ – Sidar Nov 17 '17 at 12:07
  • 3
    \$\begingroup\$ Note that this can be extended to compute the volume of an irregular 3D object made of triangles, and it can be considered a trivial case of the fundamental theorem of calculus. \$\endgroup\$ – Dietrich Epp Nov 17 '17 at 17:02
  • 5
    \$\begingroup\$ The area here is signed. Go through the points in the other direction and the final A is negated. Depending on goal, a A = |A| may be needed. With negative area code can find the area on an irregular donut using the inside and outside list of points (one in the opposite order). \$\endgroup\$ – chux - Reinstate Monica Nov 17 '17 at 18:05
  • 6
    \$\begingroup\$ Because of course either Gauss or Euler has a formula for it. \$\endgroup\$ – corsiKa Nov 17 '17 at 18:24
0
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ -1: You don't want to be using modulo to get it in range, you want to use a uniform distribution or other distribution, doing it the modulo way has all sorts of statistical issues. \$\endgroup\$ – user1997744 Nov 17 '17 at 22:04
  • 12
    \$\begingroup\$ This method might be beneficial when we don't have a simple polygon, but rather some kind of implicit shape whose border is difficult to express, like a fractal or metaball blob. For the case of a polygon as in the question though, it seems like it would be needlessly expensive. \$\endgroup\$ – DMGregory Nov 17 '17 at 23:11
  • \$\begingroup\$ As @DMGregory pointed out, this is not what I was looking for. However, I think it deserves a +1 in case someone else needs it. \$\endgroup\$ – user39208 Nov 18 '17 at 10:31
  • \$\begingroup\$ This is interesting but wouldn't the cost of the inclusion tests get prohibitive? I.e. if you have a shape that is sufficiently complex to warrant this approach, wouldn't the inclusion tests also be really expensive so you wouldn't want to do tons of them? (assuming polygons) \$\endgroup\$ – Mattia Nov 18 '17 at 12:06
  • \$\begingroup\$ Ok modulo is indeed problematic, but it's a simple solution. What we truly get is random P=1/2 bits 0/1 , so what we get is a uniform distribution of numbers eg. for 3 bits from 0 to 7. Doing rand % 5, if a random number takes the value 6 or 7, gets mapped to 1 or 2, effectivelly increasing 1,2 frequency making distribution non-uniform. To avoid that you need something like a state machine which rotates the mapping eg. 6,7 maps to 1,2 then to 3,4 then 5,0 and it goes on. We could also throw away 6,7 whenever they came up. Anyway that's a library implementation problem. \$\endgroup\$ – FranG Nov 18 '17 at 19:51
-1
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Gauss' Shoelace formula is a shorthand for this that halves or thirds the number of calculations. Work it out. \$\endgroup\$ – Pieter Geerkens Nov 18 '17 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy