1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.geometry.core.partitioning.bsp;
18
19 import java.util.ArrayList;
20 import java.util.Iterator;
21 import java.util.List;
22 import java.util.function.Function;
23 import java.util.stream.Stream;
24
25 import org.apache.commons.geometry.core.Point;
26 import org.apache.commons.geometry.core.RegionLocation;
27 import org.apache.commons.geometry.core.internal.IteratorTransform;
28 import org.apache.commons.geometry.core.partitioning.BoundarySource;
29 import org.apache.commons.geometry.core.partitioning.Hyperplane;
30 import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
31 import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
32 import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
33 import org.apache.commons.geometry.core.partitioning.HyperplaneSubset;
34 import org.apache.commons.geometry.core.partitioning.Split;
35 import org.apache.commons.geometry.core.partitioning.SplitLocation;
36 import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.ClosestFirstVisitor;
37
38
39
40
41
42
43
44
45
46
47 public abstract class AbstractRegionBSPTree<
48 P extends Point<P>,
49 N extends AbstractRegionBSPTree.AbstractRegionNode<P, N>>
50 extends AbstractBSPTree<P, N> implements HyperplaneBoundedRegion<P> {
51
52
53 private static final RegionCutRule DEFAULT_REGION_CUT_RULE = RegionCutRule.MINUS_INSIDE;
54
55
56 private static final double UNKNOWN_SIZE = -1.0;
57
58
59 private double boundarySize = UNKNOWN_SIZE;
60
61
62 private RegionSizeProperties<P> regionSizeProperties;
63
64
65
66
67
68
69
70 protected AbstractRegionBSPTree(final boolean full) {
71 getRoot().setLocationValue(full ? RegionLocation.INSIDE : RegionLocation.OUTSIDE);
72 }
73
74
75 @Override
76 public boolean isEmpty() {
77 return !hasNodeWithLocationRecursive(getRoot(), RegionLocation.INSIDE);
78 }
79
80
81 @Override
82 public boolean isFull() {
83 return !hasNodeWithLocationRecursive(getRoot(), RegionLocation.OUTSIDE);
84 }
85
86
87
88
89
90
91
92 private boolean hasNodeWithLocationRecursive(final AbstractRegionNode<P, N> node, final RegionLocation location) {
93 if (node == null) {
94 return false;
95 }
96
97 return node.getLocation() == location ||
98 hasNodeWithLocationRecursive(node.getMinus(), location) ||
99 hasNodeWithLocationRecursive(node.getPlus(), location);
100 }
101
102
103
104
105 public void setFull() {
106 final N root = getRoot();
107
108 root.clearCut();
109 root.setLocationValue(RegionLocation.INSIDE);
110 }
111
112
113
114
115 public void setEmpty() {
116 final N root = getRoot();
117
118 root.clearCut();
119 root.setLocationValue(RegionLocation.OUTSIDE);
120 }
121
122
123 @Override
124 public double getSize() {
125 return getRegionSizeProperties().getSize();
126 }
127
128
129 @Override
130 public double getBoundarySize() {
131 if (boundarySize < 0) {
132 double sum = 0.0;
133
134 RegionCutBoundary<P> boundary;
135 for (final AbstractRegionNode<P, N> node : nodes()) {
136 boundary = node.getCutBoundary();
137 if (boundary != null) {
138 sum += boundary.getSize();
139 }
140 }
141
142 boundarySize = sum;
143 }
144
145 return boundarySize;
146 }
147
148
149
150
151
152 public void insert(final HyperplaneSubset<P> sub) {
153 insert(sub, DEFAULT_REGION_CUT_RULE);
154 }
155
156
157
158
159
160 public void insert(final HyperplaneSubset<P> sub, final RegionCutRule cutRule) {
161 insert(sub.toConvex(), cutRule);
162 }
163
164
165
166
167
168 public void insert(final HyperplaneConvexSubset<P> convexSub) {
169 insert(convexSub, DEFAULT_REGION_CUT_RULE);
170 }
171
172
173
174
175
176 public void insert(final HyperplaneConvexSubset<P> convexSub, final RegionCutRule cutRule) {
177 insert(convexSub, getSubtreeInitializer(cutRule));
178 }
179
180
181
182
183
184
185 public void insert(final Iterable<? extends HyperplaneConvexSubset<P>> convexSubs) {
186 insert(convexSubs, DEFAULT_REGION_CUT_RULE);
187 }
188
189
190
191
192
193
194 public void insert(final Iterable<? extends HyperplaneConvexSubset<P>> convexSubs, final RegionCutRule cutRule) {
195 for (final HyperplaneConvexSubset<P> convexSub : convexSubs) {
196 insert(convexSub, cutRule);
197 }
198 }
199
200
201
202
203
204
205 public void insert(final BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc) {
206 insert(boundarySrc, DEFAULT_REGION_CUT_RULE);
207 }
208
209
210
211
212
213
214 public void insert(final BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc,
215 final RegionCutRule cutRule) {
216 try (Stream<? extends HyperplaneConvexSubset<P>> stream = boundarySrc.boundaryStream()) {
217 stream.forEach(c -> insert(c, cutRule));
218 }
219 }
220
221
222
223
224
225 protected SubtreeInitializer<N> getSubtreeInitializer(final RegionCutRule cutRule) {
226 switch (cutRule) {
227 case INHERIT:
228 return root -> {
229 final RegionLocation rootLoc = root.getLocation();
230
231 root.getMinus().setLocationValue(rootLoc);
232 root.getPlus().setLocationValue(rootLoc);
233 };
234 case PLUS_INSIDE:
235 return root -> {
236 root.getMinus().setLocationValue(RegionLocation.OUTSIDE);
237 root.getPlus().setLocationValue(RegionLocation.INSIDE);
238 };
239 default:
240 return root -> {
241 root.getMinus().setLocationValue(RegionLocation.INSIDE);
242 root.getPlus().setLocationValue(RegionLocation.OUTSIDE);
243 };
244 }
245 }
246
247
248
249
250
251
252
253
254 public Iterable<? extends HyperplaneConvexSubset<P>> boundaries() {
255 return createBoundaryIterable(Function.identity());
256 }
257
258
259
260
261
262
263
264 protected <C extends HyperplaneConvexSubset<P>> Iterable<C> createBoundaryIterable(
265 final Function<HyperplaneConvexSubset<P>, C> typeConverter) {
266
267 return () -> new RegionBoundaryIterator<>(
268 getRoot().nodes().iterator(),
269 typeConverter);
270 }
271
272
273
274
275
276
277 public List<? extends HyperplaneConvexSubset<P>> getBoundaries() {
278 return createBoundaryList(Function.identity());
279 }
280
281
282
283
284
285
286
287 protected <C extends HyperplaneConvexSubset<P>> List<C> createBoundaryList(
288 final Function<HyperplaneConvexSubset<P>, C> typeConverter) {
289
290 final List<C> result = new ArrayList<>();
291
292 final RegionBoundaryIterator<P, C, N> it = new RegionBoundaryIterator<>(nodes().iterator(), typeConverter);
293 it.forEachRemaining(result::add);
294
295 return result;
296 }
297
298
299 @Override
300 public P project(final P pt) {
301 final BoundaryProjector<P, N> projector = new BoundaryProjector<>(pt);
302 accept(projector);
303
304 return projector.getProjected();
305 }
306
307
308 @Override
309 public P getCentroid() {
310 return getRegionSizeProperties().getCentroid();
311 }
312
313
314
315
316
317
318
319
320
321 protected <T extends AbstractRegionBSPTree<P, N>> Split<T> split(final Hyperplane<P> splitter,
322 final T minus, final T plus) {
323
324 splitIntoTrees(splitter, minus, plus);
325
326 T splitMinus = null;
327 T splitPlus = null;
328
329 if (minus != null) {
330 minus.getRoot().getPlus().setLocationValue(RegionLocation.OUTSIDE);
331 minus.condense();
332
333 splitMinus = minus.isEmpty() ? null : minus;
334 }
335 if (plus != null) {
336 plus.getRoot().getMinus().setLocationValue(RegionLocation.OUTSIDE);
337 plus.condense();
338
339 splitPlus = plus.isEmpty() ? null : plus;
340 }
341
342 return new Split<>(splitMinus, splitPlus);
343 }
344
345
346
347
348
349 protected RegionSizeProperties<P> getRegionSizeProperties() {
350 if (regionSizeProperties == null) {
351 regionSizeProperties = computeRegionSizeProperties();
352 }
353
354 return regionSizeProperties;
355 }
356
357
358
359
360 protected abstract RegionSizeProperties<P> computeRegionSizeProperties();
361
362
363
364
365
366
367 @Override
368 public RegionLocation classify(final P point) {
369 if (point.isNaN()) {
370 return RegionLocation.OUTSIDE;
371 }
372
373 return classifyRecursive(getRoot(), point);
374 }
375
376
377
378
379
380
381
382 private RegionLocation classifyRecursive(final AbstractRegionNode<P, N> node, final P point) {
383 if (node.isLeaf()) {
384
385 return node.getLocation();
386 } else {
387 final HyperplaneLocation cutLoc = node.getCutHyperplane().classify(point);
388
389 if (cutLoc == HyperplaneLocation.MINUS) {
390 return classifyRecursive(node.getMinus(), point);
391 } else if (cutLoc == HyperplaneLocation.PLUS) {
392 return classifyRecursive(node.getPlus(), point);
393 } else {
394
395
396 final RegionLocation minusLoc = classifyRecursive(node.getMinus(), point);
397 final RegionLocation plusLoc = classifyRecursive(node.getPlus(), point);
398
399 if (minusLoc == plusLoc) {
400 return minusLoc;
401 }
402 return RegionLocation.BOUNDARY;
403 }
404 }
405 }
406
407
408
409
410 public void complement() {
411 complementRecursive(getRoot());
412 }
413
414
415
416
417
418 public void complement(final AbstractRegionBSPTree<P, N> tree) {
419 copySubtree(tree.getRoot(), getRoot());
420 complementRecursive(getRoot());
421 }
422
423
424
425
426 private void complementRecursive(final AbstractRegionNode<P, N> node) {
427 if (node != null) {
428 final RegionLocation newLoc = (node.getLocation() == RegionLocation.INSIDE) ?
429 RegionLocation.OUTSIDE :
430 RegionLocation.INSIDE;
431
432 node.setLocationValue(newLoc);
433
434 complementRecursive(node.getMinus());
435 complementRecursive(node.getPlus());
436 }
437 }
438
439
440
441
442
443 public void union(final AbstractRegionBSPTree<P, N> other) {
444 new UnionOperator<P, N>().apply(this, other, this);
445 }
446
447
448
449
450
451
452 public void union(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
453 new UnionOperator<P, N>().apply(a, b, this);
454 }
455
456
457
458
459
460 public void intersection(final AbstractRegionBSPTree<P, N> other) {
461 new IntersectionOperator<P, N>().apply(this, other, this);
462 }
463
464
465
466
467
468
469 public void intersection(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
470 new IntersectionOperator<P, N>().apply(a, b, this);
471 }
472
473
474
475
476
477 public void difference(final AbstractRegionBSPTree<P, N> other) {
478 new DifferenceOperator<P, N>().apply(this, other, this);
479 }
480
481
482
483
484
485
486 public void difference(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
487 new DifferenceOperator<P, N>().apply(a, b, this);
488 }
489
490
491
492
493
494 public void xor(final AbstractRegionBSPTree<P, N> other) {
495 new XorOperator<P, N>().apply(this, other, this);
496 }
497
498
499
500
501
502
503 public void xor(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
504 new XorOperator<P, N>().apply(a, b, this);
505 }
506
507
508
509
510
511
512
513
514
515
516
517
518
519 public boolean condense() {
520 return new Condenser<P, N>().condense(getRoot());
521 }
522
523
524 @Override
525 protected void copyNodeProperties(final N src, final N dst) {
526 dst.setLocationValue(src.getLocation());
527 }
528
529
530 @Override
531 protected void invalidate() {
532 super.invalidate();
533
534
535 boundarySize = UNKNOWN_SIZE;
536 regionSizeProperties = null;
537 }
538
539
540
541
542
543 public abstract static class AbstractRegionNode<P extends Point<P>, N extends AbstractRegionNode<P, N>>
544 extends AbstractBSPTree.AbstractNode<P, N> {
545
546 private RegionLocation location;
547
548
549
550
551 private RegionCutBoundary<P> cutBoundary;
552
553
554
555
556 protected AbstractRegionNode(final AbstractBSPTree<P, N> tree) {
557 super(tree);
558 }
559
560
561 @Override
562 public AbstractRegionBSPTree<P, N> getTree() {
563
564 return (AbstractRegionBSPTree<P, N>) super.getTree();
565 }
566
567
568
569
570
571
572
573 public RegionLocation getLocation() {
574 return location;
575 }
576
577
578
579
580
581
582
583
584
585
586
587
588 public void setLocation(final RegionLocation location) {
589 if (location != RegionLocation.INSIDE && location != RegionLocation.OUTSIDE) {
590 throw new IllegalArgumentException("Invalid node location: " + location);
591 }
592 if (this.location != location) {
593 this.location = location;
594
595 getTree().invalidate();
596 }
597 }
598
599
600
601
602
603 public boolean isInside() {
604 return isLeaf() && getLocation() == RegionLocation.INSIDE;
605 }
606
607
608
609
610
611 public boolean isOutside() {
612 return isLeaf() && getLocation() == RegionLocation.OUTSIDE;
613 }
614
615
616
617
618
619
620
621
622 public boolean insertCut(final Hyperplane<P> cutter) {
623 return insertCut(cutter, DEFAULT_REGION_CUT_RULE);
624 }
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639 public boolean insertCut(final Hyperplane<P> cutter, final RegionCutRule cutRule) {
640 final AbstractRegionBSPTree<P, N> tree = getTree();
641 return tree.cutNode(getSelf(), cutter, tree.getSubtreeInitializer(cutRule));
642 }
643
644
645
646
647 public boolean clearCut() {
648 return getTree().removeNodeCut(getSelf());
649 }
650
651
652
653
654
655
656
657
658 public N cut(final Hyperplane<P> cutter) {
659 return cut(cutter, DEFAULT_REGION_CUT_RULE);
660 }
661
662
663
664
665
666
667
668
669
670
671
672 public N cut(final Hyperplane<P> cutter, final RegionCutRule cutRule) {
673 this.insertCut(cutter, cutRule);
674
675 return getSelf();
676 }
677
678
679
680
681
682 public RegionCutBoundary<P> getCutBoundary() {
683 if (!isLeaf()) {
684 checkValid();
685
686 if (cutBoundary == null) {
687 cutBoundary = computeBoundary();
688 }
689 }
690
691 return cutBoundary;
692 }
693
694
695
696
697
698 private RegionCutBoundary<P> computeBoundary() {
699 final HyperplaneConvexSubset<P> sub = getCut();
700
701
702
703 final List<HyperplaneConvexSubset<P>> minusIn = new ArrayList<>();
704 final List<HyperplaneConvexSubset<P>> minusOut = new ArrayList<>();
705
706 characterizeHyperplaneSubset(sub, getMinus(), minusIn, minusOut);
707
708 final ArrayList<HyperplaneConvexSubset<P>> insideFacing = new ArrayList<>();
709 final ArrayList<HyperplaneConvexSubset<P>> outsideFacing = new ArrayList<>();
710
711 if (!minusIn.isEmpty()) {
712
713
714
715 for (final HyperplaneConvexSubset<P> minusInFragment : minusIn) {
716 characterizeHyperplaneSubset(minusInFragment, getPlus(), null, outsideFacing);
717 }
718 }
719
720 if (!minusOut.isEmpty()) {
721
722
723
724 for (final HyperplaneConvexSubset<P> minusOutFragment : minusOut) {
725 characterizeHyperplaneSubset(minusOutFragment, getPlus(), insideFacing, null);
726 }
727 }
728
729 insideFacing.trimToSize();
730 outsideFacing.trimToSize();
731
732 return new RegionCutBoundary<>(
733 insideFacing.isEmpty() ? null : insideFacing,
734 outsideFacing.isEmpty() ? null : outsideFacing);
735 }
736
737
738
739
740
741
742
743
744
745
746 private void characterizeHyperplaneSubset(final HyperplaneConvexSubset<P> sub,
747 final AbstractRegionNode<P, N> node, final List<? super HyperplaneConvexSubset<P>> in,
748 final List<? super HyperplaneConvexSubset<P>> out) {
749
750 if (sub != null) {
751 if (node.isLeaf()) {
752 if (node.isInside() && in != null) {
753 in.add(sub);
754 } else if (node.isOutside() && out != null) {
755 out.add(sub);
756 }
757 } else {
758 final Split<? extends HyperplaneConvexSubset<P>> split = sub.split(node.getCutHyperplane());
759
760
761
762 if (split.getLocation() == SplitLocation.NEITHER) {
763 characterizeHyperplaneSubset(sub, node.getPlus(), in, out);
764 characterizeHyperplaneSubset(sub, node.getMinus(), in, out);
765 } else {
766 characterizeHyperplaneSubset(split.getPlus(), node.getPlus(), in, out);
767 characterizeHyperplaneSubset(split.getMinus(), node.getMinus(), in, out);
768 }
769 }
770 }
771 }
772
773
774 @Override
775 public String toString() {
776 final StringBuilder sb = new StringBuilder();
777 sb.append(this.getClass().getSimpleName())
778 .append("[cut= ")
779 .append(getCut())
780 .append(", location= ")
781 .append(getLocation())
782 .append("]");
783
784 return sb.toString();
785 }
786
787
788 @Override
789 protected void nodeInvalidated() {
790 super.nodeInvalidated();
791
792
793 cutBoundary = null;
794 }
795
796
797
798
799
800
801 protected void setLocationValue(final RegionLocation locationValue) {
802 this.location = locationValue;
803 }
804 }
805
806
807
808
809
810 protected static class BoundaryProjector<P extends Point<P>, N extends AbstractRegionNode<P, N>>
811 extends ClosestFirstVisitor<P, N> {
812
813 private P projected;
814
815
816 private double minDist = -1.0;
817
818
819
820
821 public BoundaryProjector(final P point) {
822 super(point);
823 }
824
825
826 @Override
827 public Result visit(final N node) {
828 final P point = getTarget();
829
830 if (node.isInternal() && (minDist < 0.0 || isPossibleClosestCut(node.getCut(), point, minDist))) {
831 final RegionCutBoundary<P> boundary = node.getCutBoundary();
832 final P boundaryPt = boundary.closest(point);
833
834 final double dist = boundaryPt.distance(point);
835 final int cmp = Double.compare(dist, minDist);
836
837 if (minDist < 0.0 || cmp < 0) {
838 projected = boundaryPt;
839 minDist = dist;
840 } else if (cmp == 0) {
841
842
843 projected = disambiguateClosestPoint(point, projected, boundaryPt);
844 }
845 }
846
847 return Result.CONTINUE;
848 }
849
850
851
852
853
854
855
856
857
858
859 protected boolean isPossibleClosestCut(final HyperplaneSubset<P> cut, final P target,
860 final double currentMinDist) {
861 return Math.abs(cut.getHyperplane().offset(target)) <= currentMinDist;
862 }
863
864
865
866
867
868
869
870
871
872 protected P disambiguateClosestPoint(final P target, final P a, final P b) {
873 return a;
874 }
875
876
877
878
879 public P getProjected() {
880 return projected;
881 }
882 }
883
884
885
886
887
888
889 protected static class RegionSizeProperties<P extends Point<P>> {
890
891 private final double size;
892
893
894 private final P centroid;
895
896
897
898
899
900 public RegionSizeProperties(final double size, final P centroid) {
901 this.size = size;
902 this.centroid = centroid;
903 }
904
905
906
907
908 public double getSize() {
909 return size;
910 }
911
912
913
914
915 public P getCentroid() {
916 return centroid;
917 }
918 }
919
920
921
922
923
924 private abstract static class RegionMergeOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
925 extends AbstractBSPTreeMergeOperator<P, N> {
926
927
928
929
930
931
932
933
934 public void apply(final AbstractRegionBSPTree<P, N> inputTree1, final AbstractRegionBSPTree<P, N> inputTree2,
935 final AbstractRegionBSPTree<P, N> outputTree) {
936
937 this.performMerge(inputTree1, inputTree2, outputTree);
938
939 outputTree.condense();
940 }
941 }
942
943
944
945
946
947 private static final class UnionOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
948 extends RegionMergeOperator<P, N> {
949
950
951 @Override
952 protected N mergeLeaf(final N node1, final N node2) {
953 if (node1.isLeaf()) {
954 return node1.isInside() ? node1 : node2;
955 }
956
957
958 return mergeLeaf(node2, node1);
959 }
960 }
961
962
963
964
965
966 private static final class IntersectionOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
967 extends RegionMergeOperator<P, N> {
968
969
970 @Override
971 protected N mergeLeaf(final N node1, final N node2) {
972 if (node1.isLeaf()) {
973 return node1.isInside() ? node2 : node1;
974 }
975
976
977 return mergeLeaf(node2, node1);
978 }
979 }
980
981
982
983
984
985 private static final class DifferenceOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
986 extends RegionMergeOperator<P, N> {
987
988
989 @Override
990 protected N mergeLeaf(final N node1, final N node2) {
991
992
993 if (node1.isInside()) {
994
995
996 final N output = outputSubtree(node2);
997 output.getTree().complementRecursive(output);
998
999 return output;
1000 } else if (node2.isInside()) {
1001
1002 final N output = outputNode();
1003 output.setLocationValue(RegionLocation.OUTSIDE);
1004
1005 return output;
1006 }
1007
1008
1009 return node1;
1010 }
1011 }
1012
1013
1014
1015
1016
1017 private static final class XorOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
1018 extends RegionMergeOperator<P, N> {
1019
1020
1021 @Override
1022 protected N mergeLeaf(final N node1, final N node2) {
1023
1024
1025
1026 if (node1.isLeaf()) {
1027 if (node1.isInside()) {
1028
1029
1030 final N output = outputSubtree(node2);
1031 output.getTree().complementRecursive(output);
1032
1033 return output;
1034 } else {
1035
1036
1037 return node2;
1038 }
1039 }
1040
1041
1042
1043 return mergeLeaf(node2, node1);
1044 }
1045 }
1046
1047
1048
1049
1050
1051 private static final class Condenser<P extends Point<P>, N extends AbstractRegionNode<P, N>> {
1052
1053 private boolean modifiedTree;
1054
1055
1056
1057
1058
1059
1060 boolean condense(final N node) {
1061 modifiedTree = false;
1062
1063 condenseRecursive(node);
1064
1065 return modifiedTree;
1066 }
1067
1068
1069
1070
1071
1072
1073
1074 private RegionLocation condenseRecursive(final N node) {
1075 if (node.isLeaf()) {
1076 return node.getLocation();
1077 }
1078
1079 final RegionLocation minusLocation = condenseRecursive(node.getMinus());
1080 final RegionLocation plusLocation = condenseRecursive(node.getPlus());
1081
1082 if (minusLocation == plusLocation && minusLocation != null) {
1083 node.setLocationValue(minusLocation);
1084 node.clearCut();
1085
1086 modifiedTree = true;
1087
1088 return minusLocation;
1089 }
1090
1091 return null;
1092 }
1093 }
1094
1095
1096
1097
1098
1099
1100 private static final class RegionBoundaryIterator<
1101 P extends Point<P>,
1102 C extends HyperplaneConvexSubset<P>,
1103 N extends AbstractRegionNode<P, N>>
1104 extends IteratorTransform<N, C> {
1105
1106
1107 private final Function<? super HyperplaneConvexSubset<P>, C> typeConverter;
1108
1109
1110
1111
1112
1113 RegionBoundaryIterator(final Iterator<N> inputIterator,
1114 final Function<? super HyperplaneConvexSubset<P>, C> typeConverter) {
1115 super(inputIterator);
1116
1117 this.typeConverter = typeConverter;
1118 }
1119
1120
1121 @Override
1122 protected void acceptInput(final N input) {
1123 if (input.isInternal()) {
1124 final RegionCutBoundary<P> cutBoundary = input.getCutBoundary();
1125
1126 for (final HyperplaneConvexSubset<P> boundary : cutBoundary.getOutsideFacing()) {
1127 addOutput(typeConverter.apply(boundary));
1128 }
1129
1130 for (final HyperplaneConvexSubset<P> boundary : cutBoundary.getInsideFacing()) {
1131 final HyperplaneConvexSubset<P> reversed = boundary.reverse();
1132
1133 addOutput(typeConverter.apply(reversed));
1134 }
1135 }
1136 }
1137 }
1138 }