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 * https://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
18 /*
19 * This is not the original file distributed by the Apache Software Foundation
20 * It has been modified by the Hipparchus project
21 */
22 package org.hipparchus.geometry.euclidean.twod;
23
24 import org.hipparchus.exception.MathIllegalArgumentException;
25 import org.hipparchus.geometry.LocalizedGeometryFormats;
26 import org.hipparchus.geometry.euclidean.oned.Euclidean1D;
27 import org.hipparchus.geometry.euclidean.oned.IntervalsSet;
28 import org.hipparchus.geometry.euclidean.oned.OrientedPoint;
29 import org.hipparchus.geometry.euclidean.oned.SubOrientedPoint;
30 import org.hipparchus.geometry.euclidean.oned.Vector1D;
31 import org.hipparchus.geometry.partitioning.Embedding;
32 import org.hipparchus.geometry.partitioning.Hyperplane;
33 import org.hipparchus.geometry.partitioning.RegionFactory;
34 import org.hipparchus.geometry.partitioning.Transform;
35 import org.hipparchus.util.FastMath;
36 import org.hipparchus.util.MathArrays;
37 import org.hipparchus.util.MathUtils;
38 import org.hipparchus.util.SinCos;
39
40 /** This class represents an oriented line in the 2D plane.
41
42 * <p>An oriented line can be defined either by prolongating a line
43 * segment between two points past these points, or by one point and
44 * an angular direction (in trigonometric orientation).</p>
45
46 * <p>Since it is oriented the two half planes at its two sides are
47 * unambiguously identified as a left half plane and a right half
48 * plane. This can be used to identify the interior and the exterior
49 * in a simple way by local properties only when part of a line is
50 * used to define part of a polygon boundary.</p>
51
52 * <p>A line can also be used to completely define a reference frame
53 * in the plane. It is sufficient to select one specific point in the
54 * line (the orthogonal projection of the original reference frame on
55 * the line) and to use the unit vector in the line direction and the
56 * orthogonal vector oriented from left half plane to right half
57 * plane. We define two coordinates by the process, the
58 * <em>abscissa</em> along the line, and the <em>offset</em> across
59 * the line. All points of the plane are uniquely identified by these
60 * two coordinates. The line is the set of points at zero offset, the
61 * left half plane is the set of points with negative offsets and the
62 * right half plane is the set of points with positive offsets.</p>
63
64 */
65 public class Line
66 implements Hyperplane<Euclidean2D, Vector2D, Line, SubLine>,
67 Embedding<Euclidean2D, Vector2D, Euclidean1D, Vector1D> {
68
69 /** Angle with respect to the abscissa axis. */
70 private double angle;
71
72 /** Cosine of the line angle. */
73 private double cos;
74
75 /** Sine of the line angle. */
76 private double sin;
77
78 /** Offset of the frame origin. */
79 private double originOffset;
80
81 /** Tolerance below which points are considered identical. */
82 private final double tolerance;
83
84 /** Reverse line. */
85 private Line reverse;
86
87 /** Build a line from two points.
88 * <p>The line is oriented from p1 to p2</p>
89 * @param p1 first point
90 * @param p2 second point
91 * @param tolerance tolerance below which points are considered identical
92 */
93 public Line(final Vector2D p1, final Vector2D p2, final double tolerance) {
94 reset(p1, p2);
95 this.tolerance = tolerance;
96 }
97
98 /** Build a line from a point and an angle.
99 * @param p point belonging to the line
100 * @param angle angle of the line with respect to abscissa axis
101 * @param tolerance tolerance below which points are considered identical
102 */
103 public Line(final Vector2D p, final double angle, final double tolerance) {
104 reset(p, angle);
105 this.tolerance = tolerance;
106 }
107
108 /** Build a line from its internal characteristics.
109 * @param angle angle of the line with respect to abscissa axis
110 * @param cos cosine of the angle
111 * @param sin sine of the angle
112 * @param originOffset offset of the origin
113 * @param tolerance tolerance below which points are considered identical
114 */
115 private Line(final double angle, final double cos, final double sin,
116 final double originOffset, final double tolerance) {
117 this.angle = angle;
118 this.cos = cos;
119 this.sin = sin;
120 this.originOffset = originOffset;
121 this.tolerance = tolerance;
122 this.reverse = null;
123 }
124
125 /** Copy constructor.
126 * <p>The created instance is completely independent of the
127 * original instance, it is a deep copy.</p>
128 * @param line line to copy
129 */
130 public Line(final Line line) {
131 angle = MathUtils.normalizeAngle(line.angle, FastMath.PI);
132 cos = line.cos;
133 sin = line.sin;
134 originOffset = line.originOffset;
135 tolerance = line.tolerance;
136 reverse = null;
137 }
138
139 /** {@inheritDoc} */
140 @Override
141 public Line copySelf() {
142 return new Line(this);
143 }
144
145 /** Reset the instance as if built from two points.
146 * <p>The line is oriented from p1 to p2</p>
147 * @param p1 first point
148 * @param p2 second point
149 */
150 public void reset(final Vector2D p1, final Vector2D p2) {
151 unlinkReverse();
152 final double dx = p2.getX() - p1.getX();
153 final double dy = p2.getY() - p1.getY();
154 final double d = FastMath.hypot(dx, dy);
155 if (d == 0.0) {
156 angle = 0.0;
157 cos = 1.0;
158 sin = 0.0;
159 originOffset = p1.getY();
160 } else {
161 angle = FastMath.PI + FastMath.atan2(-dy, -dx);
162 cos = dx / d;
163 sin = dy / d;
164 originOffset = MathArrays.linearCombination(p2.getX(), p1.getY(), -p1.getX(), p2.getY()) / d;
165 }
166 }
167
168 /** Reset the instance as if built from a line and an angle.
169 * @param p point belonging to the line
170 * @param alpha angle of the line with respect to abscissa axis
171 */
172 public void reset(final Vector2D p, final double alpha) {
173 unlinkReverse();
174 final SinCos sinCos = FastMath.sinCos(alpha);
175 this.angle = MathUtils.normalizeAngle(alpha, FastMath.PI);
176 cos = sinCos.cos();
177 sin = sinCos.sin();
178 originOffset = MathArrays.linearCombination(cos, p.getY(), -sin, p.getX());
179 }
180
181 /** Revert the instance.
182 */
183 public void revertSelf() {
184 unlinkReverse();
185 if (angle < FastMath.PI) {
186 angle += FastMath.PI;
187 } else {
188 angle -= FastMath.PI;
189 }
190 cos = -cos;
191 sin = -sin;
192 originOffset = -originOffset;
193 }
194
195 /** Unset the link between an instance and its reverse.
196 */
197 private void unlinkReverse() {
198 if (reverse != null) {
199 reverse.reverse = null;
200 }
201 reverse = null;
202 }
203
204 /** Get the reverse of the instance.
205 * <p>Get a line with reversed orientation with respect to the
206 * instance.</p>
207 * <p>
208 * As long as neither the instance nor its reverse are modified
209 * (i.e. as long as none of the {@link #reset(Vector2D, Vector2D)},
210 * {@link #reset(Vector2D, double)}, {@link #revertSelf()},
211 * {@link #setAngle(double)} or {@link #setOriginOffset(double)}
212 * methods are called), then the line and its reverse remain linked
213 * together so that {@code line.getReverse().getReverse() == line}.
214 * When one of the line is modified, the link is deleted as both
215 * instance becomes independent.
216 * </p>
217 * @return a new line, with orientation opposite to the instance orientation
218 */
219 public Line getReverse() {
220 if (reverse == null) {
221 reverse = new Line((angle < FastMath.PI) ? (angle + FastMath.PI) : (angle - FastMath.PI),
222 -cos, -sin, -originOffset, tolerance);
223 reverse.reverse = this;
224 }
225 return reverse;
226 }
227
228 /** {@inheritDoc} */
229 @Override
230 public Vector1D toSubSpace(final Vector2D point) {
231 return new Vector1D(MathArrays.linearCombination(cos, point.getX(), sin, point.getY()));
232 }
233
234 /** {@inheritDoc} */
235 @Override
236 public Vector2D toSpace(final Vector1D point) {
237 final double abscissa = point.getX();
238 return new Vector2D(MathArrays.linearCombination(abscissa, cos, -originOffset, sin),
239 MathArrays.linearCombination(abscissa, sin, originOffset, cos));
240 }
241
242 /** Get the intersection point of the instance and another line.
243 * @param other other line
244 * @return intersection point of the instance and the other line
245 * or null if there are no intersection points
246 */
247 public Vector2D intersection(final Line other) {
248 final double d = MathArrays.linearCombination(sin, other.cos, -other.sin, cos);
249 if (FastMath.abs(d) < tolerance) {
250 return null;
251 }
252 return new Vector2D(MathArrays.linearCombination(cos, other.originOffset, -other.cos, originOffset) / d,
253 MathArrays.linearCombination(sin, other.originOffset, -other.sin, originOffset) / d);
254 }
255
256 /** {@inheritDoc}
257 */
258 @Override
259 public Vector2D project(Vector2D point) {
260 return toSpace(toSubSpace(point));
261 }
262
263 /** {@inheritDoc}
264 */
265 @Override
266 public double getTolerance() {
267 return tolerance;
268 }
269
270 /** {@inheritDoc} */
271 @Override
272 public SubLine wholeHyperplane() {
273 return new SubLine(this, new IntervalsSet(tolerance));
274 }
275
276 /** {@inheritDoc} */
277 @Override
278 public SubLine emptyHyperplane() {
279 final RegionFactory<Euclidean1D, Vector1D, OrientedPoint, SubOrientedPoint> factory = new RegionFactory<>();
280 return new SubLine(this, factory.getComplement(new IntervalsSet(tolerance)));
281 }
282
283 /** Build a region covering the whole space.
284 * @return a region containing the instance (really a {@link
285 * PolygonsSet PolygonsSet} instance)
286 */
287 @Override
288 public PolygonsSet wholeSpace() {
289 return new PolygonsSet(tolerance);
290 }
291
292 /** Get the offset (oriented distance) of a parallel line.
293 * <p>This method should be called only for parallel lines otherwise
294 * the result is not meaningful.</p>
295 * <p>The offset is 0 if both lines are the same, it is
296 * positive if the line is on the right side of the instance and
297 * negative if it is on the left side, according to its natural
298 * orientation.</p>
299 * @param line line to check
300 * @return offset of the line
301 */
302 public double getOffset(final Line line) {
303 return originOffset +
304 (MathArrays.linearCombination(cos, line.cos, sin, line.sin) > 0 ? -line.originOffset : line.originOffset);
305 }
306
307 /** {@inheritDoc} */
308 @Override
309 public double getOffset(final Vector2D point) {
310 return MathArrays.linearCombination(sin, point.getX(), -cos, point.getY(), 1.0, originOffset);
311 }
312
313 /** {@inheritDoc} */
314 @Override
315 public Vector2D moveToOffset(final Vector2D point, final double offset) {
316 final double delta = offset - getOffset(point);
317 return new Vector2D(point.getX() + delta * sin, point.getY() - delta * cos);
318 }
319
320 /** {@inheritDoc} */
321 @Override
322 public Vector2D arbitraryPoint() {
323 return getPointAt(Vector1D.ZERO, 0);
324 }
325
326 /** {@inheritDoc} */
327 @Override
328 public boolean sameOrientationAs(final Line other) {
329 return MathArrays.linearCombination(sin, other.sin, cos, other.cos) >= 0.0;
330 }
331
332 /** Get one point from the plane.
333 * @param abscissa desired abscissa for the point
334 * @param offset desired offset for the point
335 * @return one point in the plane, with given abscissa and offset
336 * relative to the line
337 */
338 public Vector2D getPointAt(final Vector1D abscissa, final double offset) {
339 final double x = abscissa.getX();
340 final double dOffset = offset - originOffset;
341 return new Vector2D(MathArrays.linearCombination(x, cos, dOffset, sin),
342 MathArrays.linearCombination(x, sin, -dOffset, cos));
343 }
344
345 /** Check if the line contains a point.
346 * @param p point to check
347 * @return true if p belongs to the line
348 */
349 public boolean contains(final Vector2D p) {
350 return FastMath.abs(getOffset(p)) < tolerance;
351 }
352
353 /** Compute the distance between the instance and a point.
354 * <p>This is a shortcut for invoking FastMath.abs(getOffset(p)),
355 * and provides consistency with what is in the
356 * org.hipparchus.geometry.euclidean.threed.Line class.</p>
357 *
358 * @param p to check
359 * @return distance between the instance and the point
360 */
361 public double distance(final Vector2D p) {
362 return FastMath.abs(getOffset(p));
363 }
364
365 /** Check the instance is parallel to another line.
366 * @param line other line to check
367 * @return true if the instance is parallel to the other line
368 * (they can have either the same or opposite orientations)
369 */
370 public boolean isParallelTo(final Line line) {
371 return FastMath.abs(MathArrays.linearCombination(sin, line.cos, -cos, line.sin)) < tolerance;
372 }
373
374 /** Translate the line to force it passing by a point.
375 * @param p point by which the line should pass
376 */
377 public void translateToPoint(final Vector2D p) {
378 originOffset = MathArrays.linearCombination(cos, p.getY(), -sin, p.getX());
379 }
380
381 /** Get the angle of the line.
382 * @return the angle of the line with respect to the abscissa axis
383 */
384 public double getAngle() {
385 return MathUtils.normalizeAngle(angle, FastMath.PI);
386 }
387
388 /** Set the angle of the line.
389 * @param angle new angle of the line with respect to the abscissa axis
390 */
391 public void setAngle(final double angle) {
392 unlinkReverse();
393 this.angle = MathUtils.normalizeAngle(angle, FastMath.PI);
394 final SinCos sinCos = FastMath.sinCos(this.angle);
395 cos = sinCos.cos();
396 sin = sinCos.sin();
397 }
398
399 /** Get the offset of the origin.
400 * @return the offset of the origin
401 */
402 public double getOriginOffset() {
403 return originOffset;
404 }
405
406 /** Set the offset of the origin.
407 * @param offset offset of the origin
408 */
409 public void setOriginOffset(final double offset) {
410 unlinkReverse();
411 originOffset = offset;
412 }
413
414 /** Get a {@link org.hipparchus.geometry.partitioning.Transform
415 * Transform} embedding an affine transform.
416 * @param cXX transform factor between input abscissa and output abscissa
417 * @param cYX transform factor between input abscissa and output ordinate
418 * @param cXY transform factor between input ordinate and output abscissa
419 * @param cYY transform factor between input ordinate and output ordinate
420 * @param cX1 transform addendum for output abscissa
421 * @param cY1 transform addendum for output ordinate
422 * @return a new transform that can be applied to either {@link
423 * Vector2D Vector2D}, {@link Line Line} or {@link
424 * org.hipparchus.geometry.partitioning.SubHyperplane
425 * SubHyperplane} instances
426 * @exception MathIllegalArgumentException if the transform is non invertible
427 */
428 public static Transform<Euclidean2D, Vector2D, Line, SubLine,
429 Euclidean1D, Vector1D, OrientedPoint, SubOrientedPoint> getTransform(final double cXX,
430 final double cYX,
431 final double cXY,
432 final double cYY,
433 final double cX1,
434 final double cY1)
435 throws MathIllegalArgumentException {
436 return new LineTransform(cXX, cYX, cXY, cYY, cX1, cY1);
437 }
438
439 /** Class embedding an affine transform.
440 * <p>This class is used in order to apply an affine transform to a
441 * line. Using a specific object allow to perform some computations
442 * on the transform only once even if the same transform is to be
443 * applied to a large number of lines (for example to a large
444 * polygon)./<p>
445 */
446 private static class LineTransform
447 implements Transform<Euclidean2D, Vector2D, Line, SubLine, Euclidean1D, Vector1D, OrientedPoint, SubOrientedPoint> {
448
449 /** Transform factor between input abscissa and output abscissa. */
450 private final double cXX;
451
452 /** Transform factor between input abscissa and output ordinate. */
453 private final double cYX;
454
455 /** Transform factor between input ordinate and output abscissa. */
456 private final double cXY;
457
458 /** Transform factor between input ordinate and output ordinate. */
459 private final double cYY;
460
461 /** Transform addendum for output abscissa. */
462 private final double cX1;
463
464 /** Transform addendum for output ordinate. */
465 private final double cY1;
466
467 /** cXY * cY1 - cYY * cX1. */
468 private final double c1Y;
469
470 /** cXX * cY1 - cYX * cX1. */
471 private final double c1X;
472
473 /** cXX * cYY - cYX * cXY. */
474 private final double c11;
475
476 /** Build an affine line transform from a n {@code AffineTransform}.
477 * @param cXX transform factor between input abscissa and output abscissa
478 * @param cYX transform factor between input abscissa and output ordinate
479 * @param cXY transform factor between input ordinate and output abscissa
480 * @param cYY transform factor between input ordinate and output ordinate
481 * @param cX1 transform addendum for output abscissa
482 * @param cY1 transform addendum for output ordinate
483 * @exception MathIllegalArgumentException if the transform is non invertible
484 */
485 LineTransform(final double cXX, final double cYX, final double cXY,
486 final double cYY, final double cX1, final double cY1)
487 throws MathIllegalArgumentException {
488
489 this.cXX = cXX;
490 this.cYX = cYX;
491 this.cXY = cXY;
492 this.cYY = cYY;
493 this.cX1 = cX1;
494 this.cY1 = cY1;
495
496 c1Y = MathArrays.linearCombination(cXY, cY1, -cYY, cX1);
497 c1X = MathArrays.linearCombination(cXX, cY1, -cYX, cX1);
498 c11 = MathArrays.linearCombination(cXX, cYY, -cYX, cXY);
499
500 if (FastMath.abs(c11) < 1.0e-20) {
501 throw new MathIllegalArgumentException(LocalizedGeometryFormats.NON_INVERTIBLE_TRANSFORM);
502 }
503
504 }
505
506 /** {@inheritDoc} */
507 @Override
508 public Vector2D apply(final Vector2D point) {
509 final double x = point.getX();
510 final double y = point.getY();
511 return new Vector2D(MathArrays.linearCombination(cXX, x, cXY, y, cX1, 1),
512 MathArrays.linearCombination(cYX, x, cYY, y, cY1, 1));
513 }
514
515 /** {@inheritDoc} */
516 @Override
517 public Line apply(final Line hyperplane) {
518 final double rOffset = MathArrays.linearCombination(c1X, hyperplane.cos, c1Y, hyperplane.sin, c11, hyperplane.originOffset);
519 final double rCos = MathArrays.linearCombination(cXX, hyperplane.cos, cXY, hyperplane.sin);
520 final double rSin = MathArrays.linearCombination(cYX, hyperplane.cos, cYY, hyperplane.sin);
521 final double inv = 1.0 / FastMath.sqrt(rSin * rSin + rCos * rCos);
522 return new Line(FastMath.PI + FastMath.atan2(-rSin, -rCos),
523 inv * rCos, inv * rSin,
524 inv * rOffset, hyperplane.tolerance);
525 }
526
527 /** {@inheritDoc} */
528 @Override
529 public SubOrientedPoint apply(final SubOrientedPoint sub, final Line original, final Line transformed) {
530 final OrientedPoint op = sub.getHyperplane();
531 final Vector1D newLoc = transformed.toSubSpace(apply(original.toSpace(op.getLocation())));
532 return new OrientedPoint(newLoc, op.isDirect(), original.tolerance).wholeHyperplane();
533 }
534
535 }
536
537 }