[Haskell-cafe] Rotating calipers
Hello all , I am trying to understand rotating calipers [ http://en.wikipedia.org/wiki/Rotating_calipers ] but i am not sure if understood this algorithm correctly . I tried to use the almost same algorithm given on wiki but with four calipers to solve the problem [ http://cgm.cs.mcgill.ca/~orm/rotcal.html ]. My approach is find xminP, xmaxP, yminP ymaxP and their corresponding calipers will be ( 0 * i - j ) , ( o * i + j ) , ( i + 0 * j ) and ( -i + 0 * j ). I implemented the algorithm in Haskell but its not working . I am not sure if i have followed the wiki algorithm correctly and could some one please tell me what is wrong with implementation. It would be great if some one can explain this algorithm in pseudo code which explains the rotating caliper and their implementation details . In case of indentation , see here [ http://hpaste.org/49907 ] . Thank you Mukesh Tiwari import Data.List import Data.Array import Data.Maybe import Data.Function import Text.Printf import qualified Data.ByteString.Char8 as BS data Point a = P a a deriving ( Show , Ord , Eq ) data Vector a = V a a deriving ( Show , Ord , Eq ) data Turn = S | L | R deriving ( Show , Eq , Ord , Enum ) --start of convex hull compPoint :: ( Num a , Ord a ) = Point a - Point a - Ordering compPoint ( P x1 y1 ) ( P x2 y2 ) | compare x1 x2 == EQ = compare y1 y2 | otherwise = compare x1 x2 findMinx :: ( Num a , Ord a ) = [ Point a ] - [ Point a ] findMinx xs = sortBy ( \x y - compPoint x y ) xs compAngle ::(Num a , Ord a ) = Point a - Point a - Point a - Ordering compAngle ( P x1 y1 ) ( P x2 y2 ) ( P x0 y0 ) = compare ( ( y1 - y0 ) * ( x2 - x0 ) ) ( ( y2 - y0) * ( x1 - x0 ) ) sortByangle :: ( Num a , Ord a ) = [ Point a ] - [ Point a ] sortByangle (z:xs) = z : sortBy ( \x y - compAngle x y z ) xs findTurn :: ( Num a , Ord a , Eq a ) = Point a - Point a - Point a - Turn findTurn ( P x0 y0 ) ( P x1 y1 ) ( P x2 y2 ) | ( y1 - y0 ) * ( x2- x0 ) ( y2 - y0 ) * ( x1 - x0 ) = L | ( y1 - y0 ) * ( x2- x0 ) == ( y2 - y0 ) * ( x1 - x0 ) = S | otherwise = R findHull :: ( Num a , Ord a ) = [ Point a ] - [ Point a ] - [ Point a ] findHull [x] ( z : ys ) = findHull [ z , x ] ys --incase of second point on line from x to z findHull xs [] = xs findHull ( y : x : xs ) ( z : ys ) | findTurn x y z == R = findHull ( x : xs ) ( z:ys ) | findTurn x y z == S = findHull ( x : xs ) ( z:ys ) | otherwise = findHull ( z : y : x : xs ) ys convexHull ::( Num a , Ord a ) = [ Point a ] - [ Point a ] convexHull xs = reverse . findHull [ y , x ] $ ys where ( x : y : ys ) = sortByangle . findMinx $ xs --end of convex hull --start of rotating caliper part http://en.wikipedia.org/wiki/Rotating_calipers --dot product for getting angle angVectors :: ( Num a , Ord a , Floating a ) = Vector a - Vector a - a angVectors ( V ax ay ) ( V bx by ) = theta where dot = ax * bx + ay * by a = sqrt $ ax ^ 2 + ay ^ 2 b = sqrt $ bx ^ 2 + by ^ 2 theta = acos $ dot / a / b --rotate the vector x y by angle t rotVector :: ( Num a , Ord a , Floating a ) = Vector a - a - Vector a rotVector ( V x y ) t = V ( x * cos t - y * sin t ) ( x * sin t + y * cos t ) --dist between two parallel vectors distVec :: ( Num a , Ord a , Floating a ) = Vector a - Vector a - a distVec ( V x1 y1 ) ( V x2 y2 ) = sqrt $ ( x1 - x2 ) ^ 2 + ( y1 - y2 ) ^ 2 --rotating caliipers rotCal :: ( Num a , Ord a , Floating a ) = Array Int ( Point a ) - a - [ Int ] - [ Vector a ] - a - Int - a rotCal arr ang [ pa , pb , qa , qb] [ cpa , cpb , cqa , cqb ] area n | 2 * ang pi = area | otherwise = rotCal arr ang' [ pa' , pb' , qa' , qb' ] [ cpa' , cpb' , cqa' , cqb' ] area' n where P x1 y1 = arr ! pa P x2 y2 = arr ! ( mod ( pa + 1 ) n ) P x3 y3 = arr ! pb P x4 y4 = arr ! ( mod ( pb + 1 ) n ) P x5 y5 = arr ! qa P x6 y6 = arr ! ( mod ( qa + 1 ) n ) P x7 y7 = arr ! qb P x8 y8 = arr ! ( mod ( qb + 1 ) n ) t1 = angVectors cpa ( V ( x2 - x1 ) ( y2 - y1 ) ) t2 = angVectors cpb ( V ( x4 - x3 ) ( y4 - y3 ) ) t3 = angVectors cqa ( V ( x6 - x5 ) ( y6 - y5 ) ) t4 = angVectors cqb ( V ( x8 - x7 ) ( y8 - y7 ) ) t = minimum [ t1 , t2 , t3 , t4 ] cpa' = rotVector cpa t cpb' = rotVector cpb t cqa' = rotVector cqa t cqb' = rotVector cqb t ang' = ang + t ( pa' , pb' , qa' , qb' ) = fN [ t1 , t2 , t3 , t4 ] t where fN [ t1 , t2 , t3 , t4 ] t | t == t1 = ( mod ( pa + 1 ) n , pb , qa , qb ) | t == t2 = ( pa , mod ( pb + 1 ) n , qa , qb ) | t == t3 = ( pa , pb , mod ( qa + 1 ) n , qb ) | otherwise = ( pa , pb , qa , mod ( qb + 1 ) n ) width = distVec cpa' cpb' length = distVec cqa' cqb' area' = min area $ length * width solve :: ( Num a , Ord a , Floating a ) = [ Point a ] - a solve [] = 0 solve [
Re: [Haskell-cafe] Rotating calipers
Am 06.08.2011 13:12, schrieb mukesh tiwari: Hello all , Hi I am trying to understand rotating calipers [ http://en.wikipedia.org/wiki/Rotating_calipers ] but i am not sure if understood this algorithm correctly . I tried to use the almost same algorithm given on wiki but with four calipers to solve the problem [ http://cgm.cs.mcgill.ca/~orm/rotcal.html ]. There are several algorithms mentioned on that page. Do you need the diameter, width, or something else? My approach is find xminP, xmaxP, yminP ymaxP and their corresponding calipers will be ( 0 * i - j ) , ( o * i + j ) , ( i + 0 * j ) and ( -i + 0 * j ). I implemented the algorithm in Haskell but its not working . I am not sure if i have followed the wiki algorithm correctly and could some one please tell me what is wrong with implementation. It would be great if some one can explain this algorithm in pseudo code which explains the rotating caliper and their implementation details . In case of indentation , see here [ http://hpaste.org/49907 ] . Thank you Mukesh Tiwari I tried your code on one of my libraries. The convex hull function seems to works correctly (I could send you a screenshot). I hope this narrows the search down. Do you have some example data and what wrong result you get? In one of my libraries (http://hackage.haskell.org/packages/archive/collada-types/0.3/doc/html/Graphics-Formats-Collada-GenerateObjects.html) there is a function: streamAnimation :: [(Float,Float,Float)] - [SceneNode] - [Animation] that can visualize a stream of points by an animation. I use this sometimes for debugging. -Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rotating calipers
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 . ghcifinal [ 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 ghcifinal [ 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.9982 ghcifinal [ 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 On Aug 6, 10:32 pm, Tillmann Vogt tillmann.v...@rwth-aachen.de wrote: Am 06.08.2011 13:12, schrieb mukesh tiwari: Hello all , Hi I am trying to understand rotating calipers [ http://en.wikipedia.org/wiki/Rotating_calipers] but i am not sure if understood this algorithm correctly . I tried to use the almost same algorithm given on wiki but with four calipers to solve the problem [http://cgm.cs.mcgill.ca/~orm/rotcal.html]. There are several algorithms mentioned on that page. Do you need the diameter, width, or something else? My approach is find xminP, xmaxP, yminP ymaxP and their corresponding calipers will be ( 0 * i - j ) , ( o * i + j ) , ( i + 0 * j ) and ( -i + 0 * j ). I implemented the algorithm in Haskell but its not working . I am not sure if i have followed the wiki algorithm correctly and could some one please tell me what is wrong with implementation. It would be great if some one can explain this algorithm in pseudo code which explains the rotating caliper and their implementation details . In case of indentation , see here [http://hpaste.org/49907] . Thank you Mukesh Tiwari I tried your code on one of my libraries. The convex hull function seems to works correctly (I could send you a screenshot). I hope this narrows the search down. Do you have some example data and what wrong result you get? In one of my libraries (http://hackage.haskell.org/packages/archive/collada-types/0.3/doc/htm...) there is a function: streamAnimation :: [(Float,Float,Float)] - [SceneNode] - [Animation] that can visualize a stream of points by an animation. I use this sometimes for debugging. -Tillmann ___ Haskell-Cafe mailing list Haskell-C...@haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Prelude read 1234 :: String - *** Exception: Prelude.read: no parse
Prelude read 1234 :: Int1234Prelude read 1234 :: String*** Exception: Prelude.read: no parse Why? Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prelude read 1234 :: String - *** Exception: Prelude.read: no parse
read expects strings to be quoted: Prelude read \1234\ :: String 1234 On Sat, Aug 6, 2011 at 19:57, michael rice nowg...@yahoo.com wrote: Prelude read 1234 :: Int 1234 Prelude read 1234 :: String *** Exception: Prelude.read: no parse Why? Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Scott Lawrence ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] trouble using the aeson package
I recently installed the aeson package using cabal-install without any trouble: ❲~❳ uname -rspi; cabal -V; ghc -V; ghc-pkg list | grep aeson\|double-conversion Linux 2.6.38-10-generic x86_64 x86_64 cabal-install version 0.10.2 using version 1.10.1.0 of the Cabal library The Glorious Glasgow Haskell Compilation System, version 7.0.3 aeson-0.3.2.9 double-conversion-0.2.0.1 However when I try to use it I receive this error message: λ let f = Data.Aeson.String Loading package double-conversion-0.2.0.1 ... can't load .so/.DLL for: stdc++ (libstdc++.so: cannot open shared object file: No such file or directory) This is the version I have installed: ❲~❳ aptitude search stdc++ | grep ^i i libstdc++6 - The GNU Standard C++ Library v3 i A libstdc++6-4.4-dev - The GNU Standard C++ Library v3 (developme i libstdc++6-4.5-dev - The GNU Standard C++ Library v3 (developme ❲~❳ aptitude show libstdc++6-4.4-dev | head -n 4 Package: libstdc++6-4.4-dev State: installed Automatically installed: yes Version: 4.4.5-15ubuntu1 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] trouble using the aeson package
On Sat, Aug 6, 2011 at 8:55 PM, anonymous qubi...@gmail.com wrote: However when I try to use it I receive this error message: Funny, I just spent some time documenting this earlier today. There are two bugs in GHCi that cause the problem you're seeing. They're documented here, with a workaround: https://github.com/mailrank/blaze-textual#readme ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Analyzing slow performance of a Haskell program
Hello Cafe, I was trying to solve ITA Software's Word Nubmers puzzle ( http://www.itasoftware.com/careers/puzzle_archive.html) using a brute force approach. Here's a my version of a quick recap of the problem: A wordNumber is defined as wordNumber 1 = one wordNumber 2 = onetwo wordNumber 3 = onethree wordNumber 15 = onetwothreefourfivesixseveneightnineteneleventwelvethirteenfourteenfifteen ... Problem: Find the 51-billion-th letter of (wordNumber Infinity); assume that letter is found at 'wordNumber x', also find 'sum [1..x]' From an imperative perspective, a naive algorithm would be to have 2 counters, keep counting the length of each wordNumber and break to return the result. The imperative brute-force approach is implemented in C# here: http://ideone.com/JjCb3. It takes about 1.5 minutes to find the answer on my computer. Then I implemented a brute-force Haskell version: http://ideone.com/ngfFq. It cannot finish the calculation in 5 minutes on my machine. (Irony: it's has more lines than the C# version) Here is the `-p` profile of the Haskell program: http://hpaste.org/49934 The Question: Are there obvious mistakes I am making? (Note: I am fully aware that brute-forcing it is not the correct solution to this problem. I am mainly interested in making the Haskell version perform comparatively to the C# version. Right now it is at least 5x slower so obviously I am missing something obvious) (Note 2: It does not seem to be space leaking. The program runs with constant memory (about 2MB) on my computer) (Note 3: I am compiling with `ghc -O2 WordNumber.hs) Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
