1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 package org.hipparchus.geometry.partitioning;
23
24 import java.util.ArrayList;
25 import java.util.List;
26
27 import org.hipparchus.geometry.Point;
28 import org.hipparchus.geometry.Space;
29 import org.hipparchus.geometry.partitioning.Region.Location;
30 import org.hipparchus.util.FastMath;
31
32
33
34
35
36
37
38
39
40
41
42 class BoundaryProjector<S extends Space,
43 P extends Point<S, P>,
44 H extends Hyperplane<S, P, H, I>,
45 I extends SubHyperplane<S, P, H, I>,
46 T extends Space,
47 Q extends Point<T, Q>,
48 F extends Hyperplane<T, Q, F, J>,
49 J extends SubHyperplane<T, Q, F, J>>
50 implements BSPTreeVisitor<S, P, H, I> {
51
52
53 private final P original;
54
55
56 private P projected;
57
58
59 private BSPTree<S, P, H, I> leaf;
60
61
62 private double offset;
63
64
65
66
67 BoundaryProjector(final P original) {
68 this.original = original;
69 this.projected = null;
70 this.leaf = null;
71 this.offset = Double.POSITIVE_INFINITY;
72 }
73
74
75 @Override
76 public Order visitOrder(final BSPTree<S, P, H, I> node) {
77
78
79 if (node.getCut().getHyperplane().getOffset(original) <= 0) {
80 return Order.MINUS_SUB_PLUS;
81 } else {
82 return Order.PLUS_SUB_MINUS;
83 }
84 }
85
86
87 @Override
88 public void visitInternalNode(final BSPTree<S, P, H, I> node) {
89
90
91 final H hyperplane = node.getCut().getHyperplane();
92 final double signedOffset = hyperplane.getOffset(original);
93 if (FastMath.abs(signedOffset) < offset) {
94
95
96 final P regular = hyperplane.project(original);
97
98
99 final List<Region<T, Q, F, J>> boundaryParts = boundaryRegions(node);
100
101
102 boolean regularFound = false;
103 for (final Region<T, Q, F, J> part : boundaryParts) {
104 if (!regularFound && belongsToPart(regular, hyperplane, part)) {
105
106 projected = regular;
107 offset = FastMath.abs(signedOffset);
108 regularFound = true;
109 }
110 }
111
112 if (!regularFound) {
113
114
115
116 for (final Region<T, Q, F, J> part : boundaryParts) {
117 final P spI = singularProjection(regular, hyperplane, part);
118 if (spI != null) {
119 final double distance = original.distance(spI);
120 if (distance < offset) {
121 projected = spI;
122 offset = distance;
123 }
124 }
125 }
126
127 }
128
129 }
130
131 }
132
133
134 @Override
135 public void visitLeafNode(final BSPTree<S, P, H, I> node) {
136 if (leaf == null) {
137
138
139 leaf = node;
140 }
141 }
142
143
144
145
146 public BoundaryProjection<S, P> getProjection() {
147
148
149 offset = FastMath.copySign(offset, (Boolean) leaf.getAttribute() ? -1 : +1);
150
151 return new BoundaryProjection<>(original, projected, offset);
152
153 }
154
155
156
157
158
159 private List<Region<T, Q, F, J>> boundaryRegions(final BSPTree<S, P, H, I> node) {
160
161 final List<Region<T, Q, F, J>> regions = new ArrayList<>(2);
162
163 @SuppressWarnings("unchecked")
164 final BoundaryAttribute<S, P, H, I> ba = (BoundaryAttribute<S, P, H, I>) node.getAttribute();
165 addRegion(ba.getPlusInside(), regions);
166 addRegion(ba.getPlusOutside(), regions);
167
168 return regions;
169
170 }
171
172
173
174
175
176 private void addRegion(final SubHyperplane<S, P, H, I> sub, final List<Region<T, Q, F, J>> list) {
177 if (sub != null) {
178 final Region<T, Q, F, J> region = ((AbstractSubHyperplane<S, P, H, I, T, Q, F, J>) sub).getRemainingRegion();
179 if (region != null) {
180 list.add(region);
181 }
182 }
183 }
184
185
186
187
188
189
190
191 private boolean belongsToPart(final P point, final Hyperplane<S, P, H, I> hyperplane,
192 final Region<T, Q, F, J> part) {
193
194
195 @SuppressWarnings("unchecked")
196 final Embedding<S, P, T, Q> embedding = (Embedding<S, P, T, Q>) hyperplane;
197 return part.checkPoint(embedding.toSubSpace(point)) != Location.OUTSIDE;
198
199 }
200
201
202
203
204
205
206
207 private P singularProjection(final P point, final Hyperplane<S, P, H, I> hyperplane,
208 final Region<T, Q, F, J> part) {
209
210
211 @SuppressWarnings("unchecked")
212 final Embedding<S, P, T, Q> embedding = (Embedding<S, P, T, Q>) hyperplane;
213 final BoundaryProjection<T, Q> bp = part.projectToBoundary(embedding.toSubSpace(point));
214
215
216 return (bp.getProjected() == null) ? null : embedding.toSpace(bp.getProjected());
217
218 }
219
220 }