On 22 Aug 2000, Friedrich Dominicus wrote:
> Dear Haskell Fans, I'm afraid that I'm a bit dumb but I'm somewhat
> stuck.
>
> Can someone give me a hand on this problem
>
> I wrote this code to solve SOE, exc 5.1.
>
> import Shape
>
> triangleArea :: [Vertex] -> Float
> triangleArea (v1:v2:v3:_) = let a = distBetween v1 v2
> b = distBetween v2 v3
> c = distBetween v3 v1
> s = 0.5 * (a + b + c)
> in sqrt (s * (s-a) *(s-b) * (s-c))
> triangleArea _ = 0
By the way:
A classical way of calculating area of a triangle is to compute
cross product r = p x q, where p = v2 - v1 and q = v3 - v1, and
then take half of its norm; 1/2 * sqrt (r1^2 + r2^2 + r3^2).
Here, function 'sqrt' is called once only (providing that you
compute vector 'r' algebraically, not via norms); that is:
r1 = p2*q3 - p3*q2
r2 = p3*q1 - p1*q3
r3 = p1*q2 - p2*q1
In your example you call 'sqrt' four times (I presume here
that 'distanceBetween' is defined in terms of 'sqrt').
Although I appreciate the reason why this algorithm has been
exposed in SOE, it is - in fact - quite inefficient due to
all those 'sqrt' computations.
Furthemore, if you wish to compute area of a polygon, you
can indeed split it into a list of triangles, sum
all the vector products, and finally take one only 'sqrt' of
the result and divide it by two. It works for any type
of polygons, even those that have local convexes, for
example 'stars', etc. Internal 'holes' in your polygons
can be also automatically accounted for.
Take a look at www.numeric-quest.com/haskell/solid/Solid.html
(section 6.2 and 8.1) and
www.numeric-quest.com/solid/Solid_test.html
(section 5) for some examples. This is a bit more that you need,
but it also show how to compute not only areas but also area
integrals (for this I use Sierpinski's fractals). Truthfully,
the later algorithm require some rethinking and optimization,
which I have not done as yet.
Jan
>
>
> o_array :: Shape -> Float
> o_array (Polygon (v1:vs)) =
> let ph = phelp vs
> in
> foldr (+) 0.0 (map triangleArea ph)
> where phelp :: [Vertex] -> [[Vertex]]
> phelp (v2:v3:vs) = (v1:v2:v3:[]):phelp (v3:vs)
> phelp _ = []
>
>
> what I want is to replace the recursive phelp function with a function
> using higher order functions.
>
> My base idea is splitting up List of Vertices into a list of exactly
> three vertices calculating that area and adding them all.
>
> BTW, I do not like the above solution anyway. It's too bulky. So if one has
> another idea on how to tackle it, I would be very thankful to some
> hint.
>
> Best regards
> Friedrich
>
> --
> for e-mail reply remove all after .com
>
