Algorithms-leetcode-codewars-hackerRank/quadtree.rb at master · pateldd1/Algorithms-leetcode-codewars-hackerRank · 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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
class Quadtree
    attr_accessor :root
    def initialize(root)
        @root = root
    end

    def insertion(point)
        current = @root
        @root = insert(current, point)
    end

    def insert(current, point, last=nil)
        if !current
            return Quadrant.create_new_quadrant(last, point)
        end

        case current.which_quadrant(point)
            when 'ne'
                current.neq = insert(current.neq, point, current)
            when 'se'
                current.seq = insert(current.seq, point, current)
            when 'sw'
                current.swq = insert(current.swq, point, current)
            when 'nw'
                current.nwq = insert(current.nwq, point, current)
        end
        return current
    end

    def find(point)
        current = @root
        search(current, point)
    end

    def search(current, point)
        loop do
            case current.which_quadrant(point)
                when 'ne'
                    current = current.neq
                when 'se'
                    current = current.seq
                when 'sw'
                    current = current.swq
                when 'nw'
                    current = current.nwq
            end
            return false if !current
            return true if current.contained_point == point
        end
    end
end

class Quadrant
    attr_accessor :center, :nw, :ne, :sw, :se, :neq, :seq, :nwq, :swq, :contained_point
    def initialize(center, ne, se, sw, nw, contained_point)
        @center = center
        @nw = nw
        @ne = ne
        @sw = sw
        @se = se
        @neq = nil
        @seq = nil
        @nwq = nil
        @swq = nil
        @contained_point = contained_point
    end

    def self.create_new_quadrant(quadrant, newpoint)
        newpoint_x, newpoint_y = newpoint
        center_x, center_y = quadrant.center
        if newpoint_x <= center_x && newpoint_y <= center_y
            southwest = quadrant.sw
            northeast = quadrant.center
            southwest_x, southwest_y = southwest
            northeast_x, northeast_y = northeast
            southeast = [northeast_x, northeast_y]
            northwest = [southwest_x, northeast_y]
            return Quadrant.new(quadrant.getcenter(southwest, northeast), northeast, southeast, southwest, northwest, newpoint)
        elsif newpoint_x <= center_x && newpoint_y >= center_y
            northwest = quadrant.nw
            southeast = quadrant.center
            northwest_x, northwest_y = northwest
            southeast_x, southeast_y = southeast
            southwest = [northwest_x, southeast_y]
            northeast = [southeast_x, northwest_y]
            return Quadrant.new(quadrant.getcenter(northwest, southeast), northeast, southeast, southwest, northwest, newpoint)
        elsif newpoint_x >= center_x && newpoint_y >= center_y
            northeast = quadrant.ne
            southwest = quadrant.center
            northeast_x, northeast_y = northeast
            southwest_x, southwest_y = southwest
            northwest = [southwest_x, northeast_y]
            southeast = [northeast_x, southwest_y]
            return Quadrant.new(quadrant.getcenter(northeast, southwest), northeast, southeast, southwest, northwest, newpoint)
        elsif newpoint_x >= center_x && newpoint_y <= center_y
            southeast = quadrant.se
            northwest = quadrant.center
            northwest_x, northwest_y = northwest
            southeast_x, southeast_y = southeast
            northeast = [southeast_x, northwest_y]
            southwest = [northwest_x, southeast_y]
            return Quadrant.new(quadrant.getcenter(southeast, northwest), northeast, southeast, southwest, northwest, newpoint)
        end
    end

    def getcenter(point1, point2)
        x1, y1 = point1
        x2, y2 = point2
        return [(x1+x2)/2.to_f, (y1+y2)/2.to_f]
    end

    def which_quadrant(point)
        point_x, point_y = point
        center_x, center_y = @center
        if point_x <= center_x && point_y <= center_y
            return 'sw'
        elsif point_x <= center_x && point_y >= center_y
            return 'nw'
        elsif point_x >= center_x && point_y >= center_y
            return 'ne'
        elsif point_x >= center_x && point_y <= center_y
            return 'se'
        end
    end
end

root = Quadrant.new([50,10], [100, 20], [100, 0], [0, 20], [0,0], [50, 10])
quadtree = Quadtree.new(root)

quadtree.insertion([1,5])
quadtree.insertion([1,6])
quadtree.insertion([1,7])
quadtree.insertion([1,8])
quadtree.insertion([60,30])
quadtree.insertion([60,40])
quadtree.insertion([60,60])
quadtree.insertion([80,2])
quadtree.insertion([80,30])
p quadtree.root
p quadtree.find([1,6])
p quadtree.find([60,40])
p quadtree.find([60,2])
p quadtree.find([80,2])
p quadtree.find([1,6])