File: test_kdtree.py

package info (click to toggle)
gamera 1:3.4.2+git20160808.1725654-1
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 22,312 kB
  • ctags: 24,991
  • sloc: xml: 122,324; ansic: 52,869; cpp: 50,664; python: 35,034; makefile: 118; sh: 101
file content (84 lines) | stat: -rw-r--r-- 2,823 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import py.test

from gamera.core import *
init_gamera()

#
# Tests for nearest neighbor finding with kd-trees
#

from gamera.kdtree import *

#
# input parameter check
#
def test_wrongparams():
    def _kdnode_input(coord):
        node = KdNode(coord)
    def _kdtree_input(nodes):
        tree = KdTree(nodes)
    # all point coordinates must be numeric
    py.test.raises(Exception, _kdnode_input, [1,2,"a"])
    py.test.raises(Exception, _kdnode_input, [])
    # all nodes must be KdNode's and of same dimension
    py.test.raises(Exception, _kdtree_input, [KdNode([1,2]),KdNode([2,3,4])])
    py.test.raises(Exception, _kdtree_input, [KdNode([1,2]),[2,3]])
    py.test.raises(Exception, _kdtree_input, None)
    py.test.raises(Exception, _kdtree_input, [])


#
# k nearest neighbor searches
#
def test_nearest_neighbors():
    points = [(1,1), (2,1), (1,3), (2,4), (3,4),
              (7,2), (8,3), (8,4), (7,5), (7,5)]
    nodes = [KdNode(p) for p in points]
    tree = KdTree(nodes)
    assert [7,2] == tree.k_nearest_neighbors([5.5,3],1)[0].point
    assert [[2,4], [3,4]] == \
        [n.point for n in tree.k_nearest_neighbors([2,4],2)]
    assert [[7,5],[7,5],[8,4]] == \
        [n.point for n in tree.k_nearest_neighbors([7,5],3)]
    assert [[8,4],[8,3],[7,5]] == \
        [n.point for n in tree.k_nearest_neighbors([8,4],3)]
    assert [[3,4],[2,4],[1,3],[2,1],[1,1],[7,5]] == \
        [n.point for n in tree.k_nearest_neighbors([3,4],6)]

#
# tests with different distance measures
#
def test_distance_metrics():
    points = [(1,4), (2,4), (1,5), (3,6), (8,9),
              (3.2,4.2), (4,4), (5,5), (3.8,6), (8,3)]
    nodes = [KdNode(p) for p in points]
    tree = KdTree(nodes)
    tree.set_distance(0)
    assert [[5,5], [3.8,6], [3.2,4.2]] == \
        [n.point for n in tree.k_nearest_neighbors([5,6],3)]
    tree.set_distance(1)
    assert [[5,5], [3.8,6], [3,6]] == \
        [n.point for n in tree.k_nearest_neighbors([5,6],3)]
    tree.set_distance(2,[1.0,0.5])
    assert [[5,5], [3.8,6], [4,4]] == \
        [n.point for n in tree.k_nearest_neighbors([5,6],3)]
    tree.set_distance(0,[0.5,1.0])
    assert [[3.8,6], [3,6], [5,5]] == \
        [n.point for n in tree.k_nearest_neighbors([5,6],3)]

#
# tests with search predicate
#
def test_search_predicate():
    class predicate(object):
        def __init__(self, point):
            self.point = point
        def __call__(self, node):
            return (self.point[1] > node.point[1])
    points = [(1,4), (2,4), (1,5), (3,6), (8,9),
              (3.2,4.2), (4,4), (5,5), (3.8,6), (8,3)]
    nodes = [KdNode(p) for p in points]
    tree = KdTree(nodes)
    assert [[5,5], [4,4]] == \
        [n.point for n in tree.k_nearest_neighbors([5,6],2,predicate([5,6]))]
    assert 0 == len(tree.k_nearest_neighbors([5,6],2,predicate([1,2])))