View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.geometry.core.partitioning.bsp;
18  
19  import java.util.stream.StreamSupport;
20  
21  import org.apache.commons.geometry.core.partitioning.test.AttributeBSPTree;
22  import org.apache.commons.geometry.core.partitioning.test.AttributeBSPTree.AttributeNode;
23  import org.apache.commons.geometry.core.partitioning.test.PartitionTestUtils;
24  import org.apache.commons.geometry.core.partitioning.test.TestLine;
25  import org.apache.commons.geometry.core.partitioning.test.TestPoint2D;
26  import org.junit.jupiter.api.Assertions;
27  import org.junit.jupiter.api.Test;
28  
29  class AbstractBSPTreeMergeOperatorTest {
30  
31      @Test
32      void testMerge_singleNodeTreeWithSingleNodeTree() {
33          // arrange
34          final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
35          a.getRoot().setAttribute("A");
36  
37          final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
38          b.getRoot().setAttribute("B");
39  
40          final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
41  
42          final TestMergeOperator mergeOp = new TestMergeOperator();
43  
44          // act
45          mergeOp.apply(a, b, c);
46  
47          // assert
48          Assertions.assertEquals(1, a.count());
49          Assertions.assertEquals(1, b.count());
50          Assertions.assertEquals(1, c.count());
51  
52          Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, 1)).getAttribute());
53          Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
54  
55          Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
56          Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
57  
58          Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
59          Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
60          Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
61          Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
62  
63          PartitionTestUtils.assertTreeStructure(a);
64          PartitionTestUtils.assertTreeStructure(b);
65          PartitionTestUtils.assertTreeStructure(c);
66      }
67  
68      @Test
69      void testMerge_singleNodeTreeWithMultiNodeTree() {
70          // arrange
71          final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
72          a.getRoot().cut(TestLine.X_AXIS)
73              .getPlus().attr("A")
74              .getParent()
75              .getMinus().attr("a");
76  
77          final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
78          b.getRoot().setAttribute("B");
79  
80          final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
81  
82          final TestMergeOperator mergeOp = new TestMergeOperator();
83  
84          // act
85          mergeOp.apply(a, b, c);
86  
87          // assert
88          Assertions.assertEquals(3, a.count());
89          Assertions.assertEquals(1, b.count());
90          Assertions.assertEquals(3, c.count());
91  
92          Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
93          Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
94  
95          Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
96          Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
97  
98          Assertions.assertEquals("Ba", c.findNode(new TestPoint2D(1, 1)).getAttribute());
99          Assertions.assertEquals("Ba", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
100         Assertions.assertEquals("BA", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
101         Assertions.assertEquals("BA", c.findNode(new TestPoint2D(1, -1)).getAttribute());
102 
103         PartitionTestUtils.assertTreeStructure(a);
104         PartitionTestUtils.assertTreeStructure(b);
105         PartitionTestUtils.assertTreeStructure(c);
106     }
107 
108     @Test
109     void testMerge_multiNodeTreeWithSingleNodeTree() {
110         // arrange
111         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
112         a.getRoot().setAttribute("A");
113 
114         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
115         b.getRoot().cut(TestLine.X_AXIS)
116             .getPlus().attr("B")
117             .getParent()
118             .getMinus().attr("b");
119 
120         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
121 
122         final TestMergeOperator mergeOp = new TestMergeOperator();
123 
124         // act
125         mergeOp.apply(a, b, c);
126 
127         // assert
128         Assertions.assertEquals(1, a.count());
129         Assertions.assertEquals(3, b.count());
130         Assertions.assertEquals(3, c.count());
131 
132         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, 1)).getAttribute());
133         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
134 
135         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, 1)).getAttribute());
136         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
137 
138         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
139         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
140         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
141         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
142 
143         PartitionTestUtils.assertTreeStructure(a);
144         PartitionTestUtils.assertTreeStructure(b);
145         PartitionTestUtils.assertTreeStructure(c);
146     }
147 
148     @Test
149     void testMerge_cutsIntersect() {
150         // arrange
151         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
152         a.getRoot().cut(TestLine.X_AXIS)
153             .getPlus().attr("A")
154             .getParent()
155             .getMinus().attr("a");
156 
157         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
158         b.getRoot().cut(TestLine.Y_AXIS)
159             .getPlus().attr("B")
160             .getParent()
161             .getMinus().attr("b");
162 
163         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
164 
165         final TestMergeOperator mergeOp = new TestMergeOperator();
166 
167         // act
168         mergeOp.apply(a, b, c);
169 
170         // assert
171         Assertions.assertEquals(3, a.count());
172         Assertions.assertEquals(3, b.count());
173         Assertions.assertEquals(7, c.count());
174 
175         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
176         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
177 
178         Assertions.assertEquals("B", b.findNode(new TestPoint2D(1, 0)).getAttribute());
179         Assertions.assertEquals("b", b.findNode(new TestPoint2D(-1, 0)).getAttribute());
180 
181         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
182         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
183         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
184         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
185 
186         PartitionTestUtils.assertTreeStructure(a);
187         PartitionTestUtils.assertTreeStructure(b);
188         PartitionTestUtils.assertTreeStructure(c);
189     }
190 
191     @Test
192     void testMerge_cutsParallel() {
193         // arrange
194         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
195         a.getRoot().cut(TestLine.X_AXIS)
196             .getPlus().attr("A")
197             .getParent()
198             .getMinus().attr("a");
199 
200         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
201         b.getRoot().cut(TestLine.X_AXIS)
202             .getPlus().attr("B")
203             .getParent()
204             .getMinus().attr("b");
205 
206         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
207 
208         final TestMergeOperator mergeOp = new TestMergeOperator();
209 
210         // act
211         mergeOp.apply(a, b, c);
212 
213         // assert
214         Assertions.assertEquals(3, a.count());
215         Assertions.assertEquals(3, b.count());
216         Assertions.assertEquals(3, c.count());
217 
218         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
219         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
220 
221         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, 1)).getAttribute());
222         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
223 
224         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
225         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
226         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
227         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
228 
229         PartitionTestUtils.assertTreeStructure(a);
230         PartitionTestUtils.assertTreeStructure(b);
231         PartitionTestUtils.assertTreeStructure(c);
232     }
233 
234     @Test
235     void testMerge_cutsAntiParallel() {
236         // arrange
237         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
238         a.getRoot().cut(TestLine.X_AXIS)
239             .getPlus().attr("A")
240             .getParent()
241             .getMinus().attr("a");
242 
243         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
244         b.getRoot().cut(new TestLine(new TestPoint2D(1, 0), TestPoint2D.ZERO))
245             .getPlus().attr("B")
246             .getParent()
247             .getMinus().attr("b");
248 
249         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
250 
251         final TestMergeOperator mergeOp = new TestMergeOperator();
252 
253         // act
254         mergeOp.apply(a, b, c);
255 
256         // assert
257         Assertions.assertEquals(3, a.count());
258         Assertions.assertEquals(3, b.count());
259         Assertions.assertEquals(3, c.count());
260 
261         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
262         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
263 
264         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
265         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, -1)).getAttribute());
266 
267         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
268         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
269         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
270         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(1, -1)).getAttribute());
271 
272         PartitionTestUtils.assertTreeStructure(a);
273         PartitionTestUtils.assertTreeStructure(b);
274         PartitionTestUtils.assertTreeStructure(c);
275     }
276 
277     @Test
278     void testMerge_cutOnPlusSide_parallel() {
279         // arrange
280         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
281         a.getRoot().cut(TestLine.X_AXIS)
282             .getPlus().attr("A")
283             .getParent()
284             .getMinus().attr("a");
285 
286         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
287         b.getRoot().cut(new TestLine(new TestPoint2D(0, -2), new TestPoint2D(1, -2)))
288             .getPlus().attr("B")
289             .getParent()
290             .getMinus().attr("b");
291 
292         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
293 
294         final TestMergeOperator mergeOp = new TestMergeOperator();
295 
296         // act
297         mergeOp.apply(a, b, c);
298 
299         // assert
300         Assertions.assertEquals(3, a.count());
301         Assertions.assertEquals(3, b.count());
302         Assertions.assertEquals(5, c.count());
303 
304         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
305         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
306 
307         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, -1)).getAttribute());
308         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -3)).getAttribute());
309 
310         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
311         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
312         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
313         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(1, -1)).getAttribute());
314 
315         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -3)).getAttribute());
316         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -3)).getAttribute());
317 
318         PartitionTestUtils.assertTreeStructure(a);
319         PartitionTestUtils.assertTreeStructure(b);
320         PartitionTestUtils.assertTreeStructure(c);
321     }
322 
323     @Test
324     void testMerge_cutOnPlusSide_antiParallel() {
325         // arrange
326         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
327         a.getRoot().cut(TestLine.X_AXIS)
328             .getPlus().attr("A")
329             .getParent()
330             .getMinus().attr("a");
331 
332         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
333         b.getRoot().cut(new TestLine(new TestPoint2D(1, -2), new TestPoint2D(0, -2)))
334             .getPlus().attr("B")
335             .getParent()
336             .getMinus().attr("b");
337 
338         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
339 
340         final TestMergeOperator mergeOp = new TestMergeOperator();
341 
342         // act
343         mergeOp.apply(a, b, c);
344 
345         // assert
346         Assertions.assertEquals(3, a.count());
347         Assertions.assertEquals(3, b.count());
348         Assertions.assertEquals(5, c.count());
349 
350         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
351         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
352 
353         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, -1)).getAttribute());
354         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, -3)).getAttribute());
355 
356         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
357         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
358         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
359         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
360 
361         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -3)).getAttribute());
362         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(1, -3)).getAttribute());
363 
364         PartitionTestUtils.assertTreeStructure(a);
365         PartitionTestUtils.assertTreeStructure(b);
366         PartitionTestUtils.assertTreeStructure(c);
367     }
368 
369     @Test
370     void testMerge_cutOnMinusSide_parallel() {
371         // arrange
372         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
373         a.getRoot().cut(TestLine.X_AXIS)
374             .getPlus().attr("A")
375             .getParent()
376             .getMinus().attr("a");
377 
378         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
379         b.getRoot().cut(new TestLine(new TestPoint2D(0, 2), new TestPoint2D(1, 2)))
380             .getPlus().attr("B")
381             .getParent()
382             .getMinus().attr("b");
383 
384         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
385 
386         final TestMergeOperator mergeOp = new TestMergeOperator();
387 
388         // act
389         mergeOp.apply(a, b, c);
390 
391         // assert
392         Assertions.assertEquals(3, a.count());
393         Assertions.assertEquals(3, b.count());
394         Assertions.assertEquals(5, c.count());
395 
396         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
397         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
398 
399         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, 1)).getAttribute());
400         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, 3)).getAttribute());
401 
402         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(1, 1)).getAttribute());
403         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
404         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
405         Assertions.assertEquals("AB", c.findNode(new TestPoint2D(1, -1)).getAttribute());
406 
407         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(-1, 3)).getAttribute());
408         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(1, 3)).getAttribute());
409 
410         PartitionTestUtils.assertTreeStructure(a);
411         PartitionTestUtils.assertTreeStructure(b);
412         PartitionTestUtils.assertTreeStructure(c);
413     }
414 
415     @Test
416     void testMerge_cutOnMinusSide_antiParallel() {
417         // arrange
418         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
419         a.getRoot().cut(TestLine.X_AXIS)
420             .getPlus().attr("A")
421             .getParent()
422             .getMinus().attr("a");
423 
424         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
425         b.getRoot().cut(new TestLine(new TestPoint2D(1, 2), new TestPoint2D(0, 2)))
426             .getPlus().attr("B")
427             .getParent()
428             .getMinus().attr("b");
429 
430         final AttributeBSPTree<TestPoint2D, String> c = new AttributeBSPTree<>();
431 
432         final TestMergeOperator mergeOp = new TestMergeOperator();
433 
434         // act
435         mergeOp.apply(a, b, c);
436 
437         // assert
438         Assertions.assertEquals(3, a.count());
439         Assertions.assertEquals(3, b.count());
440         Assertions.assertEquals(5, c.count());
441 
442         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
443         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
444 
445         Assertions.assertEquals("b", b.findNode(new TestPoint2D(0, 1)).getAttribute());
446         Assertions.assertEquals("B", b.findNode(new TestPoint2D(0, 3)).getAttribute());
447 
448         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(1, 1)).getAttribute());
449         Assertions.assertEquals("ab", c.findNode(new TestPoint2D(-1, 1)).getAttribute());
450         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(-1, -1)).getAttribute());
451         Assertions.assertEquals("Ab", c.findNode(new TestPoint2D(1, -1)).getAttribute());
452 
453         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(-1, 3)).getAttribute());
454         Assertions.assertEquals("aB", c.findNode(new TestPoint2D(1, 3)).getAttribute());
455 
456         PartitionTestUtils.assertTreeStructure(a);
457         PartitionTestUtils.assertTreeStructure(b);
458         PartitionTestUtils.assertTreeStructure(c);
459     }
460 
461     @Test
462     void testMerge_outputIsFirstInput() {
463         // arrange
464         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
465         a.getRoot().cut(TestLine.X_AXIS)
466             .getPlus().attr("A")
467             .getParent()
468             .getMinus().attr("a");
469 
470         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
471         b.getRoot().cut(TestLine.Y_AXIS)
472             .getPlus().attr("B")
473             .getParent()
474             .getMinus().attr("b");
475 
476         final TestMergeOperator mergeOp = new TestMergeOperator();
477 
478         // act
479         mergeOp.apply(a, b, a);
480 
481         // assert
482         Assertions.assertEquals(7, a.count());
483         Assertions.assertEquals(3, b.count());
484 
485         Assertions.assertEquals("B", b.findNode(new TestPoint2D(1, 0)).getAttribute());
486         Assertions.assertEquals("b", b.findNode(new TestPoint2D(-1, 0)).getAttribute());
487 
488         Assertions.assertEquals("aB", a.findNode(new TestPoint2D(1, 1)).getAttribute());
489         Assertions.assertEquals("ab", a.findNode(new TestPoint2D(-1, 1)).getAttribute());
490         Assertions.assertEquals("Ab", a.findNode(new TestPoint2D(-1, -1)).getAttribute());
491         Assertions.assertEquals("AB", a.findNode(new TestPoint2D(1, -1)).getAttribute());
492 
493         PartitionTestUtils.assertTreeStructure(a);
494         PartitionTestUtils.assertTreeStructure(b);
495     }
496 
497     @Test
498     void testMerge_outputIsSecondInput() {
499         // arrange
500         final AttributeBSPTree<TestPoint2D, String> a = new AttributeBSPTree<>();
501         a.getRoot().cut(TestLine.X_AXIS)
502             .getPlus().attr("A")
503             .getParent()
504             .getMinus().attr("a");
505 
506         final AttributeBSPTree<TestPoint2D, String> b = new AttributeBSPTree<>();
507         b.getRoot().cut(TestLine.Y_AXIS)
508             .getPlus().attr("B")
509             .getParent()
510             .getMinus().attr("b");
511 
512         final TestMergeOperator mergeOp = new TestMergeOperator();
513 
514         // act
515         mergeOp.apply(a, b, b);
516 
517         // assert
518         Assertions.assertEquals(3, a.count());
519         Assertions.assertEquals(7, b.count());
520 
521         Assertions.assertEquals("a", a.findNode(new TestPoint2D(0, 1)).getAttribute());
522         Assertions.assertEquals("A", a.findNode(new TestPoint2D(0, -1)).getAttribute());
523 
524         Assertions.assertEquals("aB", b.findNode(new TestPoint2D(1, 1)).getAttribute());
525         Assertions.assertEquals("ab", b.findNode(new TestPoint2D(-1, 1)).getAttribute());
526         Assertions.assertEquals("Ab", b.findNode(new TestPoint2D(-1, -1)).getAttribute());
527         Assertions.assertEquals("AB", b.findNode(new TestPoint2D(1, -1)).getAttribute());
528 
529         PartitionTestUtils.assertTreeStructure(a);
530         PartitionTestUtils.assertTreeStructure(b);
531     }
532 
533     private static class TestMergeOperator extends AbstractBSPTreeMergeOperator<TestPoint2D, AttributeNode<TestPoint2D, String>> {
534 
535         /** Perform the test merge operation with the given arguments.
536          * @param input1
537          * @param input2
538          * @param output
539          */
540         public void apply(final AttributeBSPTree<TestPoint2D, String> input1, final AttributeBSPTree<TestPoint2D, String> input2,
541                           final AttributeBSPTree<TestPoint2D, String> output) {
542             performMerge(input1, input2, output);
543         }
544 
545         /** {@inheritDoc} */
546         @Override
547         protected AttributeNode<TestPoint2D, String> mergeLeaf(final AttributeNode<TestPoint2D, String> node1,
548                                                                final AttributeNode<TestPoint2D, String> node2) {
549 
550             final AttributeNode<TestPoint2D, String> leaf = node1.isLeaf() ? node1 : node2;
551             final AttributeNode<TestPoint2D, String> subtree = node1.isInternal() ? node1 : node2;
552 
553             final String attr = leaf.getAttribute();
554 
555             final AttributeNode<TestPoint2D, String> output = outputSubtree(subtree);
556             StreamSupport.stream(output.nodes().spliterator(), false)
557                 .filter(BSPTree.Node::isLeaf)
558                 .forEach(n -> n.setAttribute(attr + n.getAttribute()));
559 
560             return output;
561         }
562     }
563 }