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.Arrays;
20 import java.util.Collection;
21 import java.util.Collections;
22 import java.util.List;
23 import java.util.stream.Stream;
24
25 import org.apache.commons.geometry.core.Transform;
26 import org.apache.commons.geometry.core.partitioning.AbstractConvexHyperplaneBoundedRegion;
27 import org.apache.commons.geometry.core.partitioning.Hyperplane;
28 import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
29 import org.apache.commons.geometry.core.partitioning.Split;
30 import org.apache.commons.geometry.euclidean.twod.path.InteriorAngleLinePathConnector;
31 import org.apache.commons.geometry.euclidean.twod.path.LinePath;
32 import org.apache.commons.numbers.core.Precision;
33
34 /** Class representing a finite or infinite convex area in Euclidean 2D space.
35 * The boundaries of this area, if any, are composed of convex line subsets.
36 */
37 public class ConvexArea extends AbstractConvexHyperplaneBoundedRegion<Vector2D, LineConvexSubset>
38 implements BoundarySource2D {
39
40 /** Error message used when attempting to construct a convex polygon from a non-convex line path. */
41 private static final String NON_CONVEX_PATH_ERROR = "Cannot construct convex polygon from non-convex path: ";
42
43 /** Instance representing the full 2D plane. */
44 private static final ConvexArea FULL = new ConvexArea(Collections.emptyList());
45
46 /** Simple constructor. Callers are responsible for ensuring that the given path
47 * represents the boundary of a convex area. No validation is performed.
48 * @param boundaries the boundaries of the convex area
49 */
50 protected ConvexArea(final List<LineConvexSubset> boundaries) {
51 super(boundaries);
52 }
53
54 /** {@inheritDoc} */
55 @Override
56 public Stream<LineConvexSubset> boundaryStream() {
57 return getBoundaries().stream();
58 }
59
60 /** Get the connected line subset paths comprising the boundary of the area. The
61 * line subsets are oriented so that their minus sides point toward the interior of the
62 * region. The size of the returned list is
63 * <ul>
64 * <li><strong>0</strong> if the convex area is full,</li>
65 * <li><strong>1</strong> if at least one boundary is present and
66 * a single path can connect all line subsets (this will be the case
67 * for most instances), and</li>
68 * <li><strong>2</strong> if only two boundaries exist and they are
69 * parallel to each other (in which case they cannot be connected
70 * as a single path).</li>
71 * </ul>
72 * @return the line subset paths comprising the boundary of the area.
73 */
74 public List<LinePath> getBoundaryPaths() {
75 // use connectMaximized() here since that will prevent us from skipping vertices
76 // when there are multiple equivalent vertices to choose from for a given endpoint
77 return InteriorAngleLinePathConnector.connectMaximized(getBoundaries());
78 }
79
80 /** Get the vertices for the area in a counter-clockwise order. Each vertex in the
81 * returned list is unique. If the boundary of the area is closed, the start vertex is
82 * <em>not</em> repeated at the end of the list.
83 *
84 * <p>It is important to note that, in general, the list of vertices returned by this method
85 * is not sufficient to completely characterize the area. For example, a simple triangle
86 * has 3 vertices, but an infinite area constructed from two parallel lines and two lines that
87 * intersect between them will also have 3 vertices. It is also possible for non-empty areas to
88 * contain no vertices at all. For example, an area with no boundaries (representing the full
89 * space), an area with a single boundary, or an area with two parallel boundaries will not
90 * contain any vertices.</p>
91 * @return the list of vertices for the area in a counter-clockwise order
92 */
93 public List<Vector2D> getVertices() {
94 final List<LinePath> paths = getBoundaryPaths();
95
96 // we will only have vertices if we have a single path; otherwise, we have a full
97 // area or two non-intersecting infinite line subsets
98 if (paths.size() == 1) {
99 final LinePath path = paths.get(0);
100 final List<Vector2D> vertices = path.getVertexSequence();
101
102 if (path.isClosed()) {
103 // do not include the repeated start point
104 return vertices.subList(0, vertices.size() - 1);
105 }
106 return vertices;
107 }
108
109 return Collections.emptyList();
110 }
111
112 /** Return a new instance transformed by the argument.
113 * @param transform transform to apply
114 * @return a new instance transformed by the argument
115 */
116 public ConvexArea transform(final Transform<Vector2D> transform) {
117 return transformInternal(transform, this, LineConvexSubset.class, ConvexArea::new);
118 }
119
120 /** {@inheritDoc} */
121 @Override
122 public LineConvexSubset trim(final HyperplaneConvexSubset<Vector2D> convexSubset) {
123 return (LineConvexSubset) super.trim(convexSubset);
124 }
125
126 /** {@inheritDoc} */
127 @Override
128 public double getSize() {
129 if (isFull()) {
130 return Double.POSITIVE_INFINITY;
131 }
132
133 double quadrilateralAreaSum = 0.0;
134
135 for (final LineConvexSubset boundary : getBoundaries()) {
136 if (boundary.isInfinite()) {
137 return Double.POSITIVE_INFINITY;
138 }
139
140 quadrilateralAreaSum += boundary.getStartPoint().signedArea(boundary.getEndPoint());
141 }
142
143 return 0.5 * quadrilateralAreaSum;
144 }
145
146 /** {@inheritDoc} */
147 @Override
148 public Vector2D getCentroid() {
149 final List<LineConvexSubset> boundaries = getBoundaries();
150
151 double quadrilateralAreaSum = 0.0;
152 double scaledSumX = 0.0;
153 double scaledSumY = 0.0;
154
155 double signedArea;
156 Vector2D startPoint;
157 Vector2D endPoint;
158
159 for (final LineConvexSubset seg : boundaries) {
160 if (seg.isInfinite()) {
161 // infinite => no centroid
162 return null;
163 }
164
165 startPoint = seg.getStartPoint();
166 endPoint = seg.getEndPoint();
167
168 signedArea = startPoint.signedArea(endPoint);
169
170 quadrilateralAreaSum += signedArea;
171
172 scaledSumX += signedArea * (startPoint.getX() + endPoint.getX());
173 scaledSumY += signedArea * (startPoint.getY() + endPoint.getY());
174 }
175
176 if (quadrilateralAreaSum > 0) {
177 return Vector2D.of(scaledSumX, scaledSumY).multiply(1.0 / (3.0 * quadrilateralAreaSum));
178 }
179
180 return null;
181 }
182
183 /** {@inheritDoc} */
184 @Override
185 public Split<ConvexArea> split(final Hyperplane<Vector2D> splitter) {
186 return splitInternal(splitter, this, LineConvexSubset.class, ConvexArea::new);
187 }
188
189 /** Return a BSP tree representing the same region as this instance.
190 */
191 @Override
192 public RegionBSPTree2D toTree() {
193 return RegionBSPTree2D.from(getBoundaries(), true);
194 }
195
196 /** Return an instance representing the full 2D area.
197 * @return an instance representing the full 2D area.
198 */
199 public static ConvexArea full() {
200 return FULL;
201 }
202
203 /** Construct a convex polygon from the given vertices.
204 * @param vertices vertices to use to construct the polygon
205 * @param precision precision context used for floating point comparisons
206 * @return a convex polygon constructed using the given vertices
207 * @throws IllegalStateException if {@code vertices} contains only a single unique vertex
208 * @throws IllegalArgumentException if the constructed path does not define a closed, convex polygon
209 * @see LinePath#fromVertexLoop(Collection, Precision.DoubleEquivalence)
210 */
211 public static ConvexArea convexPolygonFromVertices(final Collection<Vector2D> vertices,
212 final Precision.DoubleEquivalence precision) {
213 return convexPolygonFromPath(LinePath.fromVertexLoop(vertices, precision));
214 }
215
216 /** Construct a convex polygon from a line path.
217 * @param path path to construct the polygon from
218 * @return a convex polygon constructed from the given line path
219 * @throws IllegalArgumentException if the path does not define a closed, convex polygon
220 */
221 public static ConvexArea convexPolygonFromPath(final LinePath path) {
222 // ensure that the path is closed; this also ensures that we do not have any infinite elements
223 if (!path.isClosed()) {
224 throw new IllegalArgumentException("Cannot construct convex polygon from unclosed path: " + path);
225 }
226
227 final List<LineConvexSubset> elements = path.getElements();
228 if (elements.size() < 3) {
229 throw new IllegalArgumentException(
230 "Cannot construct convex polygon from path with less than 3 elements: " + path);
231 }
232
233 // go through the elements and validate that the produced area is convex and finite
234 // using the precision context from the first path element
235 final LineConvexSubset startElement = elements.get(0);
236 final Vector2D startVertex = startElement.getStartPoint();
237 final Precision.DoubleEquivalence precision = startElement.getPrecision();
238
239 Vector2D curVector;
240 Vector2D prevVector = null;
241
242 double signedArea;
243 double totalSignedArea = 0.0;
244
245 LineConvexSubset element;
246
247 // we can skip the last element since the we know that the path is closed, meaning that the
248 // last element's end point is equal to our start point
249 for (int i = 0; i < elements.size() - 1; ++i) {
250 element = elements.get(i);
251
252 curVector = startVertex.vectorTo(element.getEndPoint());
253
254 if (prevVector != null) {
255 signedArea = prevVector.signedArea(curVector);
256 if (precision.lt(signedArea, 0.0)) {
257 throw new IllegalArgumentException(NON_CONVEX_PATH_ERROR + path);
258 }
259
260 totalSignedArea += signedArea;
261 }
262
263 prevVector = curVector;
264 }
265
266 if (precision.lte(totalSignedArea, 0.0)) {
267 throw new IllegalArgumentException(NON_CONVEX_PATH_ERROR + path);
268 }
269
270 return new ConvexArea(elements);
271 }
272
273 /** Create a convex area formed by the intersection of the negative half-spaces of the
274 * given bounding lines. The returned instance represents the area that is on the
275 * minus side of all of the given lines. Note that this method does not support areas
276 * of zero size (ie, infinitely thin areas or points.)
277 * @param bounds lines used to define the convex area
278 * @return a new convex area instance representing the area on the minus side of all
279 * of the bounding lines or an instance representing the full area if no lines are
280 * given
281 * @throws IllegalArgumentException if the given set of bounding lines do not form a convex area,
282 * meaning that there is no region that is on the minus side of all of the bounding lines.
283 */
284 public static ConvexArea fromBounds(final Line... bounds) {
285 return fromBounds(Arrays.asList(bounds));
286 }
287
288 /** Create a convex area formed by the intersection of the negative half-spaces of the
289 * given bounding lines. The returned instance represents the area that is on the
290 * minus side of all of the given lines. Note that this method does not support areas
291 * of zero size (ie, infinitely thin areas or points.)
292 * @param bounds lines used to define the convex area
293 * @return a new convex area instance representing the area on the minus side of all
294 * of the bounding lines or an instance representing the full area if the collection
295 * is empty
296 * @throws IllegalArgumentException if the given set of bounding lines do not form a convex area,
297 * meaning that there is no region that is on the minus side of all of the bounding lines.
298 */
299 public static ConvexArea fromBounds(final Iterable<Line> bounds) {
300 final List<LineConvexSubset> subsets =
301 new ConvexRegionBoundaryBuilder<>(LineConvexSubset.class).build(bounds);
302 return subsets.isEmpty() ? full() : new ConvexArea(subsets);
303 }
304 }