File Coverage

blib/lib/Algorithm/QuadTree/PP.pm
Criterion Covered Total %
statement 73 73 100.0
branch 19 20 95.0
condition 9 9 100.0
subroutine 13 13 100.0
pod n/a
total 114 115 99.1


line stmt bran cond sub pod time code
1             package Algorithm::QuadTree::PP;
2             $Algorithm::QuadTree::PP::VERSION = '0.3';
3 6     6   36 use strict;
  6         7  
  6         142  
4 6     6   23 use warnings;
  6         12  
  6         133  
5 6     6   26 use Exporter qw(import);
  6         8  
  6         4889  
6              
7             our @EXPORT = qw(
8             _AQT_init
9             _AQT_deinit
10             _AQT_addObject
11             _AQT_findObjects
12             _AQT_delete
13             _AQT_clear
14             );
15              
16             # recursive method which adds levels to the quadtree
17             sub _addLevel
18             {
19 89     89   165 my ($self, $depth, @coords) = @_;
20 89         147 my $node = {
21             AREA => \@coords,
22             };
23              
24 89 100       143 if ($depth < $self->{DEPTH}) {
25 21         35 my ($xmin, $ymin, $xmax, $ymax) = @coords;
26 21         52 my $xmid = $xmin + ($xmax - $xmin) / 2;
27 21         42 my $ymid = $ymin + ($ymax - $ymin) / 2;
28 21         28 $depth += 1;
29              
30             # segment in the following order:
31             # top left, top right, bottom left, bottom right
32             $node->{CHILDREN} = [
33 21         48 _addLevel($self, $depth, $xmin, $ymid, $xmid, $ymax),
34             _addLevel($self, $depth, $xmid, $ymid, $xmax, $ymax),
35             _addLevel($self, $depth, $xmin, $ymin, $xmid, $ymid),
36             _addLevel($self, $depth, $xmid, $ymin, $xmax, $ymid),
37             ];
38             }
39             else {
40             # leaves must have empty aref in objects
41 68         100 $node->{OBJECTS} = [];
42             }
43              
44 89         191 return $node;
45             }
46              
47             # this private method executes $code on every leaf node of the tree
48             # which is within the circular shape
49             sub _loopOnNodesInCircle
50             {
51 12     12   30 my ($self, @coords) = @_;
52              
53             # this is a bounding box of a circle
54             # it will help us filter out all the far away shapes
55 12         37 my @box = (
56             $coords[0] - $coords[2],
57             $coords[1] - $coords[2],
58             $coords[0] + $coords[2],
59             $coords[1] + $coords[2],
60             );
61              
62             # avoid squaring the radius on each iteration
63 12         34 my $radius_squared = $coords[2] ** 2;
64              
65 12         16 my @nodes;
66 12         16 for my $current (@{_loopOnNodesInRectangle($self, @box)}) {
  12         22  
67 28         35 my ($cxmin, $cymin, $cxmax, $cymax) = @{$current->{AREA}};
  28         75  
68              
69 28 100       72 my $cx = $coords[0] < $cxmin
    100          
70             ? $cxmin
71             : $coords[0] > $cxmax
72             ? $cxmax
73             : $coords[0]
74             ;
75              
76 28 100       67 my $cy = $coords[1] < $cymin
    100          
77             ? $cymin
78             : $coords[1] > $cymax
79             ? $cymax
80             : $coords[1]
81             ;
82              
83 28 100       76 push @nodes, $current
84             if ($coords[0] - $cx) ** 2 + ($coords[1] - $cy) ** 2
85             <= $radius_squared;
86             }
87              
88 12         35 return \@nodes;
89             }
90              
91             # this private method executes $code on every leaf node of the tree
92             # which is within the rectangular shape
93             sub _loopOnNodesInRectangle
94             {
95 125     125   221 my ($self, @coords) = @_;
96              
97 125         151 my @nodes;
98 125         180 my @loopargs = $self->{ROOT};
99 125         177 for my $current (@loopargs) {
100              
101             # first check if obj overlaps current segment.
102             next if
103             $coords[0] > $current->{AREA}[2] ||
104             $coords[2] < $current->{AREA}[0] ||
105             $coords[1] > $current->{AREA}[3] ||
106 1177 100 100     4090 $coords[3] < $current->{AREA}[1];
      100        
      100        
107              
108 511 100       743 if ($current->{CHILDREN}) {
109 263         284 push @loopargs, @{$current->{CHILDREN}};
  263         434  
110             } else {
111             # segment is a leaf and overlaps the obj
112 248         340 push @nodes, $current;
113             }
114             }
115              
116 125         335 return \@nodes;
117             }
118              
119             # choose the right function based on argument count
120             # first argument is always $self, the rest are coords
121             sub _loopOnNodes
122             {
123 125 100   125   255 goto \&_loopOnNodesInCircle if @_ == 4;
124 113         294 goto \&_loopOnNodesInRectangle;
125             }
126              
127             sub _AQT_init
128             {
129 5     5   11 my $obj = shift;
130              
131 5         14 $obj->{BACKREF} = {};
132             $obj->{ROOT} = _addLevel(
133             $obj,
134             1, #current depth
135             $obj->{XMIN},
136             $obj->{YMIN},
137             $obj->{XMAX},
138             $obj->{YMAX},
139 5         18 );
140             }
141              
142             sub _AQT_deinit
143       5     {
144             # no nothing in PP implementation
145             }
146              
147             sub _AQT_addObject
148             {
149 55     55   87 my ($self, $object, @coords) = @_;
150              
151 55         69 for my $node (@{_loopOnNodes($self, @coords)}) {
  55         102  
152 60         67 push @{$node->{OBJECTS}}, $object;
  60         106  
153 60         75 push @{$self->{BACKREF}{$object}}, $node;
  60         191  
154             }
155             }
156              
157             sub _AQT_findObjects
158             {
159 70     70   123 my ($self, @coords) = @_;
160              
161             # map returned nodes to an array containing all of
162             # their objects
163             return [
164             map {
165 186         206 @{$_->{OBJECTS}}
  186         527  
166 70         78 } @{_loopOnNodes($self, @coords)}
  70         115  
167             ];
168             }
169              
170             sub _AQT_delete
171             {
172 1     1   3 my ($self, $object) = @_;
173              
174 1 50       4 return unless exists $self->{BACKREF}{$object};
175              
176 1         3 for my $node (@{$self->{BACKREF}{$object}}) {
  1         3  
177 1         2 $node->{OBJECTS} = [ grep {$_ ne $object} @{$node->{OBJECTS}} ];
  2         12  
  1         2  
178             }
179              
180 1         4 delete $self->{BACKREF}{$object};
181             }
182              
183             sub _AQT_clear
184             {
185 3     3   6 my ($self) = @_;
186              
187 3         4 for my $key (keys %{$self->{BACKREF}}) {
  3         29  
188 33         34 for my $node (@{$self->{BACKREF}{$key}}) {
  33         43  
189 38         67 $node->{OBJECTS} = [];
190             }
191             }
192 3         17 $self->{BACKREF} = {};
193             }
194              
195             1;
196