Circle.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.geometry.euclidean.twod.shape;
import java.text.MessageFormat;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
import org.apache.commons.geometry.euclidean.AbstractNSphere;
import org.apache.commons.geometry.euclidean.twod.Line;
import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
import org.apache.commons.geometry.euclidean.twod.LinecastPoint2D;
import org.apache.commons.geometry.euclidean.twod.Linecastable2D;
import org.apache.commons.geometry.euclidean.twod.Lines;
import org.apache.commons.geometry.euclidean.twod.PolarCoordinates;
import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
import org.apache.commons.numbers.angle.Angle;
import org.apache.commons.numbers.core.Precision;
/** Class representing a circle in 2 dimensional Euclidean space.
*/
public final class Circle extends AbstractNSphere<Vector2D> implements Linecastable2D {
/** Construct a new circle from its component parts.
* @param center the center of the circle
* @param radius the circle radius
* @param precision precision context used to compare floating point numbers
* @throws IllegalArgumentException if center is not finite or radius is not finite or is
* less than or equal to zero as evaluated by the given precision context
*/
private Circle(final Vector2D center, final double radius, final Precision.DoubleEquivalence precision) {
super(center, radius, precision);
}
/** {@inheritDoc} */
@Override
public double getSize() {
final double r = getRadius();
return Math.PI * r * r;
}
/** {@inheritDoc} */
@Override
public double getBoundarySize() {
return Angle.TWO_PI * getRadius();
}
/** {@inheritDoc} */
@Override
public Vector2D project(final Vector2D pt) {
return project(pt, Vector2D.Unit.PLUS_X);
}
/** Return a {@link RegionBSPTree2D} representing an approximation of the circle.
* All points in the approximation are contained in the circle (ie, they lie inside
* or on the boundary). No guarantees are made regarding the internal structure of
* the returned tree. Non-boundary split nodes may be used in order to balance the tree
* and improve performance.
*
* <p>Choosing an appropriate number of segments for an approximation is a trade-off
* between size and accuracy: approximations with large numbers of segments more closely
* match the geometric properties of the circle but at the cost of using larger tree
* structures. In general, the smallest number of segments that produces an acceptable
* result should be used.
* @param segments number of line segments to use for the boundary of
* the circle approximation
* @return a BSP tree approximation of the circle
* @throws IllegalArgumentException if {@code segments} is less than 3
*/
public RegionBSPTree2D toTree(final int segments) {
return new CircleApproximationBuilder(this, segments).build();
}
/** Get the intersections of the given line with this circle. The returned list will
* contain either 0, 1, or 2 points.
* <ul>
* <li><strong>2 points</strong> - The line is a secant line and intersects the circle at two
* distinct points. The points are ordered such that the first point in the list is the first point
* encountered when traveling in the direction of the line. (In other words, the points are ordered
* by increasing abscissa value.)
* </li>
* <li><strong>1 point</strong> - The line is a tangent line and only intersects the circle at a
* single point (as evaluated by the circle's precision context).
* </li>
* <li><strong>0 points</strong> - The line does not intersect the circle.</li>
* </ul>
* @param line line to intersect with the circle
* @return a list of intersection points between the given line and this circle
*/
public List<Vector2D> intersections(final Line line) {
return intersections(line, Line::abscissa, Line::distance);
}
/** Get the first intersection point between the given line and this circle, or null
* if no such point exists. The "first" intersection point is the first such point
* encountered when traveling in the direction of the line from infinity.
* @param line line to intersect with the circle
* @return the first intersection point between the given line and this instance or
* null if no such point exists
*/
public Vector2D firstIntersection(final Line line) {
return firstIntersection(line, Line::abscissa, Line::distance);
}
/** {@inheritDoc} */
@Override
public List<LinecastPoint2D> linecast(final LineConvexSubset segment) {
return getLinecastStream(segment)
.collect(Collectors.toList());
}
/** {@inheritDoc} */
@Override
public LinecastPoint2D linecastFirst(final LineConvexSubset segment) {
return getLinecastStream(segment)
.findFirst()
.orElse(null);
}
/** Get a stream containing the linecast intersection points of the given
* segment with this instance.
* @param segment segment to intersect against this instance
* @return a stream containing linecast intersection points
*/
private Stream<LinecastPoint2D> getLinecastStream(final LineConvexSubset segment) {
return intersections(segment.getLine()).stream()
.filter(segment::contains)
.map(pt -> new LinecastPoint2D(pt, getCenter().directionTo(pt), segment.getLine()));
}
/** Construct a circle from a center point and radius.
* @param center the center point of the circle
* @param radius the circle radius
* @param precision precision precision context used to compare floating point numbers
* @return a circle with the given center and radius
* @throws IllegalArgumentException if center is not finite or radius is not finite or is
* less than or equal to zero as evaluated by the given precision context
*/
public static Circle from(final Vector2D center, final double radius, final Precision.DoubleEquivalence precision) {
return new Circle(center, radius, precision);
}
/** Class used to build BSP tree circle approximations. Structural BSP tree cuts are
* used to help balance the tree and improve performance.
*/
private static class CircleApproximationBuilder {
/** The minimum number of segments required to create a circle approximation.
*/
private static final int MIN_SEGMENTS = 3;
/** Minimum number of line segments in a portion of the approximation in order
* to allow a structural BSP split.
*/
private static final int SPLIT_THRESHOLD = 4;
/** Circle being approximated. */
private final Circle circle;
/** Number of boundary segments in the approximation. */
private final int segments;
/** Angle delta between vertex points. */
private final double angleDelta;
/** Create a new instance for approximating the given circle.
* @param circle circle to approximate
* @param segments number of boundary segments in the approximation
* @throws IllegalArgumentException if {@code segments} is less than 3
*/
CircleApproximationBuilder(final Circle circle, final int segments) {
if (segments < MIN_SEGMENTS) {
throw new IllegalArgumentException(MessageFormat.format(
"Circle approximation segment number must be greater than or equal to {0}; was {1}",
MIN_SEGMENTS, segments));
}
this.circle = circle;
this.segments = segments;
this.angleDelta = Angle.TWO_PI / segments;
}
/** Build the BSP tree circle approximation.
* @return the BSP tree circle approximation
*/
public RegionBSPTree2D build() {
final RegionBSPTree2D tree = RegionBSPTree2D.empty();
final RegionBSPTree2D.RegionNode2D root = tree.getRoot();
if (segments < SPLIT_THRESHOLD) {
insert(root, 0, segments);
} else {
// split the circle in half (or mostly in half if an odd number of segments)
final int splitIdx = segments / 2;
final Vector2D p0 = pointAt(0);
final Vector2D p1 = pointAt(splitIdx);
root.cut(Lines.fromPoints(p0, p1, circle.getPrecision()), RegionCutRule.INHERIT);
splitAndInsert(root.getPlus(), 0, splitIdx);
splitAndInsert(root.getMinus(), splitIdx, segments);
}
return tree;
}
/** Split the given node if possible and recursively add boundary segments.
* @param node current tree node
* @param startIdx index of the start point for this node's boundary segments
* @param stopIdx index of the end point for this node's boundary segments
*/
private void splitAndInsert(final RegionBSPTree2D.RegionNode2D node, final int startIdx, final int stopIdx) {
if (stopIdx - startIdx >= SPLIT_THRESHOLD) {
final int splitIdx = ((stopIdx - startIdx + 1) / 2) + startIdx;
final Vector2D p0 = circle.getCenter();
final Vector2D p1 = pointAt(splitIdx);
node.cut(Lines.fromPoints(p0, p1, circle.getPrecision()), RegionCutRule.INHERIT);
splitAndInsert(node.getPlus(), startIdx, splitIdx);
splitAndInsert(node.getMinus(), splitIdx, stopIdx);
} else {
insert(node, startIdx, stopIdx);
}
}
/** Insert boundary segments into the given node. No structural splits are created.
* @param node current tree node
* @param startIdx index of the start point for this node's boundary segments
* @param stopIdx index of the end point for this node's boundary segments
*/
private void insert(final RegionBSPTree2D.RegionNode2D node, final int startIdx, final int stopIdx) {
RegionBSPTree2D.RegionNode2D currNode = node;
Vector2D currPt;
Vector2D prevPt = pointAt(startIdx);
for (int i = startIdx + 1; i <= stopIdx; ++i) {
currPt = pointAt(i);
currNode = currNode.cut(Lines.fromPoints(prevPt, currPt, circle.getPrecision()))
.getMinus();
prevPt = currPt;
}
}
/** Get the boundary vertex point at the given index.
* @param idx vertex point index
* @return the vertex point at the given index
*/
private Vector2D pointAt(final int idx) {
return PolarCoordinates.toCartesian(circle.getRadius(), idx * angleDelta)
.add(circle.getCenter());
}
}
}