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 }