0

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?

Agnel Kurian
  • 57,975
  • 43
  • 146
  • 217
  • Presumably you have all you need [to calculate it exactly](http://en.wikipedia.org/wiki/Circular_segment), unless the shapes are drawn freehand? In any case, just drawing and counting pixels might be more accurate than approximating with line segments. – Roger Rowland Dec 21 '13 at 09:29
  • I notice someone has voted to close. Close this first: http://stackoverflow.com/questions/451426/how-do-i-calculate-the-surface-area-of-a-2d-polygon – Agnel Kurian Dec 21 '13 at 09:29
  • @RogerRowland, that might work but what if a vertex falls wihin the arc? – Agnel Kurian Dec 21 '13 at 09:56
  • 1
    Not sure what you mean, do you mean the arc is interrupted by another shape? Maybe you can post a worst-case image so we can see. But unless you need very high precision, draw, flood-fill and count pixels would be most general (given that the curves are always closed). – Roger Rowland Dec 21 '13 at 10:02
  • Do the arcs have the same diameter? Are the arcs always half a circle? – Bathsheba Dec 21 '13 at 13:01
  • This question appears to be off-topic because it is about math, not programming. – nalply Dec 21 '13 at 15:23
  • @Bathsheba No. No. Orientation, position, number of arcs is variable. So is diameter, angle and everything else. – Agnel Kurian Dec 21 '13 at 18:06
  • @nalply, in that case, so is this question: http://stackoverflow.com/questions/451426/how-do-i-calculate-the-surface-area-of-a-2d-polygon – Agnel Kurian Dec 21 '13 at 18:07
  • Ladies, must I include some code to convince you that this is about programming? That would be trivial. – Agnel Kurian Dec 21 '13 at 18:09
  • Madame @AgnelKurian, perhaps you will have more luck on http://math.stackexchange.com/. But I am afraid you need to demonstrate first what you have tried. Show a formula you tried and why it didn't work or why you got stuck. Answerers are glad to help you but dislike to do the whole grunt work for you. – nalply Dec 21 '13 at 20:50
  • @Bathsheba, the arc diameter and sweep/angle are variable. – Agnel Kurian Dec 26 '13 at 10:05
  • Madame @nalply, the same points you have raised apply to this question as well: http://stackoverflow.com/questions/451426 Have you attempted to close that question? Or do you bear some grudge particularly against closed figures bounded by arcs? – Agnel Kurian Dec 26 '13 at 10:09
  • No, this is an old question. What's acceptable for StackOverflow has changed over the years. Take it easy. :-) – nalply Dec 26 '13 at 13:38
  • @nalply OK. Taking it easy now. But I will cast my vote to reopen. :) – Agnel Kurian Dec 26 '13 at 15:06
  • I think I have demonstrated "a minimal understanding of the problem being solved" as evident from "I know how this can be done by approximating the arcs with a series of line segments". The same can count under "attempted solutions". As for "why they didn't work" and "expected results", it is also clearly stated that I am looking for a more exact result. – Agnel Kurian Dec 27 '13 at 02:28
  • @HighPerformanceMark, image has been corrected. – Agnel Kurian Dec 27 '13 at 04:45
  • Are all of the arcs circular? Or could they be elliptical or any arbitrary curve? – mbeckish Dec 27 '13 at 04:58
  • Also, how are these drawings represented as data? Is it a bitmap? A union of circles and rectangles? Something else? – mbeckish Dec 27 '13 at 05:01
  • Are you storing a collection of splines that the user drew? Along with something to indicate whether the splines are adding to or subtracting from the drawing? For example, in your application can a user create the image from [this post](http://stackoverflow.com/q/10867437/21727)? – mbeckish Dec 27 '13 at 05:17
  • @mbeckish, only circular arcs. The data an array of the structure `(x,y,is_arc)`. `x` and `y` hold the co-ordinates. `is_arc` is true when a point forms an arc with its immediate neighbours. B-splines are not supported. – Agnel Kurian Dec 27 '13 at 10:32
  • Do you also store the radius of each arc, or is that a constant? – mbeckish Dec 27 '13 at 15:55
  • @mbeckish radius is variable. I use 3 points to define the arc. Radius is implied from the 3 points. – Agnel Kurian Dec 28 '13 at 01:39
  • Monte Carlo integration could be one option. – user18490 Dec 29 '13 at 12:05

4 Answers4

5

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

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
1

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.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
0

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

Razack
  • 1,826
  • 2
  • 16
  • 37
0

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.
mbeckish
  • 10,485
  • 5
  • 30
  • 55