[Haskell-cafe] Rotating calipers

[Tillmann Vogt]

Am 06.08.2011 22:23, schrieb mukesh tiwari:
>> There are several algorithms mentioned on that page. Do you need the
>> diameter, width, or something else?
> Oh , I did not realize that .Actually first i implemented diameter
> algorithm [ http://hpaste.org/49925 ] and tested it on couple of test
> cases . Its working fine then i tried  to implement " The minimum area
> enclosing rectangle for a convex polygon"  using four calipers but i
> don't know whats wrong code.
>> Do you have some example data and what wrong result you  get?
> For any test input [ which i tried ] it outputs 4 . If its implemented
> correctly then it will accepted here with slight modification [
> http://www.spoj.pl/problems/WLOO0707 ] since it asks for square area.
> Couple of test cases which i tried .
>
> ghci>final [ P 1 1 , P 2 2 , P 0 100 , P 0 1 ]
> Loading package array-0.3.0.0 ... linking ... done.
> Loading package bytestring-0.9.1.5 ... linking ... done.
> 4.0
>
> ghci>final [ P 0 0 ,P 5 1 , P 9 2 , P 12 3 , P 14 4 , P 15 5 , P 16
> 7 , P 17 10 , P 18 14 , P 19 19 ]
> 3.9999999999999982
>
> ghci>final [ P 2 ( -3 ) , P (-1 ) 2 , P 0 5 , P (-5) (-1) , P (-4)
> ( 2 ) , P 4 0 , P 1 3 , P 4 3 , P (-3) (-4) , P 0 (-2)]
> 4.0
>
> Thank you
> Mukesh Tiwari

I found the error!

In
 >    width = distVec cpa' cpb'
 >    length = distVec cqa' cqb'
the length of the direction vectors is used to compute the area and the 
area is then always 4.

Replace it with
 >    width = distVec (V x1 y1) (V x3 y3)
 >    length = distVec (V x5 y5) (V x7 y7)

and it seems to work:

ghci> final [ P 1 1 , P 2 2 , P 0 100 , P 0 1 ]
           221.3707297724792