Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
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 Jul 14 '11 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 Jul 14 '11 at 13:59
1  
Impossible to answer without a more precise definition of "irregular shape". How are these shapes represented? –  kevin cline Jul 14 '11 at 14:01
add comment

4 Answers

up vote 4 down vote accepted

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.

share|improve this answer
1  
+1, but note that you don't need a delauney triangulation just to calculate the area of a polygon! –  nikie Jul 14 '11 at 13:48
    
No, but Delaunay maximises the minimum angle of the triangles! –  Frank Shearar Jul 14 '11 at 14:27
add comment

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)

share|improve this answer
add comment

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.

share|improve this answer
add comment

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)
share|improve this answer
    
Sort of like a two-dimensinal Riemann approximation of the integral? –  M. Dudley Jul 14 '11 at 15:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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