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