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