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
