Triangle Area (#160)

Apologies for the latest… Some busy stuff this week in “real life.”
In light of that, I’ve kept this quiz simple: you only need implement
one function. I do provide brief descriptions of a few possible
techniques, but don’t feel you need to do them all! Just pick one that
sounds interesting to you…

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q. 2:

  1. Please do not post any solutions or spoiler discussion for this
    quiz until 48 hours have passed from the time on this message.

  2. Support Ruby Q. 2 by submitting ideas as often as you can! (A
    permanent, new website is in the works for Ruby Q. 2. Until then,
    please visit the temporary website at

    http://matthew.moss.googlepages.com/home.

  3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby T. follow the discussion. Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Quiz #160
Triangle Area

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.

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

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

  1. Something else!

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

On Apr 19, 11:39 am, Matthew M. [email protected] wrote:

Apologies for the latest… Some busy stuff this week in “real life.”

That should read, “Apologies for the lateness…”. :slight_smile:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Matthew M. wrote:
|
| On Apr 19, 11:39 am, Matthew M. [email protected] wrote:
|> Apologies for the latest… Some busy stuff this week in “real life.”
|
|
| That should read, “Apologies for the lateness…”. :slight_smile:

See, switching off the splellchecker for gains in speed isn’t helpful at
all. :stuck_out_tongue:


Phillip G.
Twitter: twitter.com/cynicalryan

Treat end of file conditions in a uniform manner.
~ - The Elements of Programming Style (Kernighan & Plaugher)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.8 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkgKPJcACgkQbtAgaoJTgL/+RgCfX6XVZVpNCEoObZwAwbTXdoGs
7+AAn0DCqhlgPUmjy2guazeqbo2Wu8dx
=8Yr2
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Matthew M. wrote:
| Splellchecker?

Oh, right, that should be splelingchequer. My bad. :wink:


Phillip G.
Twitter: twitter.com/cynicalryan

Make sure comments and code agree.
~ - The Elements of Programming Style (Kernighan & Plaugher)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.8 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkgKP2MACgkQbtAgaoJTgL+uMACcDPdEEFqzj2b3mHEW8ggiQBX3
a30An38hx+Tp4NcPVrEthmOGpQ+r8KIC
=tO+A
-----END PGP SIGNATURE-----

Phillip G. [email protected] wrote:

| That should read, “Apologies for the lateness…”. :slight_smile:

See, switching off the splellchecker for gains in speed isn’t helpful at
all. :stuck_out_tongue:

Splellchecker?

:wink:

On Sat, Apr 19, 2008 at 8:40 PM, Phillip G.
[email protected] wrote:

|
| That should read, “Apologies for the lateness…”. :slight_smile:

See, switching off the splellchecker for gains in speed isn’t helpful at
all. :stuck_out_tongue:

Rilli Ai culd not agri lesz wis u at al.
Ridikolos

Roperd

iEYEARECAAYFAkgKPJcACgkQbtAgaoJTgL/+RgCfX6XVZVpNCEoObZwAwbTXdoGs
7+AAn0DCqhlgPUmjy2guazeqbo2Wu8dx
=8Yr2
-----END PGP SIGNATURE-----


http://ruby-smalltalk.blogspot.com/


Whereof one cannot speak, thereof one must be silent.
Ludwig Wittgenstein

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Robert D. wrote:
| On Sat, Apr 19, 2008 at 8:40 PM, Phillip G.
| [email protected] wrote:
|
|> See, switching off the splellchecker for gains in speed isn’t helpful at
|> all. :stuck_out_tongue:
|
| Rilli Ai culd not agri lesz wis u at al.
| Ridikolos
|
| Roperd

Oh, that made my day. Gave me a laugh I desperately needed. :smiley:


Phillip G.
Twitter: twitter.com/cynicalryan

[Yuppies] are fickle and greedy, prone to panic like penguins, and naked
~ of roots or serious political convictions.
~ – Hunter S. Thompson
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.8 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkgKUS4ACgkQbtAgaoJTgL/xLgCgnke5qqCdpy6ZF11Un9hsV8Kt
xV8AoJXAyD6wsQrj0re2z2q18YnCU4b/
=lPSI
-----END PGP SIGNATURE-----

Some unit testing for y’all:

require “test/unit”

TOL = 0.0001

class Triangle
def Triangle.
Triangle.new(*args)
end
end

class TestTriArea < Test::Unit::TestCase

def test_3pt_degen
a = RANDOM_PT.call
t = Triangle[a, a, a]
assert_equal(0, t.area)
end

def test_2pt_degen
a, b = RANDOM_PT.call, RANDOM_PT.call
t = Triangle[a, b, b]
assert_equal(0, t.area)
end

def test_easy
t = Triangle[Vector[0, 0], Vector[3, 0], Vector[0, 1]]
assert_in_delta(1.5, t.area, TOL)
end

def test_mostly_easy
t = Triangle[Vector[-11, 0], Vector[5, 0], Vector[0, 3]]
assert_in_delta(24, t.area, TOL)
end

SAMPLES = {
Triangle[Vector[-42, 4], Vector[-26, -34], Vector[ 2, 8]] =>
868.0,
Triangle[Vector[ 45, -44], Vector[ 1, 43], Vector[ 42, 48]] =>
1893.5,
Triangle[Vector[-24, 29], Vector[ 42, -1], Vector[ 10, 43]] =>
972.0,
Triangle[Vector[ 48, -19], Vector[-19, 37], Vector[-15, 36]] =>
78.5,
Triangle[Vector[-10, -40], Vector[-35, -19], Vector[ 1, 33]] =>
1028.0,
Triangle[Vector[ 28, 23], Vector[-46, 31], Vector[-39, 5]] =>
934.0,
Triangle[Vector[-32, 17], Vector[-50, -8], Vector[-39, 27]] =>
177.5,
Triangle[Vector[ 40, -19], Vector[ 39, -34], Vector[-37, -15]] =>
579.5,
Triangle[Vector[ 47, -34], Vector[ 26, -37], Vector[ 50, -7]] =>
279.0,
Triangle[Vector[-49, 46], Vector[ 29, 46], Vector[ 5, -34]] =>
3120.0
}

def test_samples
SAMPLES.each do |t, a|
assert_in_delta(a, t.area, TOL)
end
end
end

Hi,

My solution to this week’s Ruby Q. is attached.

A quick overview of my solution:

  1. Find the lengths of all the sides of the triangle using the
    Pythagorean theorem.
  2. Find the perimeter and the semiperimeter (half the perimeter) from
    those values.
  3. Use Heron’s Formula to calculate area. Heron’s formula is a =
    sqrt(s(s-a)(s-b)(s-c)) where s is the semiperimeter and a, b, and c
    are the side lengths.

Dan

  1. Determinant Method

If you decide to implement this technique and are using random
triangles with integer coordinates (as my provided Triangle.random
method uses), make sure to require “mathn”, or your determinants are
likely to be wrong.

I couldn’t figure out why my unit tests were failing until I read the
Matrix documentation, which indicates “this may be fixed in the
future.”

I’m doing a little cheating here, and may have severely wimped out.
Not only did I fail to meet the actual requirements of the quiz, but
also ignored the unit test (well, not completely). I was going to
–and may still-- use dot products some other day to show off my
meager knowledge of math and allow myself to enter valhalla. I’m not
here for prosperity, so, anyways, my one-liner to satisfy the quiz was
atrocious. To replace it, I’ll use this for now…

require ‘mathn’
puts 0.5 * Matrix[[28.0, 23.0, 1.0], [-46.0, 31.0, 1.0], [-39.0, 5.0,
1.0]].det.abs

=> 934.0

That’s probably the easiest way.

Doing a redneck modify to the test data structure…

require ‘mathn’
arr = [
[[-42, 4, 1], [-26, -34, 1], [ 2, 8, 1]],
[[ 45, -44, 1], [ 1, 43, 1], [ 42, 48, 1]],
[[-24, 29, 1], [ 42, -1, 1], [ 10, 43, 1]],
[[ 48, -19, 1], [-19, 37, 1], [-15, 36, 1]],
[[-10, -40, 1], [-35, -19, 1], [ 1, 33, 1]],
[[ 28, 23, 1], [-46, 31, 1], [-39, 5, 1]],
[[-32, 17, 1], [-50, -8, 1], [-39, 27, 1]],
[[ 40, -19, 1], [ 39, -34, 1], [-37, -15, 1]],
[[ 47, -34, 1], [ 26, -37, 1], [ 50, -7, 1]],
[[-49, 46, 1], [ 29, 46, 1], [ 5, -34, 1]],
]
arr.each do |a|
puts 0.5 * Matrix[*a].det.abs
end

868.0 1893.5 972.0 78.5 1028.0 934.0 177.5 579.5 279.0 3120.0

It’s not “application worthy”, but I wasn’t shooting for that. I’m
also not sure if you might have to use Floats in the array above or
not, because it passes the test given Integers.

I wrote some code that attempts to build a random array, but I’m
embarrassed to show it; and also the Vector into Matrix code I used
looks ugly.

I wrote that snippet of code before going to wikipedia. I had this
feeling originally that I should attempt something like Heron’s idea,
but didn’t have the time.

I suppose another way to approach it could be to use a matrix
transformation to get your ‘base’ (turn the triangle, or the
coordinate system; however you prefer to see it) and use a simple
1/2(b*h).

Non-euclidean would be an interesting extra credit.

Todd

On Mon, Apr 21, 2008 at 6:06 PM, Daniel F. [email protected]
wrote:

=> [47, 78, 88, 39, 61]
?> Array.new(3) { rand(100) - 50 }
[[-6, -19, -25], [21, 5, -47], [-38, -7, -13]],
[[47, -20, -34], [39, -21, -35], [17, 17, -6]],
[[0, 24, -2], [-38, 14, -26], [4, 2, -9]],
[[47, 7, -34], [28, -24, 18], [-9, -5, -6]],
[[-34, -15, 1], [-26, 17, -2], [-8, 46, 30]],
[[-20, 23, -28], [44, -12, -18], [8, -40, -47]],
[[31, -6, 32], [5, 27, 31], [-14, -14, -41]]]

Dan

Hey Dan,

Thanks for pointing that out! I keep forgetting that Array.new takes
a block, which is even more embarrassing, because I have in fact
suggested that solution to someone else in the past.

Todd

Hi Todd,

I like your math-y solution – it probably runs circles around the
non-mathy ones.

For generating a random array of numbers, I like to use this technique:

Array.new(5) { rand(100) }
=> [47, 78, 88, 39, 61]

Array.new(5) { rand(100) }
=> [48, 38, 33, 94, 98]

So you could do this to generate an array of arrays like the one in your
post:

require ‘pp’
=> false

def rand_ar
Array.new(10) do
?> Array.new(3) do
?> Array.new(3) { rand(100) - 50 }

  end
end

end
=> nil

pp rand_ar
[[[47, 14, 20], [1, -18, -15], [7, -46, -44]],
[[-5, -44, -32], [-40, 9, 1], [16, 16, 10]],
[[-15, -13, 2], [16, -16, 37], [-1, 17, -4]],
[[-13, 5, -31], [47, -30, -27], [13, -2, -16]],
[[23, -50, 12], [3, 34, 6], [16, 24, -34]],
[[-6, -19, -25], [21, 5, -47], [-38, -7, -13]],
[[13, 48, 23], [12, -33, -7], [48, -14, -47]],
[[-12, -28, -31], [3, 37, -16], [-50, 29, -44]],
[[13, -21, 29], [36, 30, 45], [8, 9, 36]],
[[-16, 8, -47], [43, -49, 42], [45, 4, 5]]]
=> nil

pp rand_ar
[[[45, 5, 34], [19, -14, 11], [-17, 32, -43]],
[[-2, 31, 40], [-16, 40, -19], [-10, -18, 37]],
[[21, 38, -13], [47, 23, -10], [0, -2, -12]],
[[7, 49, 8], [-23, -38, -25], [-45, -31, -3]],
[[47, -20, -34], [39, -21, -35], [17, 17, -6]],
[[0, 24, -2], [-38, 14, -26], [4, 2, -9]],
[[47, 7, -34], [28, -24, 18], [-9, -5, -6]],
[[-34, -15, 1], [-26, 17, -2], [-8, 46, 30]],
[[-20, 23, -28], [44, -12, -18], [8, -40, -47]],
[[31, -6, 32], [5, 27, 31], [-14, -14, -41]]]

Dan

On 4/21/08, Todd B. [email protected] wrote:

I suppose another way to approach it could be to use a matrix
transformation to get your ‘base’ (turn the triangle, or the
coordinate system; however you prefer to see it) and use a simple
1/2(b*h).

1/2(b*h) wa the first thing I thought of when I read the quiz title.
Here’s my implementation:

class Triangle
def area
pts = [@a, @b, @c]
#filter out degenerate triangles
return 0 if pts.uniq!

#move one point to the origin
offset = pts[0]*-1.0
pts.map!{|v|v+=offset}

#find the angle of one leg
angle=Math::atan(pts[1][1]/pts[1][0])

#rotate that leg so it lies along X axis
rotmat = Matrix.rows( [[Math::cos(angle),Math::sin(angle)],
                       [-Math::sin(angle),Math::cos(angle)]])
pts.map!{|v|rotmat*v}

#use basic geometry
base = pts[1][0].abs
height = pts[2][1].abs
area=base*height/ 2.0

end
end

-Adam

On Mon, Apr 21, 2008 at 6:50 PM, Adam S. [email protected]
wrote:

class Triangle
angle=Math::atan(pts[1][1]/pts[1][0])
end
end

-Adam

That is awesome! It’s almost exactly what I had in mind. The cool
thing about it is you can expand it, if need be, to three dimensions
with only a couple changes.

Only a couple of small things. You want to return 0 if Vector objects
happen to be uniq!? Or, are you using my nested array model? For
example…

[Vector[1, 1], Vector[1, 1], Vector[1, 1]].uniq!
=> nil

That’s using 1.8.6 on Windoze.

Also, “bad” triangles can have legs that are almost collinear, which,
depending on your use case, you might have to check for. I didn’t.
Sigh :confused: But, it turns out I didn’t have to. It correctly returns an
area of 0.0.

For performance reasons – which I don’t really often care about when
I use Ruby – you could set up Math::sin and Math::cos before the
creation of the Matrix, since that Matrix creation is calling both
twice.

Good stuff!

Todd

On Apr 20, 2:39 am, Matthew M. [email protected] wrote:

class Triangle
    end

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

A method that hasn’t been mentioned so far is “Heron’s formula”:

Area = sqrt( s(s-a)(s-b)(s-c) )

where a, b, c   are the lengths of the sides
  and 2s = a + b + c

If someone wants to implement that, I’d be keen to see what the code
looks like.

Cheers,
Gavin

On Mon, Apr 21, 2008 at 8:15 PM, Gavin S. [email protected]
wrote:

Cheers,
Gavin

Daniel has a cool solution. It’s in his first email in this thread as
an attachment.

Todd

http://en.wikipedia.org/wiki/Polygon

Here is a solution using the above that could be used for a simple
polygon
with an arbitrary # of points:

   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

On Apr 19, 7:39 pm, Matthew M. [email protected] wrote:

time this
week, try this.

I haven’t read the link until now. Guess, my solution is close to
that proposed there. :slight_smile:

It’s based on the fact that the length of cross-product of two vectors
is equal to the area of a parallelogram built on that vectors. The
area of the triangle is half of that value then.

|a.x-b.x a.y-b.y|

|a.x-c.x a.y-c.y|

def area
((@a[0] - @b[0])(@a[1] - @c[1])
- (@a[0] - @c[0])
(@a[1] - @b[1])).abs / 2.0
end

BTW, Matthew’s tests are really nicely crafted–they helped to catch
several problems in that single line of mine. :wink:

On 4/21/08, Todd B. [email protected] wrote:

On Mon, Apr 21, 2008 at 6:50 PM, Adam S. [email protected] wrote:

class Triangle
def area
pts = [@a, @b, @c]
#filter out degenerate triangles
return 0 if pts.uniq!

Only a couple of small things. You want to return 0 if Vector objects
happen to be uniq!? Or, are you using my nested array model? For
example…

[Vector[1, 1], Vector[1, 1], Vector[1, 1]].uniq!
=> nil

Ah. This illustrates the ( joys | perils ) of test-driven development.
The solution was failing Matt’s test cases for degenerate triangles,
The uniq! test was my attempt of to filter out triangles with duplicate
points (they were causing NANs). I assumed Vectors with identical
contents would compare equal. But this method only passed the tests
because the case was creating Triangles with multiple instances of
the same Vector. I guess it should be:

return 0 if pts.map{|v|v.to_a}.uniq!

Also, “bad” triangles can have legs that are almost collinear, which,
depending on your use case, you might have to check for. I didn’t.

This solution handles that without a special case: if the legs are
colinear, both will fall on the X axis after rotation, making the height
0.
If they are only ‘almost colinear’, then the math should handle it.

Here’s another test case for those types of triangle:

def test_linear
#colinear
t = Triangle[Vector[0,0],Vector[1,1],Vector[-1,-1]]
assert_in_delta(0, t.area, TOL)
t = Triangle[Vector[2.5,1.1],Vector[5,2.2],Vector[7.5,3.3]]
assert_in_delta(0, t.area, TOL)
#nearly colinear
t = Triangle[Vector[2.5,1.1],Vector[5,2.2],Vector[7.5,3.301]]
assert_in_delta(0.00125, t.area, TOL)
[1e-3,1e-6,1e-9].each{|n|
t = Triangle[Vector[0,0],Vector[n,1],Vector[0,2]]
assert_in_delta(n, t.area, n*TOL)
}
end

-Adam

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