AbstractRegion.java

  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.  */

  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;

  24. import java.util.ArrayList;
  25. import java.util.Collection;
  26. import java.util.Comparator;
  27. import java.util.HashMap;
  28. import java.util.Iterator;
  29. import java.util.Map;
  30. import java.util.TreeSet;

  32. import org.hipparchus.geometry.Point;
  33. import org.hipparchus.geometry.Space;

  35. /** Abstract class for all regions, independently of geometry type or dimension.

  37.  * @param <S> Type of the space.
  38.  * @param <P> Type of the points in space.
  39.  * @param <H> Type of the hyperplane.
  40.  * @param <I> Type of the sub-hyperplane.
  41.  * @param <T> Type of the sub-space.
  42.  * @param <Q> Type of the points in sub-space.
  43.  * @param <F> Type of the hyperplane.
  44.  * @param <J> Type of the sub-hyperplane.

  46.  */
  47. public abstract class AbstractRegion<S extends Space,
  48.                                      P extends Point<S, P>,
  49.                                      H extends Hyperplane<S, P, H, I>,
  50.                                      I extends SubHyperplane<S, P, H, I>,
  51.                                      T extends Space, Q extends Point<T, Q>,
  52.                                      F extends Hyperplane<T, Q, F, J>,
  53.                                      J extends SubHyperplane<T, Q, F, J>>
  54.     implements Region<S, P, H, I> {

  56.     /** Inside/Outside BSP tree. */
  57.     private final BSPTree<S, P, H, I> tree;

  59.     /** Tolerance below which points are considered to belong to hyperplanes. */
  60.     private final double tolerance;

  62.     /** Size of the instance. */
  63.     private double size;

  65.     /** Barycenter. */
  66.     private P barycenter;

  68.     /** Build a region representing the whole space.
  69.      * @param tolerance tolerance below which points are considered identical.
  70.      */
  71.     protected AbstractRegion(final double tolerance) {
  72.         this.tree      = new BSPTree<>(Boolean.TRUE);
  73.         this.tolerance = tolerance;
  74.     }

  76.     /** Build a region from an inside/outside BSP tree.
  77.      * <p>The leaf nodes of the BSP tree <em>must</em> have a
  78.      * {@code Boolean} attribute representing the inside status of
  79.      * the corresponding cell (true for inside cells, false for outside
  80.      * cells). In order to avoid building too many small objects, it is
  81.      * recommended to use the predefined constants
  82.      * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The
  83.      * tree also <em>must</em> have either null internal nodes or
  84.      * internal nodes representing the boundary as specified in the
  85.      * {@link #getTree getTree} method).</p>
  86.      * @param tree inside/outside BSP tree representing the region
  87.      * @param tolerance tolerance below which points are considered identical.
  88.      */
  89.     protected AbstractRegion(final BSPTree<S, P, H, I> tree, final double tolerance) {
  90.         this.tree      = tree;
  91.         this.tolerance = tolerance;
  92.     }

  94.     /** Build a Region from a Boundary REPresentation (B-rep).
  95.      * <p>The boundary is provided as a collection of {@link
  96.      * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
  97.      * interior part of the region on its minus side and the exterior on
  98.      * its plus side.</p>
  99.      * <p>The boundary elements can be in any order, and can form
  100.      * several non-connected sets (like for example polygons with holes
  101.      * or a set of disjoints polyhedrons considered as a whole). In
  102.      * fact, the elements do not even need to be connected together
  103.      * (their topological connections are not used here). However, if the
  104.      * boundary does not really separate an inside open from an outside
  105.      * open (open having here its topological meaning), then subsequent
  106.      * calls to the {@link #checkPoint(Point) checkPoint} method will not be
  107.      * meaningful anymore.</p>
  108.      * <p>If the boundary is empty, the region will represent the whole
  109.      * space.</p>
  110.      * @param boundary collection of boundary elements, as a
  111.      * collection of {@link SubHyperplane SubHyperplane} objects
  112.      * @param tolerance tolerance below which points are considered identical.
  113.      */
  114.     protected AbstractRegion(final Collection<I> boundary, final double tolerance) {

  116.         this.tolerance = tolerance;

  118.         if (boundary.isEmpty()) {

  120.             // the tree represents the whole space
  121.             tree = new BSPTree<>(Boolean.TRUE);

  123.         } else {

  125.             // sort the boundary elements in decreasing size order
  126.             // (we don't want equal size elements to be removed, so
  127.             // we use a trick to fool the TreeSet)
  128.             final TreeSet<I> ordered = new TreeSet<>(new Comparator<I>() {
  129.                 /** {@inheritDoc} */
  130.                 @Override
  131.                 public int compare(final I o1, final I o2) {
  132.                     final double size1 = o1.getSize();
  133.                     final double size2 = o2.getSize();
  134.                     return (size2 < size1) ? -1 : ((o1 == o2) ? 0 : +1);
  135.                 }
  136.             });
  137.             ordered.addAll(boundary);

  139.             // build the tree top-down
  140.             tree = new BSPTree<>();
  141.             insertCuts(tree, ordered);

  143.             // set up the inside/outside flags
  144.             tree.visit(new BSPTreeVisitor<S, P, H, I>() {

  146.                 /** {@inheritDoc} */
  147.                 @Override
  148.                 public Order visitOrder(final BSPTree<S, P, H, I> node) {
  149.                     return Order.PLUS_SUB_MINUS;
  150.                 }

  152.                 /** {@inheritDoc} */
  153.                 @Override
  154.                 public void visitInternalNode(final BSPTree<S, P, H, I> node) {
  155.                 }

  157.                 /** {@inheritDoc} */
  158.                 @Override
  159.                 public void visitLeafNode(final BSPTree<S, P, H, I> node) {
  160.                     if (node.getParent() == null || node == node.getParent().getMinus()) {
  161.                         node.setAttribute(Boolean.TRUE);
  162.                     } else {
  163.                         node.setAttribute(Boolean.FALSE);
  164.                     }
  165.                 }
  166.             });

  168.         }

  170.     }

  172.     /** Build a convex region from an array of bounding hyperplanes.
  173.      * @param hyperplanes array of bounding hyperplanes (if null, an
  174.      * empty region will be built)
  175.      * @param tolerance tolerance below which points are considered identical.
  176.      */
  177.     public AbstractRegion(final H[] hyperplanes, final double tolerance) {
  178.         this.tolerance = tolerance;
  179.         if ((hyperplanes == null) || (hyperplanes.length == 0)) {
  180.             tree = new BSPTree<>(Boolean.FALSE);
  181.         } else {

  183.             // use the first hyperplane to build the right class
  184.             tree = hyperplanes[0].wholeSpace().getTree(false);

  186.             // chop off parts of the space
  187.             BSPTree<S, P, H, I> node = tree;
  188.             node.setAttribute(Boolean.TRUE);
  189.             for (final H hyperplane : hyperplanes) {
  190.                 if (node.insertCut(hyperplane)) {
  191.                     node.setAttribute(null);
  192.                     node.getPlus().setAttribute(Boolean.FALSE);
  193.                     node = node.getMinus();
  194.                     node.setAttribute(Boolean.TRUE);
  195.                 }
  196.             }

  198.         }

  200.     }

  202.     /** {@inheritDoc} */
  203.     @Override
  204.     public abstract AbstractRegion<S, P, H, I, T, Q, F, J> buildNew(BSPTree<S, P, H, I> newTree);

  206.     /** Get the tolerance below which points are considered to belong to hyperplanes.
  207.      * @return tolerance below which points are considered to belong to hyperplanes
  208.      */
  209.     public double getTolerance() {
  210.         return tolerance;
  211.     }

  213.     /** Recursively build a tree by inserting cut sub-hyperplanes.
  214.      * @param node current tree node (it is a leaf node at the beginning
  215.      * of the call)
  216.      * @param boundary collection of edges belonging to the cell defined
  217.      * by the node
  218.      */
  219.     private void insertCuts(final BSPTree<S, P, H, I> node, final Collection<I> boundary) {

  221.         final Iterator<I> iterator = boundary.iterator();

  223.         // build the current level
  224.         H inserted = null;
  225.         while ((inserted == null) && iterator.hasNext()) {
  226.             inserted = iterator.next().getHyperplane();
  227.             if (!node.insertCut(inserted.copySelf())) {
  228.                 inserted = null;
  229.             }
  230.         }

  232.         if (!iterator.hasNext()) {
  233.             return;
  234.         }

  236.         // distribute the remaining edges in the two sub-trees
  237.         final ArrayList<I> plusList  = new ArrayList<>();
  238.         final ArrayList<I> minusList = new ArrayList<>();
  239.         while (iterator.hasNext()) {
  240.             final I other = iterator.next();
  241.             final SubHyperplane.SplitSubHyperplane<S, P, H, I> split = other.split(inserted);
  242.             switch (split.getSide()) {
  243.             case PLUS:
  244.                 plusList.add(other);
  245.                 break;
  246.             case MINUS:
  247.                 minusList.add(other);
  248.                 break;
  249.             case BOTH:
  250.                 plusList.add(split.getPlus());
  251.                 minusList.add(split.getMinus());
  252.                 break;
  253.             default:
  254.                 // ignore the sub-hyperplanes belonging to the cut hyperplane
  255.             }
  256.         }

  258.         // recurse through lower levels
  259.         insertCuts(node.getPlus(),  plusList);
  260.         insertCuts(node.getMinus(), minusList);

  262.     }

  264.     /** {@inheritDoc} */
  265.     @Override
  266.     public AbstractRegion<S, P, H, I, T, Q, F, J> copySelf() {
  267.         return buildNew(tree.copySelf());
  268.     }

  270.     /** {@inheritDoc} */
  271.     @Override
  272.     public boolean isEmpty() {
  273.         return isEmpty(tree);
  274.     }

  276.     /** {@inheritDoc} */
  277.     @Override
  278.     public boolean isEmpty(final BSPTree<S, P, H, I> node) {

  280.         // we use a recursive function rather than the BSPTreeVisitor
  281.         // interface because we can stop visiting the tree as soon as we
  282.         // have found an inside cell

  284.         if (node.getCut() == null) {
  285.             // if we find an inside node, the region is not empty
  286.             return !((Boolean) node.getAttribute());
  287.         }

  289.         // check both sides of the sub-tree
  290.         return isEmpty(node.getMinus()) && isEmpty(node.getPlus());

  292.     }

  294.     /** {@inheritDoc} */
  295.     @Override
  296.     public boolean isFull() {
  297.         return isFull(tree);
  298.     }

  300.     /** {@inheritDoc} */
  301.     @Override
  302.     public boolean isFull(final BSPTree<S, P, H, I> node) {

  304.         // we use a recursive function rather than the BSPTreeVisitor
  305.         // interface because we can stop visiting the tree as soon as we
  306.         // have found an outside cell

  308.         if (node.getCut() == null) {
  309.             // if we find an outside node, the region does not cover full space
  310.             return (Boolean) node.getAttribute();
  311.         }

  313.         // check both sides of the sub-tree
  314.         return isFull(node.getMinus()) && isFull(node.getPlus());

  316.     }

  318.     /** {@inheritDoc} */
  319.     @Override
  320.     public boolean contains(final Region<S, P, H, I> region) {
  321.         return new RegionFactory<S, P, H, I>().difference(region, this).isEmpty();
  322.     }

  324.     /** {@inheritDoc}
  325.      */
  326.     @Override
  327.     public BoundaryProjection<S, P> projectToBoundary(final P point) {
  328.         final BoundaryProjector<S, P, H, I, T, Q, F, J> projector = new BoundaryProjector<>(point);
  329.         getTree(true).visit(projector);
  330.         return projector.getProjection();
  331.     }

  333.     /** {@inheritDoc} */
  334.     @Override
  335.     public Location checkPoint(final P point) {
  336.         return checkPoint(tree, point);
  337.     }

  339.     /** Check a point with respect to the region starting at a given node.
  340.      * @param node root node of the region
  341.      * @param point point to check
  342.      * @return a code representing the point status: either {@link
  343.      * Region.Location#INSIDE INSIDE}, {@link Region.Location#OUTSIDE
  344.      * OUTSIDE} or {@link Region.Location#BOUNDARY BOUNDARY}
  345.      */
  346.     protected Location checkPoint(final BSPTree<S, P, H, I> node, final P point) {
  347.         final BSPTree<S, P, H, I> cell = node.getCell(point, tolerance);
  348.         if (cell.getCut() == null) {
  349.             // the point is in the interior of a cell, just check the attribute
  350.             return ((Boolean) cell.getAttribute()) ? Location.INSIDE : Location.OUTSIDE;
  351.         }

  353.         // the point is on a cut-sub-hyperplane, is it on a boundary ?
  354.         final Location minusCode = checkPoint(cell.getMinus(), point);
  355.         final Location plusCode  = checkPoint(cell.getPlus(),  point);
  356.         return (minusCode == plusCode) ? minusCode : Location.BOUNDARY;

  358.     }

  360.     /** {@inheritDoc} */
  361.     @Override
  362.     public BSPTree<S, P, H, I> getTree(final boolean includeBoundaryAttributes) {
  363.         if (includeBoundaryAttributes && (tree.getCut() != null) && (tree.getAttribute() == null)) {
  364.             // compute the boundary attributes
  365.             tree.visit(new BoundaryBuilder<>());
  366.         }
  367.         return tree;
  368.     }

  370.     /** {@inheritDoc} */
  371.     @Override
  372.     public double getBoundarySize() {
  373.         final BoundarySizeVisitor<S, P, H, I> visitor = new BoundarySizeVisitor<>();
  374.         getTree(true).visit(visitor);
  375.         return visitor.getSize();
  376.     }

  378.     /** {@inheritDoc} */
  379.     @Override
  380.     public double getSize() {
  381.         if (barycenter == null) {
  382.             computeGeometricalProperties();
  383.         }
  384.         return size;
  385.     }

  387.     /** Set the size of the instance.
  388.      * @param size size of the instance
  389.      */
  390.     protected void setSize(final double size) {
  391.         this.size = size;
  392.     }

  394.     /** {@inheritDoc} */
  395.     @Override
  396.     public P getBarycenter() {
  397.         if (barycenter == null) {
  398.             computeGeometricalProperties();
  399.         }
  400.         return barycenter;
  401.     }

  403.     /** Set the barycenter of the instance.
  404.      * @param barycenter barycenter of the instance
  405.      */
  406.     protected void setBarycenter(final P barycenter) {
  407.         this.barycenter = barycenter;
  408.     }

  410.     /** Compute some geometrical properties.
  411.      * <p>The properties to compute are the barycenter and the size.</p>
  412.      */
  413.     protected abstract void computeGeometricalProperties();

  415.     /** {@inheritDoc} */
  416.     @Override
  417.     public I intersection(final I sub) {
  418.         return recurseIntersection(tree, sub);
  419.     }

  421.     /** Recursively compute the parts of a sub-hyperplane that are
  422.      * contained in the region.
  423.      * @param node current BSP tree node
  424.      * @param sub sub-hyperplane traversing the region
  425.      * @return filtered sub-hyperplane
  426.      */
  427.     private I recurseIntersection(final BSPTree<S, P, H, I> node, final I sub) {

  429.         if (node.getCut() == null) {
  430.             return (Boolean) node.getAttribute() ? sub.copySelf() : null;
  431.         }

  433.         final H hyperplane = node.getCut().getHyperplane();
  434.         final SubHyperplane.SplitSubHyperplane<S, P, H, I> split = sub.split(hyperplane);
  435.         if (split.getPlus() != null) {
  436.             if (split.getMinus() != null) {
  437.                 // both sides
  438.                 final I plus  = recurseIntersection(node.getPlus(),  split.getPlus());
  439.                 final I minus = recurseIntersection(node.getMinus(), split.getMinus());
  440.                 if (plus == null) {
  441.                     return minus;
  442.                 } else if (minus == null) {
  443.                     return plus;
  444.                 } else {
  445.                     return plus.reunite(minus);
  446.                 }
  447.             } else {
  448.                 // only on plus side
  449.                 return recurseIntersection(node.getPlus(), sub);
  450.             }
  451.         } else if (split.getMinus() != null) {
  452.             // only on minus side
  453.             return recurseIntersection(node.getMinus(), sub);
  454.         } else {
  455.             // on hyperplane
  456.             return recurseIntersection(node.getPlus(),
  457.                                        recurseIntersection(node.getMinus(), sub));
  458.         }

  460.     }

  462.     /** Transform a region.
  463.      * <p>Applying a transform to a region consist in applying the
  464.      * transform to all the hyperplanes of the underlying BSP tree and
  465.      * of the boundary (and also to the sub-hyperplanes embedded in
  466.      * these hyperplanes) and to the barycenter. The instance is not
  467.      * modified, a new instance is built.</p>
  468.      * @param transform transform to apply
  469.      * @return a new region, resulting from the application of the
  470.      * transform to the instance
  471.      */
  472.     public AbstractRegion<S, P, H, I, T, Q, F, J> applyTransform(final Transform<S, P, H, I, T, Q, F, J> transform) {

  474.         // transform the tree, except for boundary attribute splitters
  475.         final Map<BSPTree<S, P, H, I>, BSPTree<S, P, H, I>> map = new HashMap<>();
  476.         final BSPTree<S, P, H, I> transformedTree = recurseTransform(getTree(false), transform, map);

  478.         // set up the boundary attributes splitters
  479.         for (final Map.Entry<BSPTree<S, P, H, I>, BSPTree<S, P, H, I>> entry : map.entrySet()) {
  480.             if (entry.getKey().getCut() != null) {
  481.                 @SuppressWarnings("unchecked")
  482.                 BoundaryAttribute<S, P, H, I> original = (BoundaryAttribute<S, P, H, I>) entry.getKey().getAttribute();
  483.                 if (original != null) {
  484.                     @SuppressWarnings("unchecked")
  485.                     BoundaryAttribute<S, P, H, I> transformed = (BoundaryAttribute<S, P, H, I>) entry.getValue().getAttribute();
  486.                     for (final BSPTree<S, P, H, I> splitter : original.getSplitters()) {
  487.                         transformed.getSplitters().add(map.get(splitter));
  488.                     }
  489.                 }
  490.             }
  491.         }

  493.         return buildNew(transformedTree);

  495.     }

  497.     /** Recursively transform an inside/outside BSP-tree.
  498.      * @param node current BSP tree node
  499.      * @param transform transform to apply
  500.      * @param map transformed nodes map
  501.      * @return a new tree
  502.      */
  503.     @SuppressWarnings("unchecked")
  504.     private BSPTree<S, P, H, I> recurseTransform(final BSPTree<S, P, H, I> node, final Transform<S, P, H, I, T, Q, F, J> transform,
  505.                                         final Map<BSPTree<S, P, H, I>, BSPTree<S, P, H, I>> map) {

  507.         final BSPTree<S, P, H, I> transformedNode;
  508.         if (node.getCut() == null) {
  509.             transformedNode = new BSPTree<>(node.getAttribute());
  510.         } else {

  512.             final I  sub = node.getCut();
  513.             final I tSub = ((AbstractSubHyperplane<S, P, H, I, T, Q, F, J>) sub).applyTransform(transform);
  514.             BoundaryAttribute<S, P, H, I> attribute = (BoundaryAttribute<S, P, H, I>) node.getAttribute();
  515.             if (attribute != null) {
  516.                 final I tPO = (attribute.getPlusOutside() == null) ?
  517.                     null : ((AbstractSubHyperplane<S, P, H, I, T, Q, F, J>) attribute.getPlusOutside()).applyTransform(transform);
  518.                 final I tPI = (attribute.getPlusInside()  == null) ?
  519.                     null  : ((AbstractSubHyperplane<S, P, H, I, T, Q, F, J>) attribute.getPlusInside()).applyTransform(transform);
  520.                 // we start with an empty list of splitters, it will be filled in out of recursion
  521.                 attribute = new BoundaryAttribute<>(tPO, tPI, new NodesSet<>());
  522.             }

  524.             transformedNode = new BSPTree<>(tSub,
  525.                                             recurseTransform(node.getPlus(),  transform, map),
  526.                                             recurseTransform(node.getMinus(), transform, map),
  527.                                             attribute);
  528.         }

  530.         map.put(node, transformedNode);
  531.         return transformedNode;

  533.     }

  535. }
Created with JaCoCo 0.8.12.202403310830