diff options
Diffstat (limited to 'src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java')
-rw-r--r-- | src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java | 190 |
1 files changed, 190 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java b/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java new file mode 100644 index 0000000..f8ec2f9 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/partitioning/Characterization.java @@ -0,0 +1,190 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math3.geometry.partitioning; + +import java.util.ArrayList; +import java.util.List; + +import org.apache.commons.math3.exception.MathInternalError; +import org.apache.commons.math3.geometry.Space; + +/** Cut sub-hyperplanes characterization with respect to inside/outside cells. + * @see BoundaryBuilder + * @param <S> Type of the space. + * @since 3.4 + */ +class Characterization<S extends Space> { + + /** Part of the cut sub-hyperplane that touch outside cells. */ + private SubHyperplane<S> outsideTouching; + + /** Part of the cut sub-hyperplane that touch inside cells. */ + private SubHyperplane<S> insideTouching; + + /** Nodes that were used to split the outside touching part. */ + private final NodesSet<S> outsideSplitters; + + /** Nodes that were used to split the outside touching part. */ + private final NodesSet<S> insideSplitters; + + /** Simple constructor. + * <p>Characterization consists in splitting the specified + * sub-hyperplane into several parts lying in inside and outside + * cells of the tree. The principle is to compute characterization + * twice for each cut sub-hyperplane in the tree, once on the plus + * node and once on the minus node. The parts that have the same flag + * (inside/inside or outside/outside) do not belong to the boundary + * while parts that have different flags (inside/outside or + * outside/inside) do belong to the boundary.</p> + * @param node current BSP tree node + * @param sub sub-hyperplane to characterize + */ + Characterization(final BSPTree<S> node, final SubHyperplane<S> sub) { + outsideTouching = null; + insideTouching = null; + outsideSplitters = new NodesSet<S>(); + insideSplitters = new NodesSet<S>(); + characterize(node, sub, new ArrayList<BSPTree<S>>()); + } + + /** Filter the parts of an hyperplane belonging to the boundary. + * <p>The filtering consist in splitting the specified + * sub-hyperplane into several parts lying in inside and outside + * cells of the tree. The principle is to call this method twice for + * each cut sub-hyperplane in the tree, once on the plus node and + * once on the minus node. The parts that have the same flag + * (inside/inside or outside/outside) do not belong to the boundary + * while parts that have different flags (inside/outside or + * outside/inside) do belong to the boundary.</p> + * @param node current BSP tree node + * @param sub sub-hyperplane to characterize + * @param splitters nodes that did split the current one + */ + private void characterize(final BSPTree<S> node, final SubHyperplane<S> sub, + final List<BSPTree<S>> splitters) { + if (node.getCut() == null) { + // we have reached a leaf node + final boolean inside = (Boolean) node.getAttribute(); + if (inside) { + addInsideTouching(sub, splitters); + } else { + addOutsideTouching(sub, splitters); + } + } else { + final Hyperplane<S> hyperplane = node.getCut().getHyperplane(); + final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane); + switch (split.getSide()) { + case PLUS: + characterize(node.getPlus(), sub, splitters); + break; + case MINUS: + characterize(node.getMinus(), sub, splitters); + break; + case BOTH: + splitters.add(node); + characterize(node.getPlus(), split.getPlus(), splitters); + characterize(node.getMinus(), split.getMinus(), splitters); + splitters.remove(splitters.size() - 1); + break; + default: + // this should not happen + throw new MathInternalError(); + } + } + } + + /** Add a part of the cut sub-hyperplane known to touch an outside cell. + * @param sub part of the cut sub-hyperplane known to touch an outside cell + * @param splitters sub-hyperplanes that did split the current one + */ + private void addOutsideTouching(final SubHyperplane<S> sub, + final List<BSPTree<S>> splitters) { + if (outsideTouching == null) { + outsideTouching = sub; + } else { + outsideTouching = outsideTouching.reunite(sub); + } + outsideSplitters.addAll(splitters); + } + + /** Add a part of the cut sub-hyperplane known to touch an inside cell. + * @param sub part of the cut sub-hyperplane known to touch an inside cell + * @param splitters sub-hyperplanes that did split the current one + */ + private void addInsideTouching(final SubHyperplane<S> sub, + final List<BSPTree<S>> splitters) { + if (insideTouching == null) { + insideTouching = sub; + } else { + insideTouching = insideTouching.reunite(sub); + } + insideSplitters.addAll(splitters); + } + + /** Check if the cut sub-hyperplane touches outside cells. + * @return true if the cut sub-hyperplane touches outside cells + */ + public boolean touchOutside() { + return outsideTouching != null && !outsideTouching.isEmpty(); + } + + /** Get all the parts of the cut sub-hyperplane known to touch outside cells. + * @return parts of the cut sub-hyperplane known to touch outside cells + * (may be null or empty) + */ + public SubHyperplane<S> outsideTouching() { + return outsideTouching; + } + + /** Get the nodes that were used to split the outside touching part. + * <p> + * Splitting nodes are internal nodes (i.e. they have a non-null + * cut sub-hyperplane). + * </p> + * @return nodes that were used to split the outside touching part + */ + public NodesSet<S> getOutsideSplitters() { + return outsideSplitters; + } + + /** Check if the cut sub-hyperplane touches inside cells. + * @return true if the cut sub-hyperplane touches inside cells + */ + public boolean touchInside() { + return insideTouching != null && !insideTouching.isEmpty(); + } + + /** Get all the parts of the cut sub-hyperplane known to touch inside cells. + * @return parts of the cut sub-hyperplane known to touch inside cells + * (may be null or empty) + */ + public SubHyperplane<S> insideTouching() { + return insideTouching; + } + + /** Get the nodes that were used to split the inside touching part. + * <p> + * Splitting nodes are internal nodes (i.e. they have a non-null + * cut sub-hyperplane). + * </p> + * @return nodes that were used to split the inside touching part + */ + public NodesSet<S> getInsideSplitters() { + return insideSplitters; + } + +} |