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.shape;
    18
    19  import java.text.MessageFormat;
    20  import java.util.List;
    21  import java.util.stream.Collectors;
    22  import java.util.stream.Stream;
    23
    24  import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
    25  import org.apache.commons.geometry.euclidean.AbstractNSphere;
    26  import org.apache.commons.geometry.euclidean.twod.Line;
    27  import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
    28  import org.apache.commons.geometry.euclidean.twod.LinecastPoint2D;
    29  import org.apache.commons.geometry.euclidean.twod.Linecastable2D;
    30  import org.apache.commons.geometry.euclidean.twod.Lines;
    31  import org.apache.commons.geometry.euclidean.twod.PolarCoordinates;
    32  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
    33  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    34  import org.apache.commons.numbers.angle.Angle;
    35  import org.apache.commons.numbers.core.Precision;
    36
    37  /** Class representing a circle in 2 dimensional Euclidean space.
    38   */
    39  public final class Circle extends AbstractNSphere<Vector2D> implements Linecastable2D {
    40
    41      /** Construct a new circle from its component parts.
    42       * @param center the center of the circle
    43       * @param radius the circle radius
    44       * @param precision precision context used to compare floating point numbers
    45       * @throws IllegalArgumentException if center is not finite or radius is not finite or is
    46       *      less than or equal to zero as evaluated by the given precision context
    47       */
    48      private Circle(final Vector2D center, final double radius, final Precision.DoubleEquivalence precision) {
    49          super(center, radius, precision);
    50      }
    51
    52      /** {@inheritDoc} */
    53      @Override
    54      public double getSize() {
    55          final double r = getRadius();
    56          return Math.PI * r * r;
    57      }
    58
    59      /** {@inheritDoc} */
    60      @Override
    61      public double getBoundarySize() {
    62          return Angle.TWO_PI * getRadius();
    63      }
    64
    65      /** {@inheritDoc} */
    66      @Override
    67      public Vector2D project(final Vector2D pt) {
    68          return project(pt, Vector2D.Unit.PLUS_X);
    69      }
    70
    71      /** Return a {@link RegionBSPTree2D} representing an approximation of the circle.
    72       * All points in the approximation are contained in the circle (ie, they lie inside
    73       * or on the boundary). No guarantees are made regarding the internal structure of
    74       * the returned tree. Non-boundary split nodes may be used in order to balance the tree
    75       * and improve performance.
    76       *
    77       * <p>Choosing an appropriate number of segments for an approximation is a trade-off
    78       * between size and accuracy: approximations with large numbers of segments more closely
    79       * match the geometric properties of the circle but at the cost of using larger tree
    80       * structures. In general, the smallest number of segments that produces an acceptable
    81       * result should be used.
    82       * @param segments number of line segments to use for the boundary of
    83       *      the circle approximation
    84       * @return a BSP tree approximation of the circle
    85       * @throws IllegalArgumentException if {@code segments} is less than 3
    86       */
    87      public RegionBSPTree2D toTree(final int segments) {
    88          return new CircleApproximationBuilder(this, segments).build();
    89      }
    90
    91      /** Get the intersections of the given line with this circle. The returned list will
    92       * contain either 0, 1, or 2 points.
    93       * <ul>
    94       *      <li><strong>2 points</strong> - The line is a secant line and intersects the circle at two
    95       *      distinct points. The points are ordered such that the first point in the list is the first point
    96       *      encountered when traveling in the direction of the line. (In other words, the points are ordered
    97       *      by increasing abscissa value.)
    98       *      </li>
    99       *      <li><strong>1 point</strong> - The line is a tangent line and only intersects the circle at a
    100      *      single point (as evaluated by the circle's precision context).
    101      *      </li>
    102      *      <li><strong>0 points</strong> - The line does not intersect the circle.</li>
    103      * </ul>
    104      * @param line line to intersect with the circle
    105      * @return a list of intersection points between the given line and this circle
    106      */
    107     public List<Vector2D> intersections(final Line line) {
    108         return intersections(line, Line::abscissa, Line::distance);
    109     }
    110
    111     /** Get the first intersection point between the given line and this circle, or null
    112      * if no such point exists. The "first" intersection point is the first such point
    113      * encountered when traveling in the direction of the line from infinity.
    114      * @param line line to intersect with the circle
    115      * @return the first intersection point between the given line and this instance or
    116      *      null if no such point exists
    117      */
    118     public Vector2D firstIntersection(final Line line) {
    119         return firstIntersection(line, Line::abscissa, Line::distance);
    120     }
    121
    122     /** {@inheritDoc} */
    123     @Override
    124     public List<LinecastPoint2D> linecast(final LineConvexSubset segment) {
    125         return getLinecastStream(segment)
    126                 .collect(Collectors.toList());
    127     }
    128
    129     /** {@inheritDoc} */
    130     @Override
    131     public LinecastPoint2D linecastFirst(final LineConvexSubset segment) {
    132         return getLinecastStream(segment)
    133                 .findFirst()
    134                 .orElse(null);
    135     }
    136
    137     /** Get a stream containing the linecast intersection points of the given
    138      * segment with this instance.
    139      * @param segment segment to intersect against this instance
    140      * @return a stream containing linecast intersection points
    141      */
    142     private Stream<LinecastPoint2D> getLinecastStream(final LineConvexSubset segment) {
    143         return intersections(segment.getLine()).stream()
    144             .filter(segment::contains)
    145             .map(pt -> new LinecastPoint2D(pt, getCenter().directionTo(pt), segment.getLine()));
    146     }
    147
    148     /** Construct a circle from a center point and radius.
    149      * @param center the center point of the circle
    150      * @param radius the circle radius
    151      * @param precision precision precision context used to compare floating point numbers
    152      * @return a circle with the given center and radius
    153      * @throws IllegalArgumentException if center is not finite or radius is not finite or is
    154      *      less than or equal to zero as evaluated by the given precision context
    155      */
    156     public static Circle from(final Vector2D center, final double radius, final Precision.DoubleEquivalence precision) {
    157         return new Circle(center, radius, precision);
    158     }
    159
    160     /** Class used to build BSP tree circle approximations. Structural BSP tree cuts are
    161      * used to help balance the tree and improve performance.
    162      */
    163     private static class CircleApproximationBuilder {
    164
    165         /** The minimum number of segments required to create a circle approximation.
    166          */
    167         private static final int MIN_SEGMENTS = 3;
    168
    169         /** Minimum number of line segments in a portion of the approximation in order
    170          * to allow a structural BSP split.
    171          */
    172         private static final int SPLIT_THRESHOLD = 4;
    173
    174         /** Circle being approximated. */
    175         private final Circle circle;
    176
    177         /** Number of boundary segments in the approximation. */
    178         private final int segments;
    179
    180         /** Angle delta between vertex points. */
    181         private final double angleDelta;
    182
    183         /** Create a new instance for approximating the given circle.
    184          * @param circle circle to approximate
    185          * @param segments number of boundary segments in the approximation
    186          * @throws IllegalArgumentException if {@code segments} is less than 3
    187          */
    188         CircleApproximationBuilder(final Circle circle, final int segments) {
    189             if (segments < MIN_SEGMENTS) {
    190                 throw new IllegalArgumentException(MessageFormat.format(
    191                         "Circle approximation segment number must be greater than or equal to {0}; was {1}",
    192                         MIN_SEGMENTS, segments));
    193             }
    194
    195             this.circle = circle;
    196
    197             this.segments = segments;
    198             this.angleDelta = Angle.TWO_PI / segments;
    199         }
    200
    201         /** Build the BSP tree circle approximation.
    202          * @return the BSP tree circle approximation
    203          */
    204         public RegionBSPTree2D build() {
    205             final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    206             final RegionBSPTree2D.RegionNode2D root = tree.getRoot();
    207
    208             if (segments < SPLIT_THRESHOLD) {
    209                 insert(root, 0, segments);
    210             } else {
    211                 // split the circle in half (or mostly in half if an odd number of segments)
    212                 final int splitIdx = segments / 2;
    213                 final Vector2D p0 = pointAt(0);
    214                 final Vector2D p1 = pointAt(splitIdx);
    215
    216                 root.cut(Lines.fromPoints(p0, p1, circle.getPrecision()), RegionCutRule.INHERIT);
    217
    218                 splitAndInsert(root.getPlus(), 0, splitIdx);
    219                 splitAndInsert(root.getMinus(), splitIdx, segments);
    220             }
    221
    222             return tree;
    223         }
    224
    225         /** Split the given node if possible and recursively add boundary segments.
    226          * @param node current tree node
    227          * @param startIdx index of the start point for this node's boundary segments
    228          * @param stopIdx index of the end point for this node's boundary segments
    229          */
    230         private void splitAndInsert(final RegionBSPTree2D.RegionNode2D node, final int startIdx, final int stopIdx) {
    231             if (stopIdx - startIdx >= SPLIT_THRESHOLD) {
    232                 final int splitIdx = ((stopIdx - startIdx + 1) / 2) + startIdx;
    233                 final Vector2D p0 = circle.getCenter();
    234                 final Vector2D p1 = pointAt(splitIdx);
    235
    236                 node.cut(Lines.fromPoints(p0, p1, circle.getPrecision()), RegionCutRule.INHERIT);
    237
    238                 splitAndInsert(node.getPlus(), startIdx, splitIdx);
    239                 splitAndInsert(node.getMinus(), splitIdx, stopIdx);
    240             } else {
    241                 insert(node, startIdx, stopIdx);
    242             }
    243         }
    244
    245         /** Insert boundary segments into the given node. No structural splits are created.
    246          * @param node current tree node
    247          * @param startIdx index of the start point for this node's boundary segments
    248          * @param stopIdx index of the end point for this node's boundary segments
    249          */
    250         private void insert(final RegionBSPTree2D.RegionNode2D node, final int startIdx, final int stopIdx) {
    251
    252             RegionBSPTree2D.RegionNode2D currNode = node;
    253             Vector2D currPt;
    254             Vector2D prevPt = pointAt(startIdx);
    255             for (int i = startIdx + 1; i <= stopIdx; ++i) {
    256                 currPt = pointAt(i);
    257
    258                 currNode = currNode.cut(Lines.fromPoints(prevPt, currPt, circle.getPrecision()))
    259                         .getMinus();
    260
    261                 prevPt = currPt;
    262             }
    263         }
    264
    265         /** Get the boundary vertex point at the given index.
    266          * @param idx vertex point index
    267          * @return the vertex point at the given index
    268          */
    269         private Vector2D pointAt(final int idx) {
    270             return PolarCoordinates.toCartesian(circle.getRadius(), idx * angleDelta)
    271                     .add(circle.getCenter());
    272         }
    273     }
    274 }