View Javadoc
1   package org.djutils.draw.point;
2   
3   import java.awt.geom.Point2D;
4   import java.util.ArrayList;
5   import java.util.Arrays;
6   import java.util.Iterator;
7   import java.util.List;
8   import java.util.Locale;
9   
10  import org.djutils.draw.DrawRuntimeException;
11  import org.djutils.draw.Drawable2d;
12  import org.djutils.draw.bounds.Bounds2d;
13  import org.djutils.draw.line.LineSegment2d;
14  import org.djutils.exceptions.Throw;
15  
16  /**
17   * A Point2d is an immutable Point with an x and y coordinate, stored with double precision. It differs from many Point
18   * implementations by being immutable.
19   * <p>
20   * Copyright (c) 2020-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
21   * BSD-style license. See <a href="https://djutils.org/docs/current/djutils/licenses.html">DJUTILS License</a>.
22   * </p>
23   * @author <a href="https://www.tudelft.nl/averbraeck">Alexander Verbraeck</a>
24   * @author <a href="https://www.tudelft.nl/pknoppers">Peter Knoppers</a>
25   */
26  public class Point2d implements Drawable2d, Point<Point2d>
27  {
28      /** */
29      private static final long serialVersionUID = 20201201L;
30  
31      /** The x-coordinate. */
32      @SuppressWarnings("checkstyle:visibilitymodifier")
33      public final double x;
34  
35      /** The y-coordinate. */
36      @SuppressWarnings("checkstyle:visibilitymodifier")
37      public final double y;
38  
39      /**
40       * Create a new Point2d from x and y coordinates provided as double arguments.
41       * @param x double; the x coordinate
42       * @param y double; the y coordinate
43       * @throws IllegalArgumentException when x or y is NaN
44       */
45      public Point2d(final double x, final double y) throws IllegalArgumentException
46      {
47          Throw.when(Double.isNaN(x) || Double.isNaN(y), IllegalArgumentException.class, "Coordinate must be a number (not NaN)");
48          this.x = x;
49          this.y = y;
50      }
51  
52      /**
53       * Create a new Point2d from a x and y coordinates provided as values in a double array.
54       * @param xy double[]; the x and y coordinates
55       * @throws NullPointerException when xy is null
56       * @throws IllegalArgumentException when the length of xy is not 2, or a coordinate is NaN
57       */
58      public Point2d(final double[] xy) throws NullPointerException, IllegalArgumentException
59      {
60          this(checkLengthIsTwo(Throw.whenNull(xy, "xy"))[0], xy[1]);
61      }
62  
63      /**
64       * Create an new Point2d from x and y obtained from a java.awt.geom.Point2D.
65       * @param point Point2D; a java.awt.geom.Point2D
66       * @throws NullPointerException when point is null
67       * @throws IllegalArgumentException when point has a NaN coordinate
68       */
69      public Point2d(final Point2D point) throws NullPointerException, IllegalArgumentException
70      {
71          Throw.whenNull(point, "point");
72          Throw.when(Double.isNaN(point.getX()) || Double.isNaN(point.getY()), IllegalArgumentException.class,
73                  "Coordinate must be a number (not NaN)");
74          this.x = point.getX();
75          this.y = point.getY();
76      }
77  
78      /**
79       * Throw an IllegalArgumentException if the length of the provided array is not two.
80       * @param xy double[]; the provided array
81       * @return double[]; the provided array
82       * @throws IllegalArgumentException when length of xy is not two
83       */
84      private static double[] checkLengthIsTwo(final double[] xy) throws IllegalArgumentException
85      {
86          Throw.when(xy.length != 2, IllegalArgumentException.class, "Length of xy-array must be 2");
87          return xy;
88      }
89  
90      @Override
91      public final double getX()
92      {
93          return this.x;
94      }
95  
96      @Override
97      public final double getY()
98      {
99          return this.y;
100     }
101 
102     @Override
103     public double distance(final Point2d otherPoint)
104     {
105         Throw.whenNull(otherPoint, "otherPoint");
106         return Math.hypot(otherPoint.x - this.x, otherPoint.y - this.y);
107     }
108 
109     @Override
110     public double distanceSquared(final Point2d otherPoint) throws NullPointerException
111     {
112         Throw.whenNull(otherPoint, "otherPoint");
113         double dx = this.x - otherPoint.x;
114         double dy = this.y - otherPoint.y;
115         return dx * dx + dy * dy;
116     }
117 
118     @Override
119     public int size()
120     {
121         return 1;
122     }
123 
124     @Override
125     public Iterator<? extends Point2d> getPoints()
126     {
127         return Arrays.stream(new Point2d[] {this}).iterator();
128     }
129 
130     /**
131      * Return a new Point2d with a translation by the provided dx and dy.
132      * @param dx double; the x translation
133      * @param dy double; the y translation
134      * @return P; a new point with the translated coordinates
135      * @throws IllegalArgumentException when dx, or dy is NaN
136      */
137     public Point2d translate(final double dx, final double dy)
138     {
139         Throw.when(Double.isNaN(dx) || Double.isNaN(dy), IllegalArgumentException.class, "translation may not be NaN");
140         return new Point2d(this.x + dx, this.y + dy);
141     }
142 
143     /**
144      * Return a new Point3d with a translation by the provided dx, dy and dz. If this is an OrientedPoint2d, then the result is
145      * an OrientedPoint3d with rotX copied from this and rotY and rotZ are set to 0.0.
146      * @param dx double; the x translation
147      * @param dy double; the y translation
148      * @param dz double; the z translation
149      * @return Point2d; a new point with the translated coordinates
150      * @throws IllegalArgumentException when dx, dy, or dz is NaN
151      */
152     public Point3d translate(final double dx, final double dy, final double dz)
153     {
154         Throw.when(Double.isNaN(dx) || Double.isNaN(dy) || Double.isNaN(dz), IllegalArgumentException.class,
155                 "translation may not be NaN");
156         return new Point3d(this.x + dx, this.y + dy, dz);
157     }
158 
159     @Override
160     public Point2d scale(final double factor)
161     {
162         Throw.when(Double.isNaN(factor), IllegalArgumentException.class, "factor must be a number (not NaN)");
163         return new Point2d(this.x * factor, this.y * factor);
164     }
165 
166     @Override
167     public Point2d neg()
168     {
169         return scale(-1.0);
170     }
171 
172     @Override
173     public Point2d abs()
174     {
175         return new Point2d(Math.abs(this.x), Math.abs(this.y));
176     }
177 
178     @Override
179     public Point2d normalize() throws DrawRuntimeException
180     {
181         double length = Math.sqrt(this.x * this.x + this.y * this.y);
182         Throw.when(length == 0.0, DrawRuntimeException.class, "cannot normalize (0.0, 0.0)");
183         return this.scale(1.0 / length);
184     }
185 
186     @Override
187     public Point2d interpolate(final Point2d otherPoint, final double fraction)
188     {
189         Throw.whenNull(otherPoint, "otherPoint");
190         Throw.when(Double.isNaN(fraction), IllegalArgumentException.class, "fraction must be a number (not NaN)");
191         return new Point2d((1.0 - fraction) * this.x + fraction * otherPoint.x,
192                 (1.0 - fraction) * this.y + fraction * otherPoint.y);
193     }
194 
195     @Override
196     public boolean epsilonEquals(final Point2d otherPoint, final double epsilon)
197     {
198         Throw.whenNull(otherPoint, "otherPoint");
199         if (Math.abs(this.x - otherPoint.x) > epsilon)
200         {
201             return false;
202         }
203         if (Math.abs(this.y - otherPoint.y) > epsilon)
204         {
205             return false;
206         }
207         return true;
208     }
209 
210     @Override
211     public Bounds2d getBounds()
212     {
213         return new Bounds2d(this);
214     }
215 
216     /**
217      * Compute the 2D intersection of two lines. Both lines are defined by two points (that should be distinct).
218      * @param line1P1X double; x-coordinate of start point of line 1
219      * @param line1P1Y double; y-coordinate of start point of line 1
220      * @param line1P2X double; x-coordinate of end point of line 1
221      * @param line1P2Y double; y-coordinate of end point of line 1
222      * @param lowLimitLine1 boolean; if true; the intersection may not lie before the start point of line 1
223      * @param highLimitLine1 boolean; if true; the intersection may not lie beyond the end point of line 1
224      * @param line2P1X double; x-coordinate of start point of line 2
225      * @param line2P1Y double; y-coordinate of start point of line 2
226      * @param line2P2X double; x-coordinate of end point of line 2
227      * @param line2P2Y double; y-coordinate of end point of line 2
228      * @param lowLimitLine2 boolean; if true; the intersection may not lie before the start point of line 2
229      * @param highLimitLine2 boolean; if true; the intersection may not lie beyond the end point of line 2
230      * @return Point2d; the intersection of the two lines, or null if the lines are (almost) parallel, or the intersection point
231      *         lies outside the permitted range
232      * @throws DrawRuntimeException when any of the parameters is NaN
233      */
234     @SuppressWarnings("checkstyle:parameternumber")
235     public static Point2d intersectionOfLines(final double line1P1X, final double line1P1Y, final double line1P2X,
236             final double line1P2Y, final boolean lowLimitLine1, final boolean highLimitLine1, final double line2P1X,
237             final double line2P1Y, final double line2P2X, final double line2P2Y, final boolean lowLimitLine2,
238             final boolean highLimitLine2) throws DrawRuntimeException
239     {
240         double line1DX = line1P2X - line1P1X;
241         double line1DY = line1P2Y - line1P1Y;
242         double l2p1x = line2P1X - line1P1X;
243         double l2p1y = line2P1Y - line1P1Y;
244         double l2p2x = line2P2X - line1P1X;
245         double l2p2y = line2P2Y - line1P1Y;
246         double denominator = (l2p2y - l2p1y) * line1DX - (l2p2x - l2p1x) * line1DY;
247         Throw.when(Double.isNaN(denominator), DrawRuntimeException.class, "NaN value not permitted");
248         if (denominator == 0.0)
249         {
250             return null; // lines are parallel (they might even be on top of each other, but we don't check that)
251         }
252         double uA = ((l2p2x - l2p1x) * (-l2p1y) - (l2p2y - l2p1y) * (-l2p1x)) / denominator;
253         // System.out.println("uA is " + uA);
254         if (uA < 0.0 && lowLimitLine1 || uA > 1.0 && highLimitLine1)
255         {
256             return null; // intersection outside line 1
257         }
258         double uB = (line1DY * l2p1x - line1DX * l2p1y) / denominator;
259         // System.out.println("uB is " + uB);
260         if (uB < 0.0 && lowLimitLine2 || uB > 1.0 && highLimitLine2)
261         {
262             return null; // intersection outside line 2
263         }
264         if (uA == 1.0) // maximize precision
265         {
266             return new Point2d(line1P2X, line1P2Y);
267         }
268         if (uB == 0.0)
269         {
270             return new Point2d(line2P1X, line2P1Y);
271         }
272         if (uB == 1.0)
273         {
274             return new Point2d(line2P2X, line2P2Y);
275         }
276         return new Point2d(line1P1X + uA * line1DX, line1P1Y + uA * line1DY);
277     }
278 
279     /**
280      * Compute the 2D intersection of two lines. Both lines are defined by two points (that should be distinct). The lines are
281      * considered to be infinitely long; so unless the lines are parallel; there is an intersection.
282      * @param l1P1X double; x-coordinate of start point of line segment 1
283      * @param l1P1Y double; y-coordinate of start point of line segment 1
284      * @param l1P2X double; x-coordinate of end point of line segment 1
285      * @param l1P2Y double; y-coordinate of end point of line segment 1
286      * @param l2P1X double; x-coordinate of start point of line segment 2
287      * @param l2P1Y double; y-coordinate of start point of line segment 2
288      * @param l2P2X double; x-coordinate of end point of line segment 2
289      * @param l2P2Y double; y-coordinate of end point of line segment 2
290      * @return Point2d; the intersection of the two lines, or null if the lines are (almost) parallel
291      * @throws DrawRuntimeException when any of the parameters is NaN
292      */
293     @SuppressWarnings("checkstyle:parameternumber")
294     public static Point2d intersectionOfLines(final double l1P1X, final double l1P1Y, final double l1P2X, final double l1P2Y,
295             final double l2P1X, final double l2P1Y, final double l2P2X, final double l2P2Y) throws DrawRuntimeException
296     {
297         return intersectionOfLines(l1P1X, l1P1Y, l1P2X, l1P2Y, false, false, l2P1X, l2P1Y, l2P2X, l2P2Y, false, false);
298     }
299 
300     /**
301      * Compute the 2D intersection of two lines. Both lines are defined by two points (that should be distinct). The lines are
302      * considered to be infinitely long; so unless the lines are parallel; there is an intersection.
303      * @param line1P1 Point2d; first point of line 1
304      * @param line1P2 Point2d; second point of line 1
305      * @param line2P1 Point2d; first point of line 2
306      * @param line2P2 Point2d; second point of line 2
307      * @return Point2d; the intersection of the two lines, or null if the lines are (almost) parallel
308      * @throws NullPointerException when any of the points is null
309      */
310     public static Point2d intersectionOfLines(final Point2d line1P1, final Point2d line1P2, final Point2d line2P1,
311             final Point2d line2P2) throws NullPointerException
312     {
313         Throw.when(line1P1 == null || line1P2 == null || line2P1 == null || line2P2 == null, NullPointerException.class,
314                 "Points may not be null");
315         return intersectionOfLines(line1P1.x, line1P1.y, line1P2.x, line1P2.y, false, false, line2P1.x, line2P1.y, line2P2.x,
316                 line2P2.y, false, false);
317     }
318 
319     /**
320      * Compute the 2D intersection of two line segments. Both line segments are defined by two points (that should be distinct).
321      * @param line1P1 Point2d; first point of line segment 1
322      * @param line1P2 Point2d; second point of line segment 1
323      * @param line2P1 Point2d; first point of line segment 2
324      * @param line2P2 Point2d; second point of line segment 2
325      * @return Point2d; the intersection of the two line segments, or null if the lines are parallel (within rounding error), or
326      *         do not intersect
327      * @throws NullPointerException when any of the points is null
328      * @throws DrawRuntimeException when any of the line segments is ill-defined (begin point equals end point), or the two line
329      *             segments are parallel or overlapping
330      */
331     public static Point2d intersectionOfLineSegments(final Point2d line1P1, final Point2d line1P2, final Point2d line2P1,
332             final Point2d line2P2) throws NullPointerException, DrawRuntimeException
333     {
334         Throw.when(line1P1 == null || line1P2 == null || line2P1 == null || line2P2 == null, NullPointerException.class,
335                 "Points may not be null");
336         return intersectionOfLines(line1P1.x, line1P1.y, line1P2.x, line1P2.y, true, true, line2P1.x, line2P1.y, line2P2.x,
337                 line2P2.y, true, true);
338     }
339 
340     /**
341      * Compute the 2D intersection of two line segments. Both line segments are defined by two points (that should be distinct).
342      * @param line1P1X double; x coordinate of start point of first line segment
343      * @param line1P1Y double; y coordinate of start point of first line segment
344      * @param line1P2X double; x coordinate of end point of first line segment
345      * @param line1P2Y double; y coordinate of end point of first line segment
346      * @param line2P1X double; x coordinate of start point of second line segment
347      * @param line2P1Y double; y coordinate of start point of second line segment
348      * @param line2P2X double; x coordinate of end point of second line segment
349      * @param line2P2Y double; y coordinate of end point of second line segment
350      * @return Point2d; the intersection of the two line segments, or null if the lines are parallel (within rounding error), or
351      *         do not intersect
352      * @throws DrawRuntimeException when any of the values is NaN
353      */
354     @SuppressWarnings("checkstyle:parameternumber")
355     public static Point2d intersectionOfLineSegments(final double line1P1X, final double line1P1Y, final double line1P2X,
356             final double line1P2Y, final double line2P1X, final double line2P1Y, final double line2P2X, final double line2P2Y)
357             throws DrawRuntimeException
358     {
359         return intersectionOfLines(line1P1X, line1P1Y, line1P2X, line1P2Y, true, true, line2P1X, line2P1Y, line2P2X, line2P2Y,
360                 true, true);
361     }
362 
363     /**
364      * Compute the 2D intersection of two line segments.
365      * @param segment1 LineSegment; the first line segment
366      * @param segment2 LineSegment; the other line segment
367      * @return Point2d; the intersection of the line segments, or null if the line segments do not intersect
368      */
369     public static Point2d intersectionOfLineSegments(final LineSegment2d segment1, final LineSegment2d segment2)
370     {
371         return intersectionOfLineSegments(segment1.startX, segment1.startY, segment1.endX, segment1.endY, segment2.startX,
372                 segment2.startY, segment2.endX, segment2.endY);
373     }
374 
375     @Override
376     public Point2d closestPointOnSegment(final Point2d segmentPoint1, final Point2d segmentPoint2)
377     {
378         Throw.whenNull(segmentPoint1, "segmentPoint1");
379         Throw.whenNull(segmentPoint2, "segmentPoint2");
380         return closestPointOnSegment(segmentPoint1.x, segmentPoint1.y, segmentPoint2.x, segmentPoint2.y);
381     }
382 
383     /**
384      * Compute the closest point on a line with optional limiting of the result on either end.
385      * @param p1X double; the x coordinate of the first point on the line
386      * @param p1Y double; the y coordinate of the first point on the line
387      * @param p2X double; the x coordinate of the second point on the line
388      * @param p2Y double; the y coordinate of the second point on the line
389      * @param lowLimitHandling Boolean; controls handling of results that lie before the first point of the line. If null; this
390      *            method returns null; else if true; this method returns (p1X,p1Y); else (lowLimitHandling is false); this
391      *            method will return the closest point on the line
392      * @param highLimitHandling Boolean; controls the handling of results that lie beyond the second point of the line. If null;
393      *            this method returns null; else if true; this method returns (p2X,p2Y); else (highLimitHandling is false); this
394      *            method will return the closest point on the line
395      * @return Point2d; the closest point on the line after applying the indicated limit handling; so the result can be null
396      * @throws DrawRuntimeException when any of the arguments is NaN
397      */
398     public Point2d closestPointOnLine(final double p1X, final double p1Y, final double p2X, final double p2Y,
399             final Boolean lowLimitHandling, final Boolean highLimitHandling) throws DrawRuntimeException
400     {
401         double fraction = fractionalPositionOnLine(p1X, p1Y, p2X, p2Y, lowLimitHandling, highLimitHandling);
402         if (Double.isNaN(fraction))
403         {
404             return null;
405         }
406         if (fraction == 1.0)
407         {
408             return new Point2d(p2X, p2Y); // Maximize precision in case fraction == 1.0
409         }
410         return new Point2d(p1X + fraction * (p2X - p1X), p1Y + fraction * (p2Y - p1Y));
411     }
412 
413     /**
414      * Compute the fractional position of the closest point on a line with optional limiting of the result on either end. If the
415      * line has length 0; this method returns 0.0.
416      * @param p1X double; the x coordinate of the first point on the line
417      * @param p1Y double; the y coordinate of the first point on the line
418      * @param p2X double; the x coordinate of the second point on the line
419      * @param p2Y double; the y coordinate of the second point on the line
420      * @param lowLimitHandling Boolean; controls handling of results that lie before the first point of the line. If null; this
421      *            method returns NaN; else if true; this method returns 0.0; else (lowLimitHandling is false); this results &lt;
422      *            0.0 are returned
423      * @param highLimitHandling Boolean; controls the handling of results that lie beyond the second point of the line. If null;
424      *            this method returns NaN; else if true; this method returns 1.0; else (highLimitHandling is false); results
425      *            &gt; 1.0 are returned
426      * @return double; the fractional position of the closest point on the line. Results within the range 0.0 .. 1.0 are always
427      *         returned as is.. A result &lt; 0.0 is subject to lowLimitHandling. A result &gt; 1.0 is subject to
428      *         highLimitHandling
429      * @throws DrawRuntimeException when any of the arguments is NaN
430      */
431     public double fractionalPositionOnLine(final double p1X, final double p1Y, final double p2X, final double p2Y,
432             final Boolean lowLimitHandling, final Boolean highLimitHandling) throws DrawRuntimeException
433     {
434         double dX = p2X - p1X;
435         double dY = p2Y - p1Y;
436         Throw.when(Double.isNaN(dX) || Double.isNaN(dY), DrawRuntimeException.class, "NaN values not permitted");
437         if (0 == dX && 0 == dY)
438         {
439             return 0.0;
440         }
441         double fraction = ((this.x - p1X) * dX + (this.y - p1Y) * dY) / (dX * dX + dY * dY);
442         if (fraction < 0.0)
443         {
444             if (lowLimitHandling == null)
445             {
446                 return Double.NaN;
447             }
448             if (lowLimitHandling)
449             {
450                 fraction = 0.0;
451             }
452         }
453         else if (fraction > 1.0)
454         {
455             if (highLimitHandling == null)
456             {
457                 return Double.NaN;
458             }
459             if (highLimitHandling)
460             {
461                 fraction = 1.0;
462             }
463         }
464         return fraction;
465     }
466 
467     /**
468      * Project a point on a line segment. If the the projected points lies outside the line segment, the nearest end point of
469      * the line segment is returned. Otherwise the returned point lies between the end points of the line segment. <br>
470      * Adapted from <a href="http://paulbourke.net/geometry/pointlineplane/DistancePoint.java">example code provided by Paul
471      * Bourke</a>.
472      * @param p1X double; the x coordinate of the start point of the line segment
473      * @param p1Y double; the y coordinate of the start point of the line segment
474      * @param p2X double; the x coordinate of the end point of the line segment
475      * @param p2Y double; the y coordinate of the end point of the line segment
476      * @return P; either <cite>segmentPoint1</cite>, or <cite>segmentPoint2</cite> or a new Point2d that lies somewhere in
477      *         between those two.
478      */
479     public final Point2d closestPointOnSegment(final double p1X, final double p1Y, final double p2X, final double p2Y)
480     {
481         return closestPointOnLine(p1X, p1Y, p2X, p2Y, true, true);
482     }
483 
484     @Override
485     public Point2d closestPointOnLine(final Point2d linePoint1, final Point2d linePoint2)
486             throws NullPointerException, DrawRuntimeException
487     {
488         Throw.whenNull(linePoint1, "linePoint1");
489         Throw.whenNull(linePoint2, "linePoint2");
490         return closestPointOnLine(linePoint1.x, linePoint1.y, linePoint2.x, linePoint2.y);
491     }
492 
493     /**
494      * Project a point on a line. <br>
495      * Adapted from <a href="http://paulbourke.net/geometry/pointlineplane/DistancePoint.java">example code provided by Paul
496      * Bourke</a>.
497      * @param p1X double; the x coordinate of a point of the line segment
498      * @param p1Y double; the y coordinate of a point of the line segment
499      * @param p2X double; the x coordinate of another point of the line segment
500      * @param p2Y double; the y coordinate of another point of the line segment
501      * @return Point2d; a point on the line that goes through the points
502      * @throws DrawRuntimeException when the points on the line are identical
503      */
504     public final Point2d closestPointOnLine(final double p1X, final double p1Y, final double p2X, final double p2Y)
505             throws DrawRuntimeException
506     {
507         Throw.when(p1X == p2X && p1Y == p2Y, DrawRuntimeException.class, "degenerate line not allowed");
508         return closestPointOnLine(p1X, p1Y, p2X, p2Y, false, false);
509     }
510 
511     /**
512      * Return the zero, one or two intersections between two circles. The circles must be different. Derived from pseudo code by
513      * <a href="http://paulbourke.net/geometry/circlesphere/">Paul Bourke</a> and C implementation by
514      * <a href="http://paulbourke.net/geometry/circlesphere/tvoght.c">Tim Voght </a>.
515      * @param center1 Point2d; the center of circle 1
516      * @param radius1 double; the radius of circle 1
517      * @param center2 Point2d; the center of circle 2
518      * @param radius2 double; the radius of circle 2
519      * @return List&lt;Point2d&gt; a list of zero, one or two points
520      * @throws NullPointerException when center1 or center2 is null
521      * @throws DrawRuntimeException when the two circles are identical, or radius1 &lt; 0 or radius2 &lt; 0
522      */
523     public static final List<Point2d> circleIntersections(final Point2d center1, final double radius1, final Point2d center2,
524             final double radius2) throws NullPointerException, DrawRuntimeException
525     {
526         Throw.whenNull(center1, "center1");
527         Throw.whenNull(center2, "center2");
528         Throw.when(radius1 < 0 || radius2 < 0, DrawRuntimeException.class, "radius may not be less than 0");
529         Throw.when(center1.equals(center2) && radius1 == radius2, DrawRuntimeException.class, "Circles must be different");
530         List<Point2d> result = new ArrayList<>();
531         // dX,dY is the vector from center1 to center2
532         double dX = center2.x - center1.x;
533         double dY = center2.y - center1.y;
534         double distance = Math.hypot(dX, dY);
535         if (distance > radius1 + radius2 || distance < Math.abs(radius1 - radius2))
536         {
537             return result; // empty list
538         }
539         double a = (radius1 * radius1 - radius2 * radius2 + distance * distance) / (2 * distance);
540         // x2,y2 is the point where the line through the circle intersections crosses the line through the circle centers
541         double x2 = center1.x + (dX * a / distance);
542         double y2 = center1.y + (dY * a / distance);
543         // h is distance from x2,y2 to each of the solutions
544         double h = Math.sqrt(radius1 * radius1 - a * a);
545         // rX, rY is vector from x2,y2 to the first solution
546         double rX = -dY * (h / distance);
547         double rY = dX * (h / distance);
548         result.add(new Point2d(x2 + rX, y2 + rY));
549         if (h > 0)
550         {
551             // Two distinct solutions; add the second one
552             result.add(new Point2d(x2 - rX, y2 - rY));
553         }
554         return result;
555     }
556 
557     /**
558      * Return the direction to another Point2d.
559      * @param otherPoint Point2d; the other point
560      * @return double; the direction to the other point in Radians (towards infinite X is 0; towards infinite Y is &pi; / 2;
561      *         etc.). If the points are identical; this method returns NaN.
562      */
563     public double directionTo(final Point2d otherPoint)
564     {
565         return Math.atan2(otherPoint.y - this.y, otherPoint.x - this.x);
566     }
567 
568     /**
569      * Return the coordinates as a java.awt.geom.Point2D.Double object.
570      * @return Point2D; the coordinates as a java.awt.geom.Point2D.Double object
571      */
572     public Point2D toPoint2D()
573     {
574         return new Point2D.Double(this.x, this.y);
575     }
576 
577     @Override
578     public String toString()
579     {
580         return toString("%f");
581     }
582 
583     @Override
584     public String toString(final String doubleFormat, final boolean doNotIncludeClassName)
585     {
586         String format = String.format("%1$s[x=%2$s, y=%2$s]", doNotIncludeClassName ? "" : "Point2d ", doubleFormat);
587         return String.format(Locale.US, format, this.x, this.y);
588     }
589 
590     @Override
591     public int hashCode()
592     {
593         final int prime = 31;
594         int result = 1;
595         long temp;
596         temp = Double.doubleToLongBits(this.x);
597         result = prime * result + (int) (temp ^ (temp >>> 32));
598         temp = Double.doubleToLongBits(this.y);
599         result = prime * result + (int) (temp ^ (temp >>> 32));
600         return result;
601     }
602 
603     @SuppressWarnings("checkstyle:needbraces")
604     @Override
605     public boolean equals(final Object obj)
606     {
607         if (this == obj)
608             return true;
609         if (obj == null)
610             return false;
611         if (getClass() != obj.getClass())
612             return false;
613         Point2d other = (Point2d) obj;
614         if (Double.doubleToLongBits(this.x) != Double.doubleToLongBits(other.x))
615             return false;
616         if (Double.doubleToLongBits(this.y) != Double.doubleToLongBits(other.y))
617             return false;
618         return true;
619     }
620 
621 }