001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.math3.geometry.euclidean.twod;
018
019 import java.awt.geom.AffineTransform;
020
021 import org.apache.commons.math3.exception.MathIllegalArgumentException;
022 import org.apache.commons.math3.exception.util.LocalizedFormats;
023 import org.apache.commons.math3.geometry.Vector;
024 import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D;
025 import org.apache.commons.math3.geometry.euclidean.oned.IntervalsSet;
026 import org.apache.commons.math3.geometry.euclidean.oned.OrientedPoint;
027 import org.apache.commons.math3.geometry.euclidean.oned.Vector1D;
028 import org.apache.commons.math3.geometry.partitioning.Embedding;
029 import org.apache.commons.math3.geometry.partitioning.Hyperplane;
030 import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
031 import org.apache.commons.math3.geometry.partitioning.Transform;
032 import org.apache.commons.math3.util.FastMath;
033 import org.apache.commons.math3.util.MathUtils;
034
035 /** This class represents an oriented line in the 2D plane.
036
037 * <p>An oriented line can be defined either by prolongating a line
038 * segment between two points past these points, or by one point and
039 * an angular direction (in trigonometric orientation).</p>
040
041 * <p>Since it is oriented the two half planes at its two sides are
042 * unambiguously identified as a left half plane and a right half
043 * plane. This can be used to identify the interior and the exterior
044 * in a simple way by local properties only when part of a line is
045 * used to define part of a polygon boundary.</p>
046
047 * <p>A line can also be used to completely define a reference frame
048 * in the plane. It is sufficient to select one specific point in the
049 * line (the orthogonal projection of the original reference frame on
050 * the line) and to use the unit vector in the line direction and the
051 * orthogonal vector oriented from left half plane to right half
052 * plane. We define two coordinates by the process, the
053 * <em>abscissa</em> along the line, and the <em>offset</em> across
054 * the line. All points of the plane are uniquely identified by these
055 * two coordinates. The line is the set of points at zero offset, the
056 * left half plane is the set of points with negative offsets and the
057 * right half plane is the set of points with positive offsets.</p>
058
059 * @version $Id: Line.java 1422195 2012-12-15 06:45:18Z psteitz $
060 * @since 3.0
061 */
062 public class Line implements Hyperplane<Euclidean2D>, Embedding<Euclidean2D, Euclidean1D> {
063
064 /** Angle with respect to the abscissa axis. */
065 private double angle;
066
067 /** Cosine of the line angle. */
068 private double cos;
069
070 /** Sine of the line angle. */
071 private double sin;
072
073 /** Offset of the frame origin. */
074 private double originOffset;
075
076 /** Build a line from two points.
077 * <p>The line is oriented from p1 to p2</p>
078 * @param p1 first point
079 * @param p2 second point
080 */
081 public Line(final Vector2D p1, final Vector2D p2) {
082 reset(p1, p2);
083 }
084
085 /** Build a line from a point and an angle.
086 * @param p point belonging to the line
087 * @param angle angle of the line with respect to abscissa axis
088 */
089 public Line(final Vector2D p, final double angle) {
090 reset(p, angle);
091 }
092
093 /** Build a line from its internal characteristics.
094 * @param angle angle of the line with respect to abscissa axis
095 * @param cos cosine of the angle
096 * @param sin sine of the angle
097 * @param originOffset offset of the origin
098 */
099 private Line(final double angle, final double cos, final double sin, final double originOffset) {
100 this.angle = angle;
101 this.cos = cos;
102 this.sin = sin;
103 this.originOffset = originOffset;
104 }
105
106 /** Copy constructor.
107 * <p>The created instance is completely independent from the
108 * original instance, it is a deep copy.</p>
109 * @param line line to copy
110 */
111 public Line(final Line line) {
112 angle = MathUtils.normalizeAngle(line.angle, FastMath.PI);
113 cos = FastMath.cos(angle);
114 sin = FastMath.sin(angle);
115 originOffset = line.originOffset;
116 }
117
118 /** {@inheritDoc} */
119 public Line copySelf() {
120 return new Line(this);
121 }
122
123 /** Reset the instance as if built from two points.
124 * <p>The line is oriented from p1 to p2</p>
125 * @param p1 first point
126 * @param p2 second point
127 */
128 public void reset(final Vector2D p1, final Vector2D p2) {
129 final double dx = p2.getX() - p1.getX();
130 final double dy = p2.getY() - p1.getY();
131 final double d = FastMath.hypot(dx, dy);
132 if (d == 0.0) {
133 angle = 0.0;
134 cos = 1.0;
135 sin = 0.0;
136 originOffset = p1.getY();
137 } else {
138 angle = FastMath.PI + FastMath.atan2(-dy, -dx);
139 cos = FastMath.cos(angle);
140 sin = FastMath.sin(angle);
141 originOffset = (p2.getX() * p1.getY() - p1.getX() * p2.getY()) / d;
142 }
143 }
144
145 /** Reset the instance as if built from a line and an angle.
146 * @param p point belonging to the line
147 * @param alpha angle of the line with respect to abscissa axis
148 */
149 public void reset(final Vector2D p, final double alpha) {
150 this.angle = MathUtils.normalizeAngle(alpha, FastMath.PI);
151 cos = FastMath.cos(this.angle);
152 sin = FastMath.sin(this.angle);
153 originOffset = cos * p.getY() - sin * p.getX();
154 }
155
156 /** Revert the instance.
157 */
158 public void revertSelf() {
159 if (angle < FastMath.PI) {
160 angle += FastMath.PI;
161 } else {
162 angle -= FastMath.PI;
163 }
164 cos = -cos;
165 sin = -sin;
166 originOffset = -originOffset;
167 }
168
169 /** Get the reverse of the instance.
170 * <p>Get a line with reversed orientation with respect to the
171 * instance. A new object is built, the instance is untouched.</p>
172 * @return a new line, with orientation opposite to the instance orientation
173 */
174 public Line getReverse() {
175 return new Line((angle < FastMath.PI) ? (angle + FastMath.PI) : (angle - FastMath.PI),
176 -cos, -sin, -originOffset);
177 }
178
179 /** {@inheritDoc} */
180 public Vector1D toSubSpace(final Vector<Euclidean2D> point) {
181 Vector2D p2 = (Vector2D) point;
182 return new Vector1D(cos * p2.getX() + sin * p2.getY());
183 }
184
185 /** {@inheritDoc} */
186 public Vector2D toSpace(final Vector<Euclidean1D> point) {
187 final double abscissa = ((Vector1D) point).getX();
188 return new Vector2D(abscissa * cos - originOffset * sin,
189 abscissa * sin + originOffset * cos);
190 }
191
192 /** Get the intersection point of the instance and another line.
193 * @param other other line
194 * @return intersection point of the instance and the other line
195 * or null if there are no intersection points
196 */
197 public Vector2D intersection(final Line other) {
198 final double d = sin * other.cos - other.sin * cos;
199 if (FastMath.abs(d) < 1.0e-10) {
200 return null;
201 }
202 return new Vector2D((cos * other.originOffset - other.cos * originOffset) / d,
203 (sin * other.originOffset - other.sin * originOffset) / d);
204 }
205
206 /** {@inheritDoc} */
207 public SubLine wholeHyperplane() {
208 return new SubLine(this, new IntervalsSet());
209 }
210
211 /** Build a region covering the whole space.
212 * @return a region containing the instance (really a {@link
213 * PolygonsSet PolygonsSet} instance)
214 */
215 public PolygonsSet wholeSpace() {
216 return new PolygonsSet();
217 }
218
219 /** Get the offset (oriented distance) of a parallel line.
220 * <p>This method should be called only for parallel lines otherwise
221 * the result is not meaningful.</p>
222 * <p>The offset is 0 if both lines are the same, it is
223 * positive if the line is on the right side of the instance and
224 * negative if it is on the left side, according to its natural
225 * orientation.</p>
226 * @param line line to check
227 * @return offset of the line
228 */
229 public double getOffset(final Line line) {
230 return originOffset +
231 ((cos * line.cos + sin * line.sin > 0) ? -line.originOffset : line.originOffset);
232 }
233
234 /** {@inheritDoc} */
235 public double getOffset(final Vector<Euclidean2D> point) {
236 Vector2D p2 = (Vector2D) point;
237 return sin * p2.getX() - cos * p2.getY() + originOffset;
238 }
239
240 /** {@inheritDoc} */
241 public boolean sameOrientationAs(final Hyperplane<Euclidean2D> other) {
242 final Line otherL = (Line) other;
243 return (sin * otherL.sin + cos * otherL.cos) >= 0.0;
244 }
245
246 /** Get one point from the plane.
247 * @param abscissa desired abscissa for the point
248 * @param offset desired offset for the point
249 * @return one point in the plane, with given abscissa and offset
250 * relative to the line
251 */
252 public Vector2D getPointAt(final Vector1D abscissa, final double offset) {
253 final double x = abscissa.getX();
254 final double dOffset = offset - originOffset;
255 return new Vector2D(x * cos + dOffset * sin, x * sin - dOffset * cos);
256 }
257
258 /** Check if the line contains a point.
259 * @param p point to check
260 * @return true if p belongs to the line
261 */
262 public boolean contains(final Vector2D p) {
263 return FastMath.abs(getOffset(p)) < 1.0e-10;
264 }
265
266 /** Compute the distance between the instance and a point.
267 * <p>This is a shortcut for invoking FastMath.abs(getOffset(p)),
268 * and provides consistency with what is in the
269 * org.apache.commons.math3.geometry.euclidean.threed.Line class.</p>
270 *
271 * @param p to check
272 * @return distance between the instance and the point
273 * @since 3.1
274 */
275 public double distance(final Vector2D p) {
276 return FastMath.abs(getOffset(p));
277 }
278
279 /** Check the instance is parallel to another line.
280 * @param line other line to check
281 * @return true if the instance is parallel to the other line
282 * (they can have either the same or opposite orientations)
283 */
284 public boolean isParallelTo(final Line line) {
285 return FastMath.abs(sin * line.cos - cos * line.sin) < 1.0e-10;
286 }
287
288 /** Translate the line to force it passing by a point.
289 * @param p point by which the line should pass
290 */
291 public void translateToPoint(final Vector2D p) {
292 originOffset = cos * p.getY() - sin * p.getX();
293 }
294
295 /** Get the angle of the line.
296 * @return the angle of the line with respect to the abscissa axis
297 */
298 public double getAngle() {
299 return MathUtils.normalizeAngle(angle, FastMath.PI);
300 }
301
302 /** Set the angle of the line.
303 * @param angle new angle of the line with respect to the abscissa axis
304 */
305 public void setAngle(final double angle) {
306 this.angle = MathUtils.normalizeAngle(angle, FastMath.PI);
307 cos = FastMath.cos(this.angle);
308 sin = FastMath.sin(this.angle);
309 }
310
311 /** Get the offset of the origin.
312 * @return the offset of the origin
313 */
314 public double getOriginOffset() {
315 return originOffset;
316 }
317
318 /** Set the offset of the origin.
319 * @param offset offset of the origin
320 */
321 public void setOriginOffset(final double offset) {
322 originOffset = offset;
323 }
324
325 /** Get a {@link org.apache.commons.math3.geometry.partitioning.Transform
326 * Transform} embedding an affine transform.
327 * @param transform affine transform to embed (must be inversible
328 * otherwise the {@link
329 * org.apache.commons.math3.geometry.partitioning.Transform#apply(Hyperplane)
330 * apply(Hyperplane)} method would work only for some lines, and
331 * fail for other ones)
332 * @return a new transform that can be applied to either {@link
333 * Vector2D Vector2D}, {@link Line Line} or {@link
334 * org.apache.commons.math3.geometry.partitioning.SubHyperplane
335 * SubHyperplane} instances
336 * @exception MathIllegalArgumentException if the transform is non invertible
337 */
338 public static Transform<Euclidean2D, Euclidean1D> getTransform(final AffineTransform transform)
339 throws MathIllegalArgumentException {
340 return new LineTransform(transform);
341 }
342
343 /** Class embedding an affine transform.
344 * <p>This class is used in order to apply an affine transform to a
345 * line. Using a specific object allow to perform some computations
346 * on the transform only once even if the same transform is to be
347 * applied to a large number of lines (for example to a large
348 * polygon)./<p>
349 */
350 private static class LineTransform implements Transform<Euclidean2D, Euclidean1D> {
351
352 // CHECKSTYLE: stop JavadocVariable check
353 private double cXX;
354 private double cXY;
355 private double cX1;
356 private double cYX;
357 private double cYY;
358 private double cY1;
359
360 private double c1Y;
361 private double c1X;
362 private double c11;
363 // CHECKSTYLE: resume JavadocVariable check
364
365 /** Build an affine line transform from a n {@code AffineTransform}.
366 * @param transform transform to use (must be invertible otherwise
367 * the {@link LineTransform#apply(Hyperplane)} method would work
368 * only for some lines, and fail for other ones)
369 * @exception MathIllegalArgumentException if the transform is non invertible
370 */
371 public LineTransform(final AffineTransform transform) throws MathIllegalArgumentException {
372
373 final double[] m = new double[6];
374 transform.getMatrix(m);
375 cXX = m[0];
376 cXY = m[2];
377 cX1 = m[4];
378 cYX = m[1];
379 cYY = m[3];
380 cY1 = m[5];
381
382 c1Y = cXY * cY1 - cYY * cX1;
383 c1X = cXX * cY1 - cYX * cX1;
384 c11 = cXX * cYY - cYX * cXY;
385
386 if (FastMath.abs(c11) < 1.0e-20) {
387 throw new MathIllegalArgumentException(LocalizedFormats.NON_INVERTIBLE_TRANSFORM);
388 }
389
390 }
391
392 /** {@inheritDoc} */
393 public Vector2D apply(final Vector<Euclidean2D> point) {
394 final Vector2D p2D = (Vector2D) point;
395 final double x = p2D.getX();
396 final double y = p2D.getY();
397 return new Vector2D(cXX * x + cXY * y + cX1,
398 cYX * x + cYY * y + cY1);
399 }
400
401 /** {@inheritDoc} */
402 public Line apply(final Hyperplane<Euclidean2D> hyperplane) {
403 final Line line = (Line) hyperplane;
404 final double rOffset = c1X * line.cos + c1Y * line.sin + c11 * line.originOffset;
405 final double rCos = cXX * line.cos + cXY * line.sin;
406 final double rSin = cYX * line.cos + cYY * line.sin;
407 final double inv = 1.0 / FastMath.sqrt(rSin * rSin + rCos * rCos);
408 return new Line(FastMath.PI + FastMath.atan2(-rSin, -rCos),
409 inv * rCos, inv * rSin,
410 inv * rOffset);
411 }
412
413 /** {@inheritDoc} */
414 public SubHyperplane<Euclidean1D> apply(final SubHyperplane<Euclidean1D> sub,
415 final Hyperplane<Euclidean2D> original,
416 final Hyperplane<Euclidean2D> transformed) {
417 final OrientedPoint op = (OrientedPoint) sub.getHyperplane();
418 final Line originalLine = (Line) original;
419 final Line transformedLine = (Line) transformed;
420 final Vector1D newLoc =
421 transformedLine.toSubSpace(apply(originalLine.toSpace(op.getLocation())));
422 return new OrientedPoint(newLoc, op.isDirect()).wholeHyperplane();
423 }
424
425 }
426
427 }