From: Matthew Moss <matthew.moss@...>
Date: 2008-04-23T12:51:46+09:00
Subject: Re: Triangle Area (#160)

Here's my own solution. It's a Monte Carlo solution. It's accuracy
isn't that great; I had to jack up the tolerance and the samples a
good amount, and still couldn't pass the tests regularly.

I know when I've done MC in the past (back in college), my random
number generator was biased and would throw things off. I don't think
there is bias here, but I'm not certain.

Anyway, I've always liked the idea of MC for certain situations.
Certainly, I had an exact triangle area function done in 5 minutes
using the determinant (which helped me create the unit tests). But I
wanted my own submission to be a little different.

And hooray for Barycentric coordinates! Makes the point inside
triangle test real simple.



require "triangle"
require "mathn"


SAMPLE = 50000


def rand_f(lo, hi)
   rand * (hi - lo) + lo
end


class Bounds
   def initialize(l, t, r, b)
      @l, @t, @r, @b = l, t, r, b
   end

   def Bounds.enclosing(*pts)
      horz, vert = pts.map { |v| v[0] }, pts.map{ |v| v[1] }
      Bounds.new(horz.min, vert.min, horz.max, vert.max)
   end

   def area
      (@r - @l) * (@b - @t)
   end

   def rand_pt
      Vector[rand_f(@l, @r), rand_f(@t, @b)]
   end

   def inspect
      "Bounds(#{@l}, #{@t}, #{@r}, #{@b})"
   end
end


class Triangle
   def area
      bnd = Bounds.enclosing(@a, @b, @c)
      return 0 if bnd.area.zero?

      hits = 0
      SAMPLE.times do
         hits += 1 if self.contains(bnd.rand_pt)
      end

      bnd.area * hits / SAMPLE.to_f
   end

   def contains(pt)
      x0, x1, x2, x3 = pt[0], @a[0], @b[0], @c[0]
      y0, y1, y2, y3 = pt[1], @a[1], @b[1], @c[1]

      # Compute barycentric coordinates b1, b2, b3
      b0 =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
      return nil if b0.zero?

      b1 = ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) / b0
      b2 = ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) / b0
      b3 = ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) / b0

      # Point is contained if none of b1, b2, b3 are negative
      b1 >= 0 and b2 >= 0 and b3 >= 0
   end
end