Tree-Based_Index-Structure/KDNode.java at master · ayushd96/Tree-Based_Index-Structure · GitHub

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
85
86
87
88
89
90
91
92
93
94
95
96
/**
 * Class for a node in the KDTree
 */
class KDNode
{
    int axis;
    double[] point;
    int id;
    boolean checked;
    boolean orientation;

    KDNode Parent;
    KDNode Left;
    KDNode Right;

    public KDNode(double[] pt, int axis0){
        point = new double[]{pt[0], pt[1],pt[2]};
        axis = axis0;
        Left = Right = Parent = null;
        checked = false;
        id = 0;
    }

    public KDNode FindParent(double[] pt){
        KDNode parent = null;
        KDNode next = this;
        int split;

        while (next != null){
            split = next.axis;
            parent = next;
            if (pt[split] > next.point[split])
                next = next.Right;
            else
                next = next.Left;
        }

        return parent;
    }


    public KDNode Insert(double[] pt){
        //point = new double[3];
        KDNode parent = FindParent(pt);
        if (equal(pt, parent.point) == true)
            return null;

        KDNode newNode = new KDNode(pt,parent.axis + 1 < 3 ? parent.axis + 1 : 0);

        newNode.Parent = parent;

        if (pt[parent.axis] > parent.point[parent.axis]){
            parent.Right = newNode;
            newNode.orientation = true; //
        }
        else{
            parent.Left = newNode;
            newNode.orientation = false; //
        }

        return newNode;
    }

    /**
     * Check if two points have the same value
     * @param pt1
     * @param pt2
     * @return
     */
    boolean equal(double[] pt1, double[] pt2){
        for (int i = 0; i < 3; i++){
            if (pt1[i] != pt2[i])
                return false;
        }
        return true;
    }

    /**
     * check if node is in given range
     * @param from
     * @param to
     * @return
     */
    boolean inRange(double[] from, double[] to){
        boolean inRange = false;

        if((this.point[0] >= from[0] && this.point[0]<= to[0])
            && (this.point[1] >= from[1] && this.point[1]<= to[1])
                && (this.point[2] >= from[2] && this.point[2]<= to[2])){
                    inRange = true;
                }

        return inRange;
    }

}