Algorithm to Calculate the Area of a Closed Curve with Holes

Question

Our application allows users to trace closed curves composed of straight lines and arcs. These closed curves can have holes within them which are also made up of straight lines and arcs. Something like this:

The number, position, orientation, diameter and sweep/angle of arc segments and straight segments is variable.

How do I go about calculating the area within the closed curve excluding the area of the holes? I know how this can be done by approximating the arcs with a series of line segments. But is there a better, more accurate algorithm to do this?

Answer 1

1. The general approach is straightforward: the area of your region is calculated as the area of the external contour minus the areas of the holes. This takes care of the "hole" issue, so we can forget about holes.

   The problem now is calculating the area of "generalized polygon": a pseudo-polygon whose edges are either straight segments or arcs.

2. The ordinary Shoelace formula would give you the area of any ordinary polygon. But since we are dealing with a "generalized polygon", the formula is not immediately applicable because of arc edges.

   However, the basic idea behind the Shoelace formula can be adapted to this situation as well.

   Shoelace formula basically calculates a sum of signed areas of triangles OAB, built from point O(0,0) and points A and B of each edge AB of the polygon in question. Signedness of the area in this case means that the area shall be positive when OAB is a counterclockwise triangle and negative otherwise. See here for an illustration of how it works for polygon area calculation.

   In order to adapt this formula to your situation you have to find a way to calculate signed area of a "generalized triangle": a pseudo-triangle OAB in which OA and OB are straight segments, while AB can be an arc. That's a significantly simpler problem that is perfectly solvable.

That's basically all you need to do. The whole problem is reduced to a set of elementary problems: calculation of signed area of aforementioned "generalized triangle".

Answer 2

You have a complex shape that you can't give the area of. What you need to do is break it down into shapes that you can give the area of. I would suggest rectangles, triangles, and triangles with one edge substituted by an arc. Working vertically from the top, define a horizontal line each time you hit a vertex or the point of an arc where the slope changes between positive and negative. Calculate the area of all the shapes you generate between successive horizontal lines.

Answer 3

I think you have several options:

1. Integrate each segment (except straight vertical segments) to find the area underneath each segment. The integrals should be easy, because you only have straight lines and circle arcs. The reason this method might be too tricky or even impossible is that integrals give you the area of the extrusion of an arc to the x-axis. However, your final shape is not the union of all of the vertical extrusions of each arc. It's probably more like the convex hull of the outermost arcs minus the convex hulls of interior arcs (which make the holes in your shape).
2. You could change your data model. Instead of arcs and straight lines, treat them as sectors and rectangles. Finding the area of each object is easy - the hard part is then taking overlap into account to get the total area.
3. Since your app already knows how to draw the final figure and know what parts are solid and what are holes, use that to implement some kind of pixel counting / flood fill algorithm to calculate the area.

Answer 4

Looks like you got to find area of polygon, circle, ellipse and arcs. Approximate arc with polygons. Except Arc rest is straight forward. If you are using Graphics path in GDI+ one option is to take polygon points form graphics path. Else look for polygon approximation of curves. http://keisan.casio.com/ Possibly use GraphicsPath.PathPoints http://msdn.microsoft.com/en-us/library/system.drawing.drawing2d.graphicspath.pathpoints(v=vs.110).aspx