160 Triangle Area

Description

Start with the following code for a Triangle class:

require 'matrix'

RANDOM_PT = lambda { Vector[rand(101)-50, rand(101)-50] }

class Triangle
	def initialize(a, b, c)
		@a, @b, @c = a, b, c
	end

	def Triangle.random(foo = RANDOM_PT)
		Triangle.new(foo.call, foo.call, foo.call)
	end

	def [](i)
		[@a, @b, @c][i]
	end

	def area
		# Fill in this stub.
	end

	def inspect
		"Triangle[#{@a}, #{@b}, #{@c}]"
	end
	alias to_s inspect
end

Your task this week is to write the code for the area method.

There are a few techniques that come to mind for determining (or closely estimating) the area of a triangle. You do not need to attempt all of these; just pick a technique that sounds fun and do implement it.

  1. Determinant Method

    It is possible to calculate the area of a triangle very simply using just the points as part of a matrix, and calculating the determinant of that matrix. See http://mathforum.org/library/drmath/view/55063.html for an explanation of the technique. This is quick and easy, so if you don’t have much time this week, try this.

  2. Monte Carlo Method

    The Monte Carlo method first requires that you determine a bounding area (typically a box) that surrounds the test area (i.e. the triangle). Then you choose thousands of random points within the box, determining for each point whether it falls inside or outside the triangle.

    Knowing the area of the box (an easier calculation) and the percentage of random points that fell inside the triangle, you can multiply those two values together to get the triangle’s area.

  3. Scan-Line Method

    Imagine covering the triangle with horizontal bars of a certain height, such that each bar is only wide enough to hide the triangle underneath. Knowing the width and height of each bar (i.e. rectangle) lets you calculate the area of each, and summed together is an approximation of the triangle’s area.

    (This is sometimes called a scan-line method, as you are examining horizontal slices of the subject, very much like a television scan line draws a number of horizontal slices of the picture.)

    Each time the height of the bars are halved (and twice as many are employed), your estimate of the triangle’s area will improve. Those familiar with calculus will recognize this as integration, as the height of each horizontal slice approaches zero.

  4. Something else!

    If none of these methods interest you, but you have another method to estimate or determine exactly the triangle’s area, please do!

Summary

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


Wednesday, February 04, 2009