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