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 * https://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
18 /*
19 * This is not the original file distributed by the Apache Software Foundation
20 * It has been modified by the Hipparchus project
21 */
22 package org.hipparchus.geometry.partitioning;
23
24 import java.util.HashMap;
25 import java.util.Map;
26
27 import org.hipparchus.geometry.Point;
28 import org.hipparchus.geometry.Space;
29
30 /** This class implements the dimension-independent parts of {@link SubHyperplane}.
31
32 * <p>sub-hyperplanes are obtained when parts of an {@link
33 * Hyperplane hyperplane} are chopped off by other hyperplanes that
34 * intersect it. The remaining part is a convex region. Such objects
35 * appear in {@link BSPTree BSP trees} as the intersection of a cut
36 * hyperplane with the convex region which it splits, the chopping
37 * hyperplanes are the cut hyperplanes closer to the tree root.</p>
38
39 * @param <S> Type of the space.
40 * @param <P> Type of the points in space.
41 * @param <H> Type of the hyperplane.
42 * @param <I> Type of the sub-hyperplane.
43 * @param <T> Type of the sub-space.
44 * @param <Q> Type of the points in sub-space.
45 * @param <F> Type of the hyperplane.
46 * @param <J> Type of the sub-hyperplane.
47
48 */
49 public abstract class AbstractSubHyperplane<S extends Space,
50 P extends Point<S, P>,
51 H extends Hyperplane<S, P, H, I>,
52 I extends SubHyperplane<S, P, H, I>,
53 T extends Space, Q extends Point<T, Q>,
54 F extends Hyperplane<T, Q, F, J>,
55 J extends SubHyperplane<T, Q, F, J>>
56 implements SubHyperplane<S, P, H, I> {
57
58 /** Underlying hyperplane. */
59 private final H hyperplane;
60
61 /** Remaining region of the hyperplane. */
62 private final Region<T, Q, F, J> remainingRegion;
63
64 /** Build a sub-hyperplane from an hyperplane and a region.
65 * @param hyperplane underlying hyperplane
66 * @param remainingRegion remaining region of the hyperplane
67 */
68 protected AbstractSubHyperplane(final H hyperplane,
69 final Region<T, Q, F, J> remainingRegion) {
70 this.hyperplane = hyperplane;
71 this.remainingRegion = remainingRegion;
72 }
73
74 /** Build a sub-hyperplane from an hyperplane and a region.
75 * @param hyper underlying hyperplane
76 * @param remaining remaining region of the hyperplane
77 * @return a new sub-hyperplane
78 */
79 protected abstract I buildNew(H hyper, Region<T, Q, F, J> remaining);
80
81 /** {@inheritDoc} */
82 @Override
83 public I copySelf() {
84 return buildNew(hyperplane.copySelf(), remainingRegion);
85 }
86
87 /** Get the underlying hyperplane.
88 * @return underlying hyperplane
89 */
90 @Override
91 public H getHyperplane() {
92 return hyperplane;
93 }
94
95 /** Get the remaining region of the hyperplane.
96 * <p>The returned region is expressed in the canonical hyperplane
97 * frame and has the hyperplane dimension. For example a chopped
98 * hyperplane in the 3D euclidean is a 2D plane and the
99 * corresponding region is a convex 2D polygon.</p>
100 * @return remaining region of the hyperplane
101 */
102 public Region<T, Q, F, J> getRemainingRegion() {
103 return remainingRegion;
104 }
105
106 /** {@inheritDoc} */
107 @Override
108 public double getSize() {
109 return remainingRegion.getSize();
110 }
111
112 /** {@inheritDoc} */
113 @Override
114 public I reunite(final I other) {
115 @SuppressWarnings("unchecked")
116 AbstractSubHyperplane<S, P, H, I, T, Q, F, J> o = (AbstractSubHyperplane<S, P, H, I, T, Q, F, J>) other;
117 return buildNew(hyperplane,
118 new RegionFactory<T, Q, F, J>().union(remainingRegion, o.remainingRegion));
119 }
120
121 /** Apply a transform to the instance.
122 * <p>The instance must be a (D-1)-dimension sub-hyperplane with
123 * respect to the transform <em>not</em> a (D-2)-dimension
124 * sub-hyperplane the transform knows how to transform by
125 * itself. The transform will consist in transforming first the
126 * hyperplane and then the all region using the various methods
127 * provided by the transform.</p>
128 * @param transform D-dimension transform to apply
129 * @return the transformed instance
130 */
131 public I applyTransform(final Transform<S, P, H, I, T, Q, F, J> transform) {
132 final H tHyperplane = transform.apply(hyperplane);
133
134 // transform the tree, except for boundary attribute splitters
135 final Map<BSPTree<T, Q, F, J>, BSPTree<T, Q, F, J>> map = new HashMap<>();
136 final BSPTree<T, Q, F, J> tTree =
137 recurseTransform(remainingRegion.getTree(false), tHyperplane, transform, map);
138
139 // set up the boundary attributes splitters
140 for (final Map.Entry<BSPTree<T, Q, F, J>, BSPTree<T, Q, F, J>> entry : map.entrySet()) {
141 if (entry.getKey().getCut() != null) {
142 @SuppressWarnings("unchecked")
143 BoundaryAttribute<T, Q, F, J> original = (BoundaryAttribute<T, Q, F, J>) entry.getKey().getAttribute();
144 if (original != null) {
145 @SuppressWarnings("unchecked")
146 BoundaryAttribute<T, Q, F, J> transformed = (BoundaryAttribute<T, Q, F, J>) entry.getValue().getAttribute();
147 for (final BSPTree<T, Q, F, J> splitter : original.getSplitters()) {
148 transformed.getSplitters().add(map.get(splitter));
149 }
150 }
151 }
152 }
153
154 return buildNew(tHyperplane, remainingRegion.buildNew(tTree));
155
156 }
157
158 /** Recursively transform a BSP-tree from a sub-hyperplane.
159 * @param node current BSP tree node
160 * @param transformed image of the instance hyperplane by the transform
161 * @param transform transform to apply
162 * @param map transformed nodes map
163 * @return a new tree
164 */
165 private BSPTree<T, Q, F, J> recurseTransform(final BSPTree<T, Q, F, J> node,
166 final H transformed,
167 final Transform<S, P, H, I, T, Q, F, J> transform,
168 final Map<BSPTree<T, Q, F, J>, BSPTree<T, Q, F, J>> map) {
169
170 final BSPTree<T, Q, F, J> transformedNode;
171 if (node.getCut() == null) {
172 transformedNode = new BSPTree<>(node.getAttribute());
173 } else {
174
175 @SuppressWarnings("unchecked")
176 BoundaryAttribute<T, Q, F, J> attribute = (BoundaryAttribute<T, Q, F, J>) node.getAttribute();
177 if (attribute != null) {
178 final J tPO = (attribute.getPlusOutside() == null) ?
179 null : transform.apply(attribute.getPlusOutside(), hyperplane, transformed);
180 final J tPI = (attribute.getPlusInside() == null) ?
181 null : transform.apply(attribute.getPlusInside(), hyperplane, transformed);
182 // we start with an empty list of splitters, it will be filled in out of recursion
183 attribute = new BoundaryAttribute<>(tPO, tPI, new NodesSet<>());
184 }
185
186 transformedNode = new BSPTree<>(transform.apply(node.getCut(), hyperplane, transformed),
187 recurseTransform(node.getPlus(), transformed, transform, map),
188 recurseTransform(node.getMinus(), transformed, transform, map),
189 attribute);
190 }
191
192 map.put(node, transformedNode);
193 return transformedNode;
194
195 }
196
197 /** {@inheritDoc} */
198 @Override
199 public abstract SplitSubHyperplane<S, P, H, I> split(H hyper);
200
201 /** {@inheritDoc} */
202 @Override
203 public boolean isEmpty() {
204 return remainingRegion.isEmpty();
205 }
206
207 }