algorithmgraphicsgeometrycurve

Algorithm to Calculate the Area of a Closed Curve with Holes

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:

enter image description here

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?

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

    1. 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".