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