KdTree 0.2 → 0.2.1

raw patch · 3 files changed

+35/−5 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/Trees/KdTree.hs +20/−1
• KdTree.cabal +3/−3
• KdTreeTest.hs +12/−1

@@ -55,7 +55,8 @@ fromList :: Point p => [p] -> KdTree p fromList points = fromListWithDepth points 0 --- Select axis based on depth so that axis cycles through all valid values+-- |fromListWithDepth selects an axis based on depth so that the axis cycles+-- through all valid values. fromListWithDepth :: Point p => [p] -> Int -> KdTree p fromListWithDepth [] _ = KdEmpty fromListWithDepth points depth = node@@ -98,6 +99,24 @@                                     then candidates1 ++ maybeToList (nearestNeighbor tree2 probe)                                     else candidates1 in                 Just . L.minimumBy (compareDistance probe) $ candidates2++-- |nearNeighbors tree p returns all neighbors within distance r from p in tree.+nearNeighbors :: Point p => KdTree p -> Double -> p -> [p]+nearNeighbors KdEmpty radius probe                      = []+nearNeighbors (KdNode KdEmpty p KdEmpty _) radius probe = if dist2 p probe <= radius^2 then [p] else []+nearNeighbors (KdNode l p r axis) radius probe          =+    if xProbe <= xp+      then let nearest = maybePivot ++ nearNeighbors l radius probe+           in if xProbe + abs radius > xp+                then nearNeighbors r radius probe ++ nearest+                else nearest+      else let nearest = maybePivot ++ nearNeighbors r radius probe+           in if xProbe - abs radius < xp+                then nearNeighbors l radius probe ++ nearest+                else nearest+  where xProbe     = coord axis probe+        xp         = coord axis p+        maybePivot = if dist2 probe p <= radius^2 then [p] else []  -- |isValid tells whether the K-D tree property holds for a given tree. -- Specifically, it tests that all points in the left subtree lie to the left

@@ -3,11 +3,11 @@ -- The package version. See the Haskell package versioning policy -- (http://www.haskell.org/haskellwiki/Package_versioning_policy) for -- standards guiding when and how versions should be incremented.-Version:             0.2+Version:             0.2.1 Synopsis:            KdTree, for efficient search in K-dimensional point clouds. Description:         -    This is a simple library for k-d trees in Haskell. It enables efficient-    searching through collections of points in O(log N) time on average,+    This is a simple library for k-d trees in Haskell. It enables+    searching through collections of points in O(log N) average time,     using the nearestNeighbor function.  Homepage:            https://github.com/ijt/kdtree

@@ -20,12 +20,23 @@  prop_nearestNeighbor :: [Kd.Point3d] -> Kd.Point3d -> Bool prop_nearestNeighbor points probe =-    Kd.nearestNeighbor tree probe == bruteNearestNeighbor points probe+    Kd.nearestNeighbor tree probe == bruteNearestNeighbor points probe      where tree = Kd.fromList points           bruteNearestNeighbor :: [Kd.Point3d] -> Kd.Point3d -> Maybe Kd.Point3d           bruteNearestNeighbor [] _ = Nothing           bruteNearestNeighbor points probe =               Just . head . L.sortBy (Kd.compareDistance probe) $ points++prop_nearNeighbors :: [Kd.Point3d] -> Kd.Point3d -> Double -> Bool+prop_nearNeighbors points probe radius =+    (L.sort (Kd.nearNeighbors   tree   radius probe) ==+     L.sort (bruteNearNeighbors points radius probe))+    where tree = Kd.fromList points+          bruteNearNeighbors :: [Kd.Point3d] -> Double -> Kd.Point3d -> [Kd.Point3d]+          bruteNearNeighbors []     radius _     = []+          bruteNearNeighbors points radius probe =+              filter (withinDistance probe radius) points+          withinDistance probe radius point = Kd.dist2 probe point <= radius^2  prop_pointsAreClosestToThemselves :: [Kd.Point3d] -> Bool prop_pointsAreClosestToThemselves points =