3

Is there any algo that can help splitting irregular shape into regular shapes, and eventually calculate the area of the main object by summing the areas of those regular objects?

Improve this question
3
  • It's been a while since I've looked into this... If your shape only has straight edges, it should be possible to break it down into triangles and calculate the area. If it has curved edges... I'm pretty sure there's a solution but I forget what it is (though you could approximate the curves with many small straight edges if you can accept some loss of accuracy) :(
    – FrustratedWithFormsDesigner
    Commented Jul 14, 2011 at 13:35
  • What happens if your user presses Cntl+? How does size of a digital image mean anything? I would simply way to count the Pixels. If you are using vectors.. then you did that because you don't care about size. (I'm also assuming 2d Pics)
    – Morons
    Commented Jul 14, 2011 at 13:59
  • 1
    Impossible to answer without a more precise definition of "irregular shape". How are these shapes represented?
    – kevin cline
    Commented Jul 14, 2011 at 14:01

4 Answers 4

Reset to default
4

Delaunay triangulation is probably what you're looking for.

As FrustratedWithFormsDesigner this is precise when dealing with a polygon; for arbitrary curved shapes you end up with an approximation.

The Delaunay triangulation algorithm gives you "fat" triangles, which will give you less errors in your calculations.

Improve this answer
2
  • 1
    +1, but note that you don't need a delauney triangulation just to calculate the area of a polygon!
    – nikie
    Commented Jul 14, 2011 at 13:48
  • No, but Delaunay maximises the minimum angle of the triangles!
    – Frank Shearar
    Commented Jul 14, 2011 at 14:27
3

Can you approximate your shape with a polygon? Calculating a polygon's area is quite simple:

A = 1/2 * sum(x[i]*y[i+1] - x[i+1]*y[i])

(wiki)

Improve this answer
2

Is there any algo that can help splitting irregular shape into regular shapes, and eventually calculate the area of the main object by summing the areas of those regular objects?

This is, to put long story short, the basis of numerical integration with the goal to determine the area beneath a curve - a problem very common in naval architecture. Two most used methods are Trapezoid rule and Simpson's rule .

For example, trapezoid rule is based on linear interpolation in which you approximate the area beneath the curve with trapezoids, and calculate the area of each one. By summing all trapezoid areas you get the area beneath a curve (or an irregular shape).

The logic and implementation of the algorithm is very simple, and Wikipedia even has some examples.

There are many more complicated variations to the theme (for non-equidistant points distribution and so on...) but you should try first if this one will suit your need.

Improve this answer
1

I don't know one off the top of my head (Google would probably reveal it)

However this is how I'd approach it:

  • Create a grid of known size.
  • Place this grid over your irregular shape
  • Count all elements inside the shape
  • For each element that contains part of the outline of the shape. Perform all the above steps on that element with a finer resolution (or count this element as 0.5)
Improve this answer
1
  • Sort of like a two-dimensinal Riemann approximation of the integral?
    – sourcenouveau
    Commented Jul 14, 2011 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.