xref: /6.6.0/geocouch/vtree/test/004-util.t (revision 92def13f)
1#!/usr/bin/env escript
2%% -*- erlang -*-
3
4% Licensed under the Apache License, Version 2.0 (the "License"); you may not
5% use this file except in compliance with the License. You may obtain a copy of
6% the License at
7%
8%   http://www.apache.org/licenses/LICENSE-2.0
9%
10% Unless required by applicable law or agreed to in writing, software
11% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13% License for the specific language governing permissions and limitations under
14% the License.
15
16-define(MOD, vtree_util).
17
18main(_) ->
19    % Set the random seed once, for the whole test suite
20    rand:seed(exrop, {1, 11, 91}),
21
22    code:add_pathz(filename:dirname(escript:script_name())),
23    etap:plan(55),
24    case (catch test()) of
25        ok ->
26            etap:end_tests();
27        Other ->
28            % Somehow etap:diag/1 and etap:bail/1 don't work properly
29            %etap:diag(io_lib:format("Test died abnormally: ~p", [Other])),
30            %etap:bail(Other),
31            io:format("Test died abnormally:~n~p~n", [Other])
32    end,
33    ok.
34
35test() ->
36    test_min(),
37    test_max(),
38    test_calc_perimeter(),
39    test_calc_volume(),
40    test_calc_mbb(),
41    test_nodes_mbb(),
42    test_intersect_mbb(),
43    test_find_min_value(),
44    test_within_mbb(),
45    ok.
46
47test_min() ->
48    Less = fun(A, B) -> A < B end,
49
50    etap:is(?MOD:min({-5, 2}, Less), -5, "min (a)"),
51    etap:is(?MOD:min({2, -5}, Less), -5, "min (b)"),
52    etap:is(?MOD:min({39.450, 70}, Less), 39.450, "min (c)"),
53    etap:is(?MOD:min({70, 39.450}, Less), 39.450, "min (d)"),
54    etap:is(?MOD:min({9572, 9572}, Less), 9572, "min (e)"),
55
56    etap:is(-485, ?MOD:min([842, -84.29, -485, 8372, 294.93], Less),
57            "min (f)").
58
59test_max() ->
60    Less = fun(A, B) -> A < B end,
61
62    etap:is(?MOD:max({-5, 2}, Less), 2, "max (a)"),
63    etap:is(?MOD:max({2, -5}, Less), 2, "max (b)"),
64    etap:is(?MOD:max({39.450, 70}, Less), 70, "max (c)"),
65    etap:is(?MOD:max({70, 39.450}, Less), 70, "max (d)"),
66    etap:is(?MOD:max({9572, 9572}, Less), 9572, "max (e)"),
67
68    etap:is(?MOD:max([842, -84.29, -485, 8372, 294.93], Less), 8372,
69            "max (f)").
70
71
72test_calc_perimeter() ->
73    Mbb1 = [{-38, 74.2}, {38, 948}, {-480, -27}, {-7, -4.28}, {84.3, 923.8}],
74    Mbb2 = [{39, 938}, {-937, 8424}, {-1000, -82}, {4.72, 593}, {372, 490.3}],
75
76    etap:is(?MOD:calc_perimeter(Mbb1), 2317.42, "Perimeter of an MBB (a)"),
77    etap:is(?MOD:calc_perimeter(Mbb2), 11884.58, "Perimeter of an MBB (b)").
78
79
80test_calc_volume() ->
81    Mbb1 = [{-38, 74.2}, {38, 948}, {-480, -27}, {-7, -4.28}, {84.3, 923.8}],
82    Mbb2 = [{39, 938}, {-937, 8424}, {-1000, -82}, {4.72, 593}, {372, 490.3}],
83    Mbb3 = [{48, 472}, {-9.38, 26.1}, {-29, -29}, {-1.4, 30}, {39.9, 100}],
84
85    etap:is(?MOD:calc_volume(Mbb1), 105614137268.64, "Volume of an MBB (a)"),
86    etap:is(?MOD:calc_volume(Mbb2), 537642320109142.24,
87            "Volume of an MBB (b)"),
88    etap:is(?MOD:calc_volume(Mbb3), 0, "Zero volume of an MBB").
89
90
91test_calc_mbb() ->
92    Less = fun(A, B) -> A < B end,
93
94    Mbb1 = [{-38, 74.2}, {38, 948}, {-27, -3480}, {-4.28, -7}, {84.4, 923.1}],
95    Mbb2 = [{39, 938}, {-937, 8424}, {-1, 0}, {372, 490.2}, {593, 45982.72}],
96    etap:is(?MOD:calc_mbb([Mbb1, Mbb2], Less),
97            [{-38, 938}, {-937, 8424}, {-27, 0}, {-4.28, 490.2},
98             {84.4, 45982.72}],
99            "Combine two MBBs"),
100    etap:is(?MOD:calc_mbb([Mbb1], Less), Mbb1,
101            "Single MBB (nothing to combine)").
102
103
104test_nodes_mbb() ->
105    Less = fun(A, B) -> A < B end,
106
107    Mbb1 = [{-38, 74.2}, {38, 948}, {-480, -27}, {-7, -4.28}, {84.3, 923.8}],
108    Mbb2 = [{39, 938}, {-937, 8424}, {-1000, -82}, {4.72, 593}, {372, 490.3}],
109    Mbb3 = [{48, 472}, {-9.38, 26.1}, {-382, -29}, {-1.4, 30}, {39.9, 100}],
110    Node1 = {Mbb1, 3487},
111    Node2 = {Mbb2, 823},
112    Node3 = {Mbb3, 96242},
113
114    etap:is(?MOD:nodes_mbb([Node1, Node2], Less),
115            vtree_util:calc_mbb([Mbb1, Mbb2], Less),
116            "Calculate the MBB of two nodes (a)"),
117    etap:is(?MOD:nodes_mbb([Node2, Node3], Less),
118            vtree_util:calc_mbb([Mbb2, Mbb3], Less),
119            "Calculate the MBB of two nodes (b)"),
120    etap:is(?MOD:nodes_mbb([Node2], Less), vtree_util:calc_mbb([Mbb2], Less),
121            "Calculate the MBB of a single node (a)"),
122    etap:is(?MOD:nodes_mbb([Node3], Less), vtree_util:calc_mbb([Mbb3], Less),
123            "Calculate the MBB of a single node (b)").
124
125
126test_intersect_mbb() ->
127    Less = fun(A, B) -> A < B end,
128
129    Mbb1 = [{-38, 74.2}, {38, 948}],
130    Mbb2 = [{-480, 5}, {-7, 428.74}],
131    Mbb3 = [{84.3, 923.8}, {39, 938}],
132    Mbb4 = [{-937, 8424}, {-1000, -82}],
133    Mbb5 = [{4.72, 593}, {-472, -390.3}],
134    Mbb6 = [{4.72, 593}, {-472, 390.3}, {-480, 5}, {-7, 428.74}],
135    Mbb7 = [{84.3, 923.8}, {39, 938}, {-937, 8424}, {-1000, 82}],
136    Mbb8 = [{222, 222}, {-432.39, -294.20}],
137    Mbb9 = [{-222, -222}, {-382.39, 294.20}],
138    Mbb10 = [{593, 777}, {-432.39, -294.20}],
139    Mbb11 = [{593, 593}, {-432.39, -294.20}],
140
141    Mbb12 = [{nil, nil}, {-7, 428.74}],
142    Mbb13 = [{-480, 5}, {nil, nil}],
143    Mbb14 = [{nil, nil}, {nil, nil}],
144    Mbb15 = [{4.72, 593}, {nil, nil}, {-480, 5}, {-7, 428.74}],
145    Mbb16 = [{4.72, 593}, {nil, nil}, {-480, 5}, {nil, nil}],
146    Mbb17 = [{nil, nil}, {nil, nil}, {nil, nil}, {nil, nil}],
147
148    Mbb18 = [{nil, 5}, {-7, 428.74}],
149    Mbb19 = [{-480, 5}, {nil, 428.74}],
150    Mbb20 = [{-480, nil}, {-7, 428.74}],
151    Mbb21 = [{-480, 5}, {-7, nil}],
152    Mbb22 = [{4.72, 593}, {nil, 390.3}, {nil, 5}, {-7, 428.74}],
153    Mbb23 = [{4.72, nil}, {-472, 390.3}, {-480, nil}, {-7, nil}],
154    Mbb24 = [{4.72, nil}, {nil, 390.3}, {nil, nil}, {-7, nil}],
155
156
157    etap:is(?MOD:intersect_mbb(Mbb1, Mbb2, Less), [{-38,5},{38,428.74}],
158            "MBBs intersect (two dimensions)"),
159    etap:is(?MOD:intersect_mbb(Mbb2, Mbb3, Less), overlapfree,
160            "MBBs are overlap-free (first dimension)"),
161    etap:is(?MOD:intersect_mbb(Mbb3, Mbb4, Less), overlapfree,
162            "MBBs are overlap-free (second dimension)"),
163    etap:is(?MOD:intersect_mbb(Mbb4, Mbb5, Less), Mbb5,
164            "One MBB is in another MBB"),
165    etap:is(?MOD:intersect_mbb(Mbb6, Mbb7, Less),
166            [{84.3,593},{39,390.3},{-480,5},{-7,82}],
167            "MBBs intersect (4 dimensions)"),
168    etap:is(?MOD:intersect_mbb(Mbb5, Mbb8, Less),
169            [{222,222},{-432.39,-390.3}],
170            "One MBBs has zero volume and intersects"),
171    etap:is(?MOD:intersect_mbb(Mbb3, Mbb9, Less),
172            overlapfree,
173            "One MBBs has zero volume and doesn't overlap (is overlap-free)"),
174    etap:is(?MOD:intersect_mbb(Mbb5, Mbb10, Less),
175            [{593, 593}, {-432.39, -390.3}],
176            "One MBB touches another MBB"),
177    etap:is(?MOD:intersect_mbb(Mbb5, Mbb11, Less),
178            [{593, 593}, {-432.39, -390.3}],
179            "A zero volume MBB touches another MBB"),
180
181    etap:is(?MOD:intersect_mbb(Mbb1, Mbb12, Less), [{-38,74.2},{38,428.74}],
182            "MBBs intersect (two dimensions, one range is a wildcard) (a)"),
183    etap:is(?MOD:intersect_mbb(Mbb1, Mbb13, Less), [{-38,5},{38,948}],
184            "MBBs intersect (two dimensions, one range is a wildcard) (b)"),
185    etap:is(?MOD:intersect_mbb(Mbb1, Mbb14, Less), Mbb1,
186            "MBBs intersect (two dimensions, one MBB has wildcards only)"),
187    etap:is(?MOD:intersect_mbb(Mbb15, Mbb7, Less),
188            [{84.3,593},{39,938},{-480,5},{-7,82}],
189            "MBBs intersect (4 dimensions, one range is a wildcard)"),
190    etap:is(?MOD:intersect_mbb(Mbb16, Mbb7, Less),
191            [{84.3,593},{39,938},{-480,5},{-1000,82}],
192            "MBBs intersect (4 dimensions, two ranges are a wildcard)"),
193    etap:is(?MOD:intersect_mbb(Mbb17, Mbb7, Less), Mbb7,
194            "MBBs intersect (4 dimensions, one MBB has wildcards only)"),
195
196    etap:is(?MOD:intersect_mbb(Mbb1, Mbb18, Less), [{-38,5},{38,428.74}],
197            "MBBs intersect (two dimensions, open range at start) (a)"),
198    etap:is(?MOD:intersect_mbb(Mbb1, Mbb19, Less), [{-38,5},{38,428.74}],
199            "MBBs intersect (two dimensions, open range at start) (b)"),
200    etap:is(?MOD:intersect_mbb(Mbb1, Mbb20, Less), [{-38,74.2},{38,428.74}],
201            "MBBs intersect (two dimensions, open range at end) (a)"),
202    etap:is(?MOD:intersect_mbb(Mbb1, Mbb21, Less), [{-38,5},{38,948}],
203            "MBBs intersect (two dimensions, open range at end) (b)"),
204    etap:is(?MOD:intersect_mbb(Mbb22, Mbb7, Less),
205            [{84.3,593},{39,390.3},{-937,5},{-7,82}],
206            "MBBs intersect (4 dimensions, two open range at start)"),
207    etap:is(?MOD:intersect_mbb(Mbb24, Mbb7, Less),
208            [{84.3,923.8},{39,390.3},{-937,8424},{-7,82}],
209            "MBBs intersect (4 dimensions, open ranges and wildcard mixed)").
210
211
212test_find_min_value() ->
213    Pair1 = {a, 1},
214    Pair2 = {b, 2},
215    Pair3 = {c, 3},
216    Pair4 = {d, 4},
217    Pair5 = {e, 5},
218
219    MinFun = fun({_Key, Value}) -> Value+3 end,
220    etap:is(?MOD:find_min_value(MinFun, [Pair3, Pair4, Pair2, Pair1]),
221            {4, Pair1}, "Last item has minimum value"),
222    etap:is(?MOD:find_min_value(MinFun, [Pair1, Pair4, Pair2, Pair3]),
223            {4, Pair1}, "First item has minimum value"),
224    etap:is(?MOD:find_min_value(MinFun, [Pair5, Pair4, Pair2, Pair3]),
225            {5, Pair2}, "Item in the middle has minimum value"),
226    etap:throws_ok(fun() -> ?MOD:find_min_value(MinFun, []) end,
227                   function_clause, "Empty list throws error").
228
229
230test_within_mbb() ->
231    Less = fun(A, B) -> A < B end,
232
233    Mbb1 = [{-38, 74.2}, {38, 948}],
234    Mbb2 = [{-37.3, 50}, {43, 428.74}],
235    Mbb3 = [{-37.3, 74.2}, {43, 428.74}],
236    Mbb4 = [{400.72, 593}, {-472, -390.3}],
237    Mbb5 = [{4.72, 593}, {72, 390.3}],
238    Mbb6 = [{-48, 84.2}, {28, 958}],
239    Mbb7 = [{-48.4, -38}, {28, 958}],
240
241    etap:is(?MOD:within_mbb(Mbb2, Mbb1, Less), true,
242            "The MBB is completely within the other"),
243    etap:is(?MOD:within_mbb(Mbb3, Mbb1, Less), true,
244            "The MBB is completely within the other, but touches the other"),
245    etap:is(?MOD:within_mbb(Mbb1, Mbb1, Less), true,
246            "The MBB is the same as the other"),
247    etap:is(?MOD:within_mbb(Mbb4, Mbb1, Less), false,
248            "The MBB is complely outside the other"),
249    etap:is(?MOD:within_mbb(Mbb5, Mbb1, Less), false,
250            "The MBB intersects the other"),
251    etap:is(?MOD:within_mbb(Mbb6, Mbb1, Less), false,
252            "The MBB encloses the other"),
253    etap:is(?MOD:within_mbb(Mbb7, Mbb1, Less), false,
254            "The MBB is outside, but touches the other").
255