From: Matthew Moss <matthew.moss@...>
Date: 2008-04-24T23:46:13+09:00
Subject: [SUMMARY] 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 Mahurin'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 Koppel 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 Finnie 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 Shelly, 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 Moss <matthew.moss@gmail.com>