Triangle Area (#160)

Calculating the area of a triangle is a long solved problem with
well-known
solutions. I mentioned a few possible techniques in the quiz; almost
everyone
provided short, simple, exact solutions, which I’ll go over in a moment.

For those interested in seeing how Monte Carlo solutions work, take a
look at
the code which I provided. The quiz description describes the basic
method
for Monte Carlo simulations, and the code isn’t that difficult to
understand.
Keep in mind, Monte Carlo is for estimating, and you won’t get an exact
answer.
However, it’s a useful technique to know when an exact answer is
difficult or
impossible to compute exactly.

Back to the exact solutions…

First, the determinant method, as mentioned in the quiz description. I
didn’t
know if there was a proper name for this, but Alex reminded me that it
is
similar to taking half of the magnitude of the cross-product of two
vectors
that form the triangle. (A bit of a mouthful, I know…). In fact, they
are
exactly the same thing: that’s what the determinant of the matrix
calculates.

However, I want to look at Eric M.'s solution here, as it is simple
yet
applicable to more than just triangles.

def area
   p0 = @c
   area2 = 0
   [@a, @b, @c].each { |p|
      area2 += p0[0]*p[1] - p[0]*p0[1]
      p0 = p
   }
   (area2 / 2.0).abs
end

To show that this is the determinant method on the triangle, I’m going
to
refactor this a bit, to remove the loop and swap the order of the
division
and abs call.

def area
   area2 = 0
   area2 += @c[0]*@a[1] - @a[0]*@c[1]
   area2 += @a[0]*@b[1] - @b[0]*@a[1]
   area2 += @b[0]*@c[1] - @c[0]*@b[1]
   area2.abs / 2.0
end

If you compare this to Alex’s solution (after expanding the
multiplication
and combining terms), you’ll see they’re exactly the same.

Eric’s solution, however, is more generic in that you can replace the
vertex
array [@a, @b, @c] to be a larger array of points that describe a
polygon.
Very handy, indeed.

Next, we have Heron’s (or Hero’s) Formula, credited to Heron of
Alexandria
circa 60 A.D., though it may be even older. This is new technique to me,
and
I was delighted by its simplicity.

James K. had a mostly simple implementation:

class Vector
  def distance(oth)
    Math.sqrt(to_a.zip(oth.to_a).inject(0){|s,(a,b)|s+(a-b)**2})
  end
end

class Triangle
  def area
    ab = @a.distance(@b)
    bc = @b.distance(@c)
    ac = @a.distance(@c)
    s = (ab+bc+ac)/2
    Math.sqrt(s*(s-ab)*(s-bc)*(s-ac))
  end
end

As you can see, Heron’s Formula is very simple and clear (though I
recommend
researching it online[1] if you want to know its history and
derivation).

What I would recommend is an alternative implementation of distance on
the
Vector class. James did work that’s already been done, and could be more
simply implemented as

class Vector
   def distance(oth)
     (self - oth).r
   end
end

Daniel F. also provided a Heron’s Formula solution, though did write
a
bit of redundant code, duplicating existing functionality of the Vector
class
in his Point class. Also, the Triangle.random method appears to have
been
untested. However, I do want to point out a couple of interesting bits
from
Daniel’s solution.

blk ||= lambda { ... }

A nice, simple way to assign a default value to a variable, if currently
unset.

[@a, @b, @c, @a].enum_for(:each_cons, 2)

After requiring the enumerator module, Daniel now has access to
enum_for
which creates Enumerator objects, to be used later. The use of
:each_cons
and the value two will enumerate pairs of objects at a time, rather than
the
typical one-at-a-time when using each.

Finally, a shout out to Adam S., who went old school and remembered
the old “base times height over two” formula that, for many of us, was
the
second area of a shape formula we learned (right after rectangles). Of
course,
since the triangles tested do not always have a base parallel to the X
axis,
he had to do a bit of rotation to get it into place.

Check out Adam’s solution to see how to rotate a triangle using a matrix
just
so you can use simple math for the area. Good show, I say.

[1] http://mathworld.wolfram.com/HeronsFormula.html

Matthew M. [email protected]

On Thu, Apr 24, 2008 at 8:46 AM, Matthew M. [email protected]
wrote:

Alex reminded me that it is similar to taking half of the magnitude
of the cross-product of two vectors that form the triangle. (A bit of
a mouthful, I know…). In fact, they are exactly the same thing:
that’s what the determinant of the matrix calculates.

The norm of the cross product of two vectors corresponds to the area of
the parallelogram spanned by those vectors. Since a parallelogram can
be split into two identical triangles, the area of the triangle whose
sides are described by the vectors corresponds to half the area of the
parallelogram.

(And I probably got the language wrong, I’m a bit rusty)

Next, we have Heron’s (or Hero’s) Formula, credited to Heron of
Alexandria circa 60 A.D., though it may be even older. This is new
technique to me, and I was delighted by its simplicity.

The story behind how Heron arrived at this result is very interesting.
I think there’s a book called “the joy of mathematics” which contains a
very nice account of it.

Thanks for the quiz!

Marcelo

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs