View Javadoc

    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.geometry.euclidean.twod;
    18
    19  import java.util.ArrayList;
    20  import java.util.Collections;
    21  import java.util.List;
    22  import java.util.stream.Collectors;
    23  import java.util.stream.Stream;
    24  import java.util.stream.StreamSupport;
    25
    26  import org.apache.commons.geometry.core.partitioning.Hyperplane;
    27  import org.apache.commons.geometry.core.partitioning.Split;
    28  import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
    29  import org.apache.commons.geometry.core.partitioning.bsp.AbstractPartitionedRegionBuilder;
    30  import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree;
    31  import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor;
    32  import org.apache.commons.geometry.core.partitioning.bsp.RegionCutBoundary;
    33  import org.apache.commons.geometry.euclidean.twod.path.InteriorAngleLinePathConnector;
    34  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
    35  import org.apache.commons.numbers.core.Precision;
    36
    37  /** Binary space partitioning (BSP) tree representing a region in two dimensional
    38   * Euclidean space.
    39   */
    40  public final class RegionBSPTree2D extends AbstractRegionBSPTree<Vector2D, RegionBSPTree2D.RegionNode2D>
    41      implements BoundarySource2D {
    42
    43      /** List of line subset paths comprising the region boundary. */
    44      private List<LinePath> boundaryPaths;
    45
    46      /** Create a new, empty region.
    47       */
    48      public RegionBSPTree2D() {
    49          this(false);
    50      }
    51
    52      /** Create a new region. If {@code full} is true, then the region will
    53       * represent the entire 2D space. Otherwise, it will be empty.
    54       * @param full whether or not the region should contain the entire
    55       *      2D space or be empty
    56       */
    57      public RegionBSPTree2D(final boolean full) {
    58          super(full);
    59      }
    60
    61      /** Return a deep copy of this instance.
    62       * @return a deep copy of this instance.
    63       * @see #copy(org.apache.commons.geometry.core.partitioning.bsp.BSPTree)
    64       */
    65      public RegionBSPTree2D copy() {
    66          final RegionBSPTree2D result = RegionBSPTree2D.empty();
    67          result.copy(this);
    68
    69          return result;
    70      }
    71
    72      /** {@inheritDoc} */
    73      @Override
    74      public Iterable<LineConvexSubset> boundaries() {
    75          return createBoundaryIterable(LineConvexSubset.class::cast);
    76      }
    77
    78      /** {@inheritDoc} */
    79      @Override
    80      public Stream<LineConvexSubset> boundaryStream() {
    81          return StreamSupport.stream(boundaries().spliterator(), false);
    82      }
    83
    84      /** {@inheritDoc} */
    85      @Override
    86      public List<LineConvexSubset> getBoundaries() {
    87          return createBoundaryList(LineConvexSubset.class::cast);
    88      }
    89
    90      /** Get the boundary of the region as a list of connected line subset paths.
    91       * The line subset are oriented such that their minus (left) side lies on the
    92       * interior of the region.
    93       * @return line subset paths representing the region boundary
    94       */
    95      public List<LinePath> getBoundaryPaths() {
    96          if (boundaryPaths == null) {
    97              boundaryPaths = Collections.unmodifiableList(computeBoundaryPaths());
    98          }
    99          return boundaryPaths;
    100     }
    101
    102     /** Add a convex area to this region. The resulting region will be the
    103      * union of the convex area and the region represented by this instance.
    104      * @param area the convex area to add
    105      */
    106     public void add(final ConvexArea area) {
    107         union(area.toTree());
    108     }
    109
    110     /** Return a list of {@link ConvexArea}s representing the same region
    111      * as this instance. One convex area is returned for each interior leaf
    112      * node in the tree.
    113      * @return a list of convex areas representing the same region as this
    114      *      instance
    115      */
    116     public List<ConvexArea> toConvex() {
    117         final List<ConvexArea> result = new ArrayList<>();
    118
    119         toConvexRecursive(getRoot(), ConvexArea.full(), result);
    120
    121         return result;
    122     }
    123
    124     /** Recursive method to compute the convex areas of all inside leaf nodes in the subtree rooted at the given
    125      * node. The computed convex areas are added to the given list.
    126      * @param node root of the subtree to compute the convex areas for
    127      * @param nodeArea the convex area for the current node; this will be split by the node's cut hyperplane to
    128      *      form the convex areas for any child nodes
    129      * @param result list containing the results of the computation
    130      */
    131     private void toConvexRecursive(final RegionNode2D node, final ConvexArea nodeArea,
    132             final List<? super ConvexArea> result) {
    133         if (node.isLeaf()) {
    134             // base case; only add to the result list if the node is inside
    135             if (node.isInside()) {
    136                 result.add(nodeArea);
    137             }
    138         } else {
    139             // recurse
    140             final Split<ConvexArea> split = nodeArea.split(node.getCutHyperplane());
    141
    142             toConvexRecursive(node.getMinus(), split.getMinus(), result);
    143             toConvexRecursive(node.getPlus(), split.getPlus(), result);
    144         }
    145     }
    146
    147     /** {@inheritDoc} */
    148     @Override
    149     public Split<RegionBSPTree2D> split(final Hyperplane<Vector2D> splitter) {
    150         return split(splitter, RegionBSPTree2D.empty(), RegionBSPTree2D.empty());
    151     }
    152
    153     /** {@inheritDoc} */
    154     @Override
    155     public Vector2D project(final Vector2D pt) {
    156         // use our custom projector so that we can disambiguate points that are
    157         // actually equidistant from the target point
    158         final BoundaryProjector2D projector = new BoundaryProjector2D(pt);
    159         accept(projector);
    160
    161         return projector.getProjected();
    162     }
    163
    164     /** Return the current instance.
    165      */
    166     @Override
    167     public RegionBSPTree2D toTree() {
    168         return this;
    169     }
    170
    171     /** {@inheritDoc} */
    172     @Override
    173     public List<LinecastPoint2D> linecast(final LineConvexSubset subset) {
    174         final LinecastVisitor visitor = new LinecastVisitor(subset, false);
    175         accept(visitor);
    176
    177         return visitor.getResults();
    178     }
    179
    180     /** {@inheritDoc} */
    181     @Override
    182     public LinecastPoint2D linecastFirst(final LineConvexSubset subset) {
    183         final LinecastVisitor visitor = new LinecastVisitor(subset, true);
    184         accept(visitor);
    185
    186         return visitor.getFirstResult();
    187     }
    188
    189     /** Compute the line subset paths comprising the region boundary.
    190      * @return the line subset paths comprising the region boundary
    191      */
    192     private List<LinePath> computeBoundaryPaths() {
    193         final InteriorAngleLinePathConnector connector = new InteriorAngleLinePathConnector.Minimize();
    194         connector.connect(boundaries());
    195
    196         return connector.connectAll().stream()
    197                 .map(LinePath::simplify).collect(Collectors.toList());
    198     }
    199
    200     /** {@inheritDoc} */
    201     @Override
    202     protected RegionSizeProperties<Vector2D> computeRegionSizeProperties() {
    203         // handle simple cases
    204         if (isFull()) {
    205             return new RegionSizeProperties<>(Double.POSITIVE_INFINITY, null);
    206         } else if (isEmpty()) {
    207             return new RegionSizeProperties<>(0, null);
    208         }
    209
    210         // compute the size based on the boundary line subsets
    211         double quadrilateralAreaSum = 0.0;
    212
    213         double scaledSumX = 0.0;
    214         double scaledSumY = 0.0;
    215
    216         Vector2D startPoint;
    217         Vector2D endPoint;
    218         double signedArea;
    219
    220         for (final LineConvexSubset boundary : boundaries()) {
    221
    222             if (boundary.isInfinite()) {
    223                 // at least on boundary is infinite, meaning that
    224                 // the size is also infinite
    225                 quadrilateralAreaSum = Double.POSITIVE_INFINITY;
    226
    227                 break;
    228             }
    229
    230             startPoint = boundary.getStartPoint();
    231             endPoint = boundary.getEndPoint();
    232
    233             // compute the area
    234             signedArea = startPoint.signedArea(endPoint);
    235
    236             quadrilateralAreaSum += signedArea;
    237
    238             // compute scaled coordinate values for the centroid
    239             scaledSumX += signedArea * (startPoint.getX() + endPoint.getX());
    240             scaledSumY += signedArea * (startPoint.getY() + endPoint.getY());
    241         }
    242
    243         double size = Double.POSITIVE_INFINITY;
    244         Vector2D centroid = null;
    245
    246         // The area is finite only if the computed quadrilateral area is finite and non-negative.
    247         // Negative areas indicate that the region is inside-out, with a finite outside surrounded
    248         // by an infinite inside.
    249         if (quadrilateralAreaSum >= 0 && Double.isFinite(quadrilateralAreaSum)) {
    250             size = 0.5 * quadrilateralAreaSum;
    251
    252             if (quadrilateralAreaSum > 0) {
    253                 centroid = Vector2D.of(scaledSumX, scaledSumY).multiply(1.0 / (3.0 * quadrilateralAreaSum));
    254             }
    255         }
    256
    257         return new RegionSizeProperties<>(size, centroid);
    258     }
    259
    260     /** {@inheritDoc} */
    261     @Override
    262     protected void invalidate() {
    263         super.invalidate();
    264
    265         boundaryPaths = null;
    266     }
    267
    268     /** {@inheritDoc} */
    269     @Override
    270     protected RegionNode2D createNode() {
    271         return new RegionNode2D(this);
    272     }
    273
    274     /** Return a new {@link RegionBSPTree2D} instance containing the entire space.
    275      * @return a new {@link RegionBSPTree2D} instance containing the entire space
    276      */
    277     public static RegionBSPTree2D full() {
    278         return new RegionBSPTree2D(true);
    279     }
    280
    281     /** Return a new, empty {@link RegionBSPTree2D} instance.
    282      * @return a new, empty {@link RegionBSPTree2D} instance
    283      */
    284     public static RegionBSPTree2D empty() {
    285         return new RegionBSPTree2D(false);
    286     }
    287
    288     /** Construct a new tree from the given boundaries. If no boundaries
    289      * are present, the returned tree is empty.
    290      * @param boundaries boundaries to construct the tree from
    291      * @return a new tree instance constructed from the given boundaries
    292      * @see #from(Iterable, boolean)
    293      */
    294     public static RegionBSPTree2D from(final Iterable<? extends LineConvexSubset> boundaries) {
    295         return from(boundaries, false);
    296     }
    297
    298     /** Construct a new tree from the given boundaries. If {@code full} is true, then
    299      * the initial tree before boundary insertion contains the entire space. Otherwise,
    300      * it is empty.
    301      * @param boundaries boundaries to construct the tree from
    302      * @param full if true, the initial tree will contain the entire space
    303      * @return a new tree instance constructed from the given boundaries
    304      */
    305     public static RegionBSPTree2D from(final Iterable<? extends LineConvexSubset> boundaries, final boolean full) {
    306         final RegionBSPTree2D tree = new RegionBSPTree2D(full);
    307         tree.insert(boundaries);
    308
    309         return tree;
    310     }
    311
    312     /** Create a new {@link PartitionedRegionBuilder2D} instance which can be used to build balanced
    313      * BSP trees from region boundaries.
    314      * @return a new {@link PartitionedRegionBuilder2D} instance
    315      */
    316     public static PartitionedRegionBuilder2D partitionedRegionBuilder() {
    317         return new PartitionedRegionBuilder2D();
    318     }
    319
    320     /** BSP tree node for two dimensional Euclidean space.
    321      */
    322     public static final class RegionNode2D extends AbstractRegionBSPTree.AbstractRegionNode<Vector2D, RegionNode2D> {
    323         /** Simple constructor.
    324          * @param tree the owning tree instance
    325          */
    326         private RegionNode2D(final AbstractBSPTree<Vector2D, RegionNode2D> tree) {
    327             super(tree);
    328         }
    329
    330         /** Get the region represented by this node. The returned region contains
    331          * the entire area contained in this node, regardless of the attributes of
    332          * any child nodes.
    333          * @return the region represented by this node
    334          */
    335         public ConvexArea getNodeRegion() {
    336             ConvexArea area = ConvexArea.full();
    337
    338             RegionNode2D child = this;
    339             RegionNode2D parent;
    340
    341             while ((parent = child.getParent()) != null) {
    342                 final Split<ConvexArea> split = area.split(parent.getCutHyperplane());
    343
    344                 area = child.isMinus() ? split.getMinus() : split.getPlus();
    345
    346                 child = parent;
    347             }
    348
    349             return area;
    350         }
    351
    352         /** {@inheritDoc} */
    353         @Override
    354         protected RegionNode2D getSelf() {
    355             return this;
    356         }
    357     }
    358
    359     /** Class used to build regions in Euclidean 2D space by inserting boundaries into a BSP
    360      * tree containing "partitions", i.e. structural cuts where both sides of the cut have the same region location.
    361      * When partitions are chosen that effectively divide the region boundaries at each partition level, the
    362      * constructed tree is shallower and more balanced than one constructed from the region boundaries alone,
    363      * resulting in improved performance. For example, consider a line segment approximation of a circle. The region is
    364      * convex so each boundary has all of the other boundaries on its minus side; the plus sides are all empty.
    365      * When these boundaries are inserted directly into a tree, the tree degenerates into a simple linked list of
    366      * nodes with a height directly proportional to the number of boundaries. This means that many operations on the
    367      * tree, such as inside/outside testing of points, involve iterating through each and every region boundary. In
    368      * contrast, if a partition is first inserted that passes through the circle center, the first BSP tree node
    369      * contains region nodes on its plus <em>and</em> minus sides, cutting the height of the tree in half. Operations
    370      * such as inside/outside testing are then able to skip half of the tree nodes with a single test on the
    371      * root node, resulting in drastically improved performance. Insertion of additional partitions (using a grid
    372      * layout, for example) can produce even shallower trees, although there is a point unique to each boundary set at
    373      * which the addition of more partitions begins to decrease instead of increase performance.
    374      *
    375      * <h2>Usage</h2>
    376      * <p>Usage of this class consists of two phases: (1) <em>partition insertion</em> and (2) <em>boundary
    377      * insertion</em>. Instances begin in the <em>partition insertion</em> phase. Here, partitions can be inserted
    378      * into the empty tree using {@link PartitionedRegionBuilder2D#insertPartition(LineConvexSubset) insertPartition}
    379      * or similar methods. The {@link org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule#INHERIT INHERIT}
    380      * cut rule is used internally to insert the cut so the represented region remains empty even as partitions are
    381      * inserted.
    382      * </p>
    383      *
    384      * <p>The instance moves into the <em>boundary insertion</em> phase when the caller inserts the first region
    385      * boundary, using {@link PartitionedRegionBuilder2D#insertBoundary(LineConvexSubset) insertBoundary} or
    386      * similar methods. Attempting to insert a partition after this point results in an {@code IllegalStateException}.
    387      * This ensures that partitioning cuts are always located higher up the tree than boundary cuts.</p>
    388      *
    389      * <p>After all boundaries are inserted, the {@link PartitionedRegionBuilder2D#build() build} method is used
    390      * to perform final processing and return the computed tree.</p>
    391      */
    392     public static final class PartitionedRegionBuilder2D
    393         extends AbstractPartitionedRegionBuilder<Vector2D, RegionNode2D> {
    394
    395         /** Construct a new builder instance.
    396          */
    397         private PartitionedRegionBuilder2D() {
    398             super(RegionBSPTree2D.empty());
    399         }
    400
    401         /** Insert a partition line.
    402          * @param partition partition to insert
    403          * @return this instance
    404          * @throws IllegalStateException if a boundary has previously been inserted
    405          */
    406         public PartitionedRegionBuilder2D insertPartition(final Line partition) {
    407             return insertPartition(partition.span());
    408         }
    409
    410         /** Insert a line convex subset as a partition.
    411          * @param partition partition to insert
    412          * @return this instance
    413          * @throws IllegalStateException if a boundary has previously been inserted
    414          */
    415         public PartitionedRegionBuilder2D insertPartition(final LineConvexSubset partition) {
    416             insertPartitionInternal(partition);
    417
    418             return this;
    419         }
    420
    421         /** Insert two axis aligned lines intersecting at the given point as partitions.
    422          * The lines each contain the {@code center} point and have the directions {@code +x} and {@code +y}
    423          * in that order. If inserted into an empty tree, this will partition the space
    424          * into 4 sections.
    425          * @param center center point for the partitions; the inserted lines intersect at this point
    426          * @param precision precision context used to construct the lines
    427          * @return this instance
    428          * @throws IllegalStateException if a boundary has previously been inserted
    429          */
    430         public PartitionedRegionBuilder2D insertAxisAlignedPartitions(final Vector2D center,
    431                 final Precision.DoubleEquivalence precision) {
    432
    433             insertPartition(Lines.fromPointAndDirection(center, Vector2D.Unit.PLUS_X, precision));
    434             insertPartition(Lines.fromPointAndDirection(center, Vector2D.Unit.PLUS_Y, precision));
    435
    436             return this;
    437         }
    438
    439         /** Insert a grid of partitions. The partitions are constructed recursively: at each level two axis-aligned
    440          * partitioning lines are inserted using
    441          * {@link #insertAxisAlignedPartitions(Vector2D, Precision.DoubleEquivalence) insertAxisAlignedPartitions}.
    442          * The algorithm then recurses using bounding boxes from the min point to the center and from the center
    443          * point to the max. Note that this means no partitions are ever inserted directly on the boundaries of
    444          * the given bounding box. This is intentional and done to allow this method to be called directly with the
    445          * bounding box from a set of boundaries to be inserted without unnecessarily adding partitions that will
    446          * never have region boundaries on both sides.
    447          * @param bounds bounding box for the grid
    448          * @param level recursion level for the grid; each level subdivides each grid cube into 4 sections, making the
    449          *      total number of grid cubes equal to {@code 4 ^ level}
    450          * @param precision precision context used to construct the partition lines
    451          * @return this instance
    452          * @throws IllegalStateException if a boundary has previously been inserted
    453          */
    454         public PartitionedRegionBuilder2D insertAxisAlignedGrid(final Bounds2D bounds, final int level,
    455                 final Precision.DoubleEquivalence precision) {
    456
    457             insertAxisAlignedGridRecursive(bounds.getMin(), bounds.getMax(), level, precision);
    458
    459             return this;
    460         }
    461
    462         /** Recursively insert axis-aligned grid partitions.
    463          * @param min min point for the grid square to partition
    464          * @param max max point for the grid square to partition
    465          * @param level current recursion level
    466          * @param precision precision context used to construct the partition planes
    467          */
    468         private void insertAxisAlignedGridRecursive(final Vector2D min, final Vector2D max, final int level,
    469                 final Precision.DoubleEquivalence precision) {
    470             if (level > 0) {
    471                 final Vector2D center = min.lerp(max, 0.5);
    472
    473                 insertAxisAlignedPartitions(center, precision);
    474
    475                 final int nextLevel = level - 1;
    476                 insertAxisAlignedGridRecursive(min, center, nextLevel, precision);
    477                 insertAxisAlignedGridRecursive(center, max, nextLevel, precision);
    478             }
    479         }
    480
    481         /** Insert a region boundary.
    482          * @param boundary region boundary to insert
    483          * @return this instance
    484          */
    485         public PartitionedRegionBuilder2D insertBoundary(final LineConvexSubset boundary) {
    486             insertBoundaryInternal(boundary);
    487
    488             return this;
    489         }
    490
    491         /** Insert a collection of region boundaries.
    492          * @param boundaries boundaries to insert
    493          * @return this instance
    494          */
    495         public PartitionedRegionBuilder2D insertBoundaries(final Iterable<? extends LineConvexSubset> boundaries) {
    496             for (final LineConvexSubset boundary : boundaries) {
    497                 insertBoundaryInternal(boundary);
    498             }
    499
    500             return this;
    501         }
    502
    503         /** Insert all boundaries from the given source.
    504          * @param boundarySrc source of boundaries to insert
    505          * @return this instance
    506          */
    507         public PartitionedRegionBuilder2D insertBoundaries(final BoundarySource2D boundarySrc) {
    508             try (Stream<LineConvexSubset> stream = boundarySrc.boundaryStream()) {
    509                 stream.forEach(this::insertBoundaryInternal);
    510             }
    511
    512             return this;
    513         }
    514
    515         /** Build and return the region BSP tree.
    516          * @return the region BSP tree
    517          */
    518         public RegionBSPTree2D build() {
    519             return (RegionBSPTree2D) buildInternal();
    520         }
    521     }
    522
    523     /** Class used to project points onto the 2D region boundary.
    524      */
    525     private static final class BoundaryProjector2D extends BoundaryProjector<Vector2D, RegionNode2D> {
    526         /** Simple constructor.
    527          * @param point the point to project onto the region's boundary
    528          */
    529         BoundaryProjector2D(final Vector2D point) {
    530             super(point);
    531         }
    532
    533         /** {@inheritDoc} */
    534         @Override
    535         protected Vector2D disambiguateClosestPoint(final Vector2D target, final Vector2D a, final Vector2D b) {
    536             // return the point with the smallest coordinate values
    537             final int cmp = Vector2D.COORDINATE_ASCENDING_ORDER.compare(a, b);
    538             return cmp < 0 ? a : b;
    539         }
    540     }
    541
    542     /** BSP tree visitor that performs a linecast operation against the boundaries of the visited tree.
    543      */
    544     private static final class LinecastVisitor implements BSPTreeVisitor<Vector2D, RegionNode2D> {
    545
    546         /** The line subset to intersect with the boundaries of the BSP tree. */
    547         private final LineConvexSubset linecastSubset;
    548
    549         /** If true, the visitor will stop visiting the tree once the first linecast
    550          * point is determined.
    551          */
    552         private final boolean firstOnly;
    553
    554         /** The minimum abscissa found during the search. */
    555         private double minAbscissa = Double.POSITIVE_INFINITY;
    556
    557         /** List of results from the linecast operation. */
    558         private final List<LinecastPoint2D> results = new ArrayList<>();
    559
    560         /** Create a new instance with the given intersecting line subset.
    561          * @param linecastSubset line subset to intersect with the BSP tree region boundary
    562          * @param firstOnly if true, the visitor will stop visiting the tree once the first
    563          *      linecast point is determined
    564          */
    565         LinecastVisitor(final LineConvexSubset linecastSubset, final boolean firstOnly) {
    566             this.linecastSubset = linecastSubset;
    567             this.firstOnly = firstOnly;
    568         }
    569
    570         /** Get the first {@link LinecastPoint2D} resulting from the linecast operation.
    571          * @return the first linecast result point
    572          */
    573         public LinecastPoint2D getFirstResult() {
    574             final List<LinecastPoint2D> sortedResults = getResults();
    575
    576             return sortedResults.isEmpty() ?
    577                     null :
    578                     sortedResults.get(0);
    579         }
    580
    581         /** Get a list containing the results of the linecast operation. The list is
    582          * sorted and filtered.
    583          * @return list of sorted and filtered results from the linecast operation
    584          */
    585         public List<LinecastPoint2D> getResults() {
    586             LinecastPoint2D.sortAndFilter(results);
    587
    588             return results;
    589         }
    590
    591         /** {@inheritDoc} */
    592         @Override
    593         public Order visitOrder(final RegionNode2D internalNode) {
    594             final Line cut = (Line) internalNode.getCutHyperplane();
    595             final Line line = linecastSubset.getLine();
    596
    597             final boolean plusIsNear = line.getDirection().dot(cut.getOffsetDirection()) < 0;
    598
    599             return plusIsNear ?
    600                     Order.PLUS_NODE_MINUS :
    601                     Order.MINUS_NODE_PLUS;
    602         }
    603
    604         /** {@inheritDoc} */
    605         @Override
    606         public Result visit(final RegionNode2D node) {
    607             if (node.isInternal()) {
    608                 // check if the line subset intersects the node cut
    609                 final Line line = linecastSubset.getLine();
    610                 final Vector2D pt = ((Line) node.getCutHyperplane()).intersection(line);
    611
    612                 if (pt != null) {
    613                     if (firstOnly && !results.isEmpty() &&
    614                             line.getPrecision().compare(minAbscissa, line.abscissa(pt)) < 0) {
    615                         // we have results and we are now sure that no other intersection points will be
    616                         // found that are closer or at the same position on the intersecting line.
    617                         return Result.TERMINATE;
    618                     } else if (linecastSubset.contains(pt)) {
    619                         // we've potentially found a new linecast point; add it to the list of potential
    620                         // results
    621                         final LinecastPoint2D potentialResult = computeLinecastPoint(pt, node);
    622                         if (potentialResult != null) {
    623                             results.add(potentialResult);
    624
    625                             // update the min abscissa
    626                             minAbscissa = Math.min(minAbscissa, potentialResult.getAbscissa());
    627                         }
    628                     }
    629                 }
    630             }
    631
    632             return Result.CONTINUE;
    633         }
    634
    635         /** Compute the linecast point for the given intersection point and tree node, returning null
    636          * if the point does not actually lie on the region boundary.
    637          * @param pt intersection point
    638          * @param node node containing the cut that the linecast line intersected with
    639          * @return a new linecast point instance or null if the intersection point does not lie
    640          *      on the region boundary
    641          */
    642         private LinecastPoint2D computeLinecastPoint(final Vector2D pt, final RegionNode2D node) {
    643             final Line cut = (Line) node.getCutHyperplane();
    644             final RegionCutBoundary<Vector2D> boundary = node.getCutBoundary();
    645
    646             boolean onBoundary = false;
    647             boolean negateNormal = false;
    648
    649             if (boundary.containsInsideFacing(pt)) {
    650                 // on inside-facing boundary
    651                 onBoundary = true;
    652                 negateNormal = true;
    653             } else  if (boundary.containsOutsideFacing(pt)) {
    654                 // on outside-facing boundary
    655                 onBoundary = true;
    656             }
    657
    658             if (onBoundary) {
    659                 Vector2D normal = cut.getOffsetDirection();
    660                 if (negateNormal) {
    661                     normal = normal.negate();
    662                 }
    663
    664                 return new LinecastPoint2D(pt, normal, linecastSubset.getLine());
    665             }
    666
    667             return null;
    668         }
    669     }
    670 }