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.List;
20
21 import org.apache.commons.geometry.core.RegionEmbedding;
22 import org.apache.commons.geometry.core.RegionLocation;
23 import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
24 import org.apache.commons.geometry.core.partitioning.HyperplaneSubset;
25 import org.apache.commons.geometry.core.partitioning.Split;
26 import org.apache.commons.geometry.euclidean.oned.Vector1D;
27 import org.apache.commons.numbers.core.Precision;
28
29 /** Class representing a subset of points on a line in 2D Euclidean space. For example, line segments
30 * and rays are line subsets. Line subsets may be finite or infinite.
31 */
32 public abstract class LineSubset implements HyperplaneSubset<Vector2D>, RegionEmbedding<Vector2D, Vector1D> {
33 /** The line containing this instance. */
34 private final Line line;
35
36 /** Construct a new instance based on the given line.
37 * @param line line forming the base of the instance
38 */
39 LineSubset(final Line line) {
40 this.line = line;
41 }
42
43 /** Get the line containing this subset. This method is an alias
44 * for {@link #getHyperplane()}.
45 * @return the line containing this subset
46 * @see #getHyperplane()
47 */
48 public Line getLine() {
49 return getHyperplane();
50 }
51
52 /** {@inheritDoc} */
53 @Override
54 public Line getHyperplane() {
55 return line;
56 }
57
58 /** {@inheritDoc} */
59 @Override
60 public Vector1D toSubspace(final Vector2D pt) {
61 return line.toSubspace(pt);
62 }
63
64 /** Get a {@link Bounds2D} object defining an axis-aligned bounding box containing all
65 * vertices for this subset. Null is returned if the subset is infinite or does not
66 * contain any vertices.
67 * @return the bounding box for this instance or null if no valid bounds could be determined
68 */
69 public abstract Bounds2D getBounds();
70
71 /** {@inheritDoc} */
72 @Override
73 public abstract HyperplaneBoundedRegion<Vector1D> getSubspaceRegion();
74
75 /** {@inheritDoc} */
76 @Override
77 public Vector2D toSpace(final Vector1D pt) {
78 return line.toSpace(pt);
79 }
80
81 /** {@inheritDoc} */
82 @Override
83 public abstract List<LineConvexSubset> toConvex();
84
85 /** {@inheritDoc} */
86 @Override
87 public RegionLocation classify(final Vector2D pt) {
88 if (line.contains(pt)) {
89 return classifyAbscissa(line.abscissa(pt));
90 }
91
92 return RegionLocation.OUTSIDE;
93 }
94
95 /** Get the unique intersection of this subset with the given line. Null is
96 * returned if no unique intersection point exists (ie, the lines are
97 * parallel or coincident) or the line does not intersect this instance.
98 * @param inputLine line to intersect with this line subset
99 * @return the unique intersection point between the line and this line subset
100 * or null if no such point exists.
101 * @see Line#intersection(Line)
102 */
103 public Vector2D intersection(final Line inputLine) {
104 final Vector2D pt = line.intersection(inputLine);
105 return (pt != null && contains(pt)) ? pt : null;
106 }
107
108 /** Get the unique intersection of this instance with the given line subset. Null
109 * is returned if the lines containing the line subsets do not have a unique intersection
110 * point (ie, they are parallel or coincident) or the intersection point is unique
111 * but is not contained in both line subsets.
112 * @param subset line subset to intersect with
113 * @return the unique intersection point between this line subset and the argument or
114 * null if no such point exists.
115 * @see Line#intersection(Line)
116 */
117 public Vector2D intersection(final LineSubset subset) {
118 final Vector2D pt = intersection(subset.getLine());
119 return (pt != null && subset.contains(pt)) ? pt : null;
120 }
121
122 /** Return the object used to perform floating point comparisons, which is the
123 * same object used by the underlying {@link Line}).
124 * @return precision object used to perform floating point comparisons.
125 */
126 public Precision.DoubleEquivalence getPrecision() {
127 return line.getPrecision();
128 }
129
130 /** Classify the given line abscissa value with respect to the subspace region.
131 * @param abscissa the abscissa value to classify
132 * @return the region location of the line abscissa value
133 */
134 abstract RegionLocation classifyAbscissa(double abscissa);
135
136 /** Get a split result for cases where no intersection exists between the splitting line and the
137 * line underlying the given line subset. This occurs when the two lines are parallel or coincident.
138 * @param <T> Line subset type
139 * @param splitter splitting line
140 * @param subset line subset instance being split
141 * @return return result of the non-intersecting split operation
142 */
143 <T extends LineSubset> Split<T> getNonIntersectingSplitResult(final Line splitter, final T subset) {
144 // check which side of the splitter we lie on
145 final double offset = splitter.offset(subset.getLine());
146 final int comp = getPrecision().compare(offset, 0.0);
147
148 if (comp < 0) {
149 return new Split<>(subset, null);
150 } else if (comp > 0) {
151 return new Split<>(null, subset);
152 } else {
153 return new Split<>(null, null);
154 }
155 }
156
157 /** Return true if the plus side of the given splitter line is facing in the positive direction
158 * of this line.
159 * @param splitterLine line splitting this instance
160 * @return true if the plus side of the given line is facing in the positive direction of this
161 * line
162 */
163 boolean splitterPlusIsPositiveFacing(final Line splitterLine) {
164 return line.getOffsetDirection().dot(splitterLine.getDirection()) <= 0;
165 }
166
167 /** Create a split result for the given splitter line, given the low and high split portion of this
168 * instance. The arguments are assigned to the split result's minus and plus properties based on the
169 * relative orientation of the splitter line.
170 * @param <T> Line subset type
171 * @param splitter splitter line
172 * @param low portion of the split result closest to negative infinity on this line
173 * @param high portion of th split result closest to positive infinity on this line
174 * @return a split result for the given splitter line.
175 */
176 <T extends LineSubset> Split<T> createSplitResult(final Line splitter, final T low, final T high) {
177 return splitterPlusIsPositiveFacing(splitter) ?
178 new Split<>(low, high) :
179 new Split<>(high, low);
180 }
181 }