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