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 }