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