001package jmri.util;
002
003import java.awt.*;
004import java.awt.geom.*;
005import static java.lang.Float.NEGATIVE_INFINITY;
006import static java.lang.Float.POSITIVE_INFINITY;
007import static java.lang.Math.PI;
008import java.util.*;
009import java.util.List;
010
011import javax.annotation.*;
012
013/**
014 * Useful math methods.
015 *
016 * @author geowar Copyright 2017
017 */
018public final class MathUtil {
019
020    public static final Point2D zeroPoint2D = zeroPoint2D();
021    public static final Point2D infinityPoint2D = infinityPoint2D();
022    public static final Rectangle2D zeroRectangle2D = zeroRectangle2D();
023    public static final Rectangle2D zeroToInfinityRectangle2D = zeroToInfinityRectangle2D();
024    public static final Rectangle2D infinityRectangle2D = infinityRectangle2D();
025
026    /**
027     * Class only supplies static methods.
028     */
029    private MathUtil() {}
030
031    /**
032     * @return the point {0, 0}
033     */
034    @CheckReturnValue
035    public static Point2D zeroPoint2D() {
036        return new Point2D.Double(0, 0);
037    }
038
039    /**
040     * @return the point {POSITIVE_INFINITY, POSITIVE_INFINITY}
041     */
042    @CheckReturnValue
043    public static Point2D infinityPoint2D() {
044        return new Point2D.Double(POSITIVE_INFINITY, POSITIVE_INFINITY);
045    }
046
047    /**
048     * @param a the first number
049     * @param b the second number
050     * @return the greatest common divisor of a and b
051     */
052    public static int gcd(int a, int b) {
053        int result = b;
054        if (a != 0) {
055            result = gcd(b % a, a);
056        }
057        return result;
058    }
059
060    /**
061     * Convert Point to Point2D.
062     *
063     * @param p the Point
064     * @return the Point2D
065     */
066    @CheckReturnValue
067    public static Point2D pointToPoint2D(@Nonnull Point p) {
068        return new Point2D.Double(p.x, p.y);
069    }
070
071    /**
072     * Convert Point2D to Point.
073     *
074     * @param p the Point
075     * @return the Point2D
076     */
077    @CheckReturnValue
078    public static Point point2DToPoint(@Nonnull Point2D p) {
079        return new Point((int) p.getX(), (int) p.getY());
080    }
081
082    /**
083     * @param a the first float
084     * @param b the second float
085     * @return true if a is equal to b
086     */
087    public static boolean equals(float a, float b) {
088        return (Float.floatToIntBits(a) == Float.floatToIntBits(b));
089    }
090
091    /**
092     * @param a the first double
093     * @param b the second double
094     * @return true if a is equal to b
095     */
096    public static boolean equals(double a, double b) {
097        return (Double.doubleToLongBits(a) == Double.doubleToLongBits(b));
098    }
099
100    /**
101     * @param a the first Rectangle2D
102     * @param b the second Rectangle2D
103     * @return true if a is equal to b
104     */
105    public static boolean equals(Rectangle2D a, Rectangle2D b) {
106        return (equals(a.getMinX(), b.getMinX())
107                && equals(a.getMinY(), b.getMinY())
108                && equals(a.getWidth(), b.getWidth())
109                && equals(a.getHeight(), b.getHeight()));
110    }
111
112    /**
113     * @param a the first Point2D
114     * @param b the second Point2D
115     * @return true if a is equal to b
116     */
117    public static boolean equals(Point2D a, Point2D b) {
118        return (equals(a.getX(), b.getX()) && equals(a.getY(), b.getY()));
119    }
120
121    /**
122     * @param p the point
123     * @return true if p1 is equal to zeroPoint2D
124     */
125    public static boolean isEqualToZeroPoint2D(@Nonnull Point2D p) {
126        return p.equals(zeroPoint2D);
127    }
128
129    /**
130     * Get the minimum coordinates of two points.
131     *
132     * @param pA the first point
133     * @param pB the second point
134     * @return the minimum coordinates
135     */
136    @CheckReturnValue
137    public static Point2D min(@Nonnull Point2D pA, @Nonnull Point2D pB) {
138        return new Point2D.Double(Math.min(pA.getX(), pB.getX()), Math.min(pA.getY(), pB.getY()));
139    }
140
141    /**
142     * Get the maximum coordinates of two points.
143     *
144     * @param pA the first point
145     * @param pB the second point
146     * @return the maximum coordinates
147     */
148    @CheckReturnValue
149    public static Point2D max(@Nonnull Point2D pA, @Nonnull Point2D pB) {
150        return new Point2D.Double(Math.max(pA.getX(), pB.getX()), Math.max(pA.getY(), pB.getY()));
151    }
152
153    /**
154     * Get the coordinates of a point pinned between two other points.
155     *
156     * @param pA the first point
157     * @param pB the second point
158     * @param pC the third point
159     * @return the coordinates of pA pined between pB and pC
160     */
161    @CheckReturnValue
162    public static Point2D pin(@Nonnull Point2D pA, @Nonnull Point2D pB, @Nonnull Point2D pC) {
163        return min(max(pA, min(pB, pC)), max(pB, pC));
164    }
165
166    /**
167     * Get the coordinates of a point pinned in a rectangle
168     *
169     * @param pA the point
170     * @param pR the rectangle
171     * @return the coordinates of point pA pined in rectangle pR
172     */
173    @CheckReturnValue
174    public static Point2D pin(@Nonnull Point2D pA, @Nonnull Rectangle2D pR) {
175        return min(max(pA, getOrigin(pR)), offset(getOrigin(pR), pR.getWidth(), pR.getHeight()));
176    }
177
178    /**
179     * Add two points.
180     *
181     * @param pA the first point
182     * @param pB the second point
183     * @return the sum of the two points
184     */
185    @CheckReturnValue
186    public static Point2D add(@Nonnull Point2D pA, @Nonnull Point2D pB) {
187        return new Point2D.Double(pA.getX() + pB.getX(), pA.getY() + pB.getY());
188    }
189
190    /**
191     * Subtract two points.
192     *
193     * @param pA the first point
194     * @param pB the second point
195     * @return the difference of the two points
196     */
197    @CheckReturnValue
198    public static Point2D subtract(@Nonnull Point2D pA, @Nonnull Point2D pB) {
199        return new Point2D.Double(pA.getX() - pB.getX(), pA.getY() - pB.getY());
200    }
201
202    /**
203     * Multiply a point times a scalar.
204     *
205     * @param p the point
206     * @param s the scalar
207     * @return the point multiplied by the scalar
208     */
209    @CheckReturnValue
210    public static Point2D multiply(@Nonnull Point2D p, double s) {
211        return new Point2D.Double(p.getX() * s, p.getY() * s);
212    }
213
214    /**
215     * Multiply a point times two scalar.
216     *
217     * @param p the point
218     * @param x the X scalar
219     * @param y the Y scalar
220     * @return the point multiplied by the two scalars
221     */
222    @CheckReturnValue
223    public static Point2D multiply(@Nonnull Point2D p, double x, double y) {
224        return new Point2D.Double(p.getX() * x, p.getY() * y);
225    }
226
227    /**
228     * Multiply a scalar times a point.
229     *
230     * @param s the scalar
231     * @param p the point
232     * @return the point multiplied by the scalar
233     */
234    // (again just so parameter order doesn't matter...)
235    public static Point2D multiply(double s, @Nonnull Point2D p) {
236        return new Point2D.Double(p.getX() * s, p.getY() * s);
237    }
238
239    /**
240     * Multiply a point times a point.
241     *
242     * @param p1 the first point
243     * @param p2 the second point
244     * @return the first point multiplied by the second
245     */
246    @CheckReturnValue
247    public static Point2D multiply(@Nonnull Point2D p1, @Nonnull Point2D p2) {
248        return multiply(p1, p2.getX(), p2.getY());
249    }
250
251    /**
252     * Divide a point by a scalar.
253     *
254     * @param p the point
255     * @param s the scalar
256     * @return the point divided by the scalar
257     */
258    @CheckReturnValue
259    public static Point2D divide(@Nonnull Point2D p, double s) {
260        return new Point2D.Double(p.getX() / s, p.getY() / s);
261    }
262
263    /**
264     * Divide a point by two scalars.
265     *
266     * @param p the point
267     * @param x the X scalar
268     * @param y the Y scalar
269     * @return the point divided by the scalar
270     */
271    @CheckReturnValue
272    public static Point2D divide(@Nonnull Point2D p, double x, double y) {
273        return new Point2D.Double(p.getX() / x, p.getY() / y);
274    }
275
276    /**
277     * Offset a point by two scalars.
278     *
279     * @param p the point
280     * @param x the x scalar
281     * @param y the y scalar
282     * @return the point offset by the scalars
283     */
284    @CheckReturnValue
285    public static Point2D offset(@Nonnull Point2D p, double x, double y) {
286        return new Point2D.Double(p.getX() + x, p.getY() + y);
287    }
288
289    /**
290     * Rotate x and y coordinates (by radians).
291     *
292     * @param x the x coordinate
293     * @param y the y coordinate
294     * @param a the angle (in radians)
295     * @return the point rotated by the angle
296     */
297    @CheckReturnValue
298    public static Point2D rotateRAD(double x, double y, double a) {
299        double cosA = Math.cos(a), sinA = Math.sin(a);
300        return new Point2D.Double(cosA * x - sinA * y, sinA * x + cosA * y);
301    }
302
303    /**
304     * Rotate x and y coordinates (by degrees).
305     *
306     * @param x the x coordinate
307     * @param y the y coordinate
308     * @param a the angle (in radians)
309     * @return the point rotated by the angle
310     */
311    @CheckReturnValue
312    public static Point2D rotateDEG(double x, double y, double a) {
313        return rotateRAD(x, y, Math.toRadians(a));
314    }
315
316    /**
317     * Rotate a point (by radians).
318     *
319     * @param p the point
320     * @param a the angle (in radians)
321     * @return the point rotated by the angle
322     */
323    @CheckReturnValue
324    public static Point2D rotateRAD(@Nonnull Point2D p, double a) {
325        return rotateRAD(p.getX(), p.getY(), a);
326    }
327
328    /**
329     * Rotate a point (by degrees).
330     *
331     * @param p the point
332     * @param a the angle (in radians)
333     * @return the point rotated by the angle
334     */
335    @CheckReturnValue
336    public static Point2D rotateDEG(@Nonnull Point2D p, double a) {
337        return rotateRAD(p, Math.toRadians(a));
338    }
339
340    /**
341     * Rotate a point around another point (by radians).
342     *
343     * @param p    the point being rotated
344     * @param c    the point its being rotated around
345     * @param aRAD the angle (in radians)
346     * @return the point rotated by the angle
347     */
348    @CheckReturnValue
349    public static Point2D rotateRAD(
350            @Nonnull Point2D p, @Nonnull Point2D c, double aRAD) {
351        return add(c, rotateRAD(subtract(p, c), aRAD));
352    }
353
354    /**
355     * Rotate a point around another point (by degrees).
356     *
357     * @param p    the point being rotated
358     * @param c    the point its being rotated around
359     * @param aDEG the angle (in radians)
360     * @return the point rotated by the angle
361     */
362    @CheckReturnValue
363    public static Point2D rotateDEG(
364            @Nonnull Point2D p, @Nonnull Point2D c, double aDEG) {
365        return rotateRAD(p, c, Math.toRadians(aDEG));
366    }
367
368    /**
369     * @param p the point
370     * @return the point orthogonal to this one (relative to {0, 0})
371     */
372    public static Point2D orthogonal(@Nonnull Point2D p) {
373        return new Point2D.Double(-p.getY(), p.getX());
374    }
375
376    /**
377     * Create a vector given a direction and a magnitude.
378     *
379     * @param dirDEG    the direction (in degrees)
380     * @param magnitude the magnitude
381     * @return the vector with the specified direction and magnitude
382     */
383    @CheckReturnValue
384    public static Point2D vectorDEG(double dirDEG, double magnitude) {
385        Point2D result = new Point2D.Double(magnitude, 0.0);
386        return rotateDEG(result, dirDEG);
387    }
388
389    /**
390     * Create a vector given a direction and a magnitude.
391     *
392     * @param dirRAD    the direction (in radians)
393     * @param magnitude the magnitude
394     * @return the vector with the specified direction and magnitude
395     */
396    @CheckReturnValue
397    public static Point2D vectorRAD(double dirRAD, double magnitude) {
398        Point2D result = new Point2D.Double(magnitude, 0.0);
399        return rotateRAD(result, dirRAD);
400    }
401
402    /**
403     * Dot product of two points (vectors).
404     *
405     * @param pA the first point
406     * @param pB the second point
407     * @return the dot product of the two points note: Arccos(x) (inverse
408     *         cosine) of dot product is the angle between the vectors
409     */
410    @CheckReturnValue
411    public static double dot(@Nonnull Point2D pA, @Nonnull Point2D pB) {
412        return (pA.getX() * pB.getX() + pA.getY() * pB.getY());
413    }
414
415    /**
416     * Calculate the length squared of a point (vector).
417     *
418     * @param p the point (vector)
419     * @return the length squared of the point (vector)
420     */
421    @CheckReturnValue
422    public static double lengthSquared(@Nonnull Point2D p) {
423        return dot(p, p);
424    }
425
426    /**
427     * Calculate the length of a point (vector).
428     *
429     * @param p the point (vector)
430     * @return the length of the point (vector)
431     */
432    @CheckReturnValue
433    public static double length(@Nonnull Point2D p) {
434        return Math.hypot(p.getX(), p.getY());
435    }
436
437    /**
438     * Calculate the distance between two points.
439     *
440     * @param pA the first point
441     * @param pB the second point
442     * @return the distance between the two points
443     */
444    @CheckReturnValue
445    public static double distance(@Nonnull Point2D pA, @Nonnull Point2D pB) {
446        return pA.distance(pB);
447    }
448
449    /**
450     * Normalize a point (vector) to a length.
451     *
452     * @param p      the point (vector)
453     * @param length the length to normalize to
454     * @return the normalized point (vector)
455     */
456    @CheckReturnValue
457    public static Point2D normalize(@Nonnull Point2D p, double length) {
458        return multiply(normalize(p), length);
459    }
460
461    /**
462     * Normalize a point (vector).
463     *
464     * @param p the point (vector)
465     * @return the normalized point (vector)
466     */
467    @CheckReturnValue
468    public static Point2D normalize(@Nonnull Point2D p) {
469        Point2D result = p;
470        double length = length(p);
471        if (length > 0.0) {
472            result = divide(p, length);
473        }
474        return result;
475    }
476
477    /**
478     * Compute the angle (direction in radians) for a vector.
479     *
480     * @param p the vector (point relative to zeroPoint2D)
481     * @return the angle in radians
482     */
483    @CheckReturnValue
484    public static double computeAngleRAD(@Nonnull Point2D p) {
485        return Math.atan2(p.getX(), p.getY());
486    }
487
488    /**
489     * Compute the angle (direction in degrees) for a vector.
490     *
491     * @param p the vector (point relative to zeroPoint2D)
492     * @return the angle in degrees
493     */
494    @CheckReturnValue
495    public static double computeAngleDEG(@Nonnull Point2D p) {
496        return Math.toDegrees(computeAngleRAD(p));
497    }
498
499    /**
500     * Compute the angle (direction in radians) from point 1 to point 2.
501     * <p>
502     * Note: Goes CCW from south to east to north to west, etc. For JMRI
503     * subtract from PI/2 to get east, south, west, north
504     *
505     * @param p1 the first Point2D
506     * @param p2 the second Point2D
507     * @return the angle in radians
508     */
509    @CheckReturnValue
510    public static double computeAngleRAD(@Nonnull Point2D p1, @Nonnull Point2D p2) {
511        return computeAngleRAD(subtract(p1, p2));
512    }
513
514    /**
515     * Compute the angle (direction in degrees) from point 1 to point 2.
516     * <p>
517     * Note: Goes CCW from south to east to north to west, etc. For JMRI
518     * subtract from 90.0 to get east, south, west, north
519     *
520     * @param p1 the first Point2D
521     * @param p2 the second Point2D
522     * @return the angle in degrees
523     */
524    @CheckReturnValue
525    public static double computeAngleDEG(@Nonnull Point2D p1, @Nonnull Point2D p2) {
526        return Math.toDegrees(computeAngleRAD(subtract(p1, p2)));
527    }
528
529    /**
530     * Calculate the linear interpolation between two integers.
531     *
532     * @param a the first number
533     * @param b the second number
534     * @param t the fraction (between 0 and 1)
535     * @return the linear interpolation between a and b for t
536     */
537    public static int lerp(int a, int b, double t) {
538        return (int) lerp((double) a, (double) b, t);
539    }
540
541    /**
542     * Calculate the linear interpolation between two doubles.
543     *
544     * @param a the first number
545     * @param b the second number
546     * @param t the fraction (between 0 and 1)
547     * @return the linear interpolation between a and b for t
548     */
549    @CheckReturnValue
550    public static double lerp(double a, double b, double t) {
551        return ((1.D - t) * a) + (t * b);
552    }
553
554    /**
555     * Calculate the linear interpolation between two Doubles.
556     *
557     * @param a the first number
558     * @param b the second number
559     * @param t the fraction (between 0 and 1)
560     * @return the linear interpolation between a and b for t
561     */
562    @CheckReturnValue
563    public static Double lerp(@Nonnull Double a, @Nonnull Double b, @Nonnull Double t) {
564        return ((1.D - t) * a) + (t * b);
565    }
566
567    /**
568     * Calculate the linear interpolation between two points.
569     *
570     * @param pA the first point
571     * @param pB the second point
572     * @param t  the fraction (between 0 and 1)
573     * @return the linear interpolation between a and b for t
574     */
575    @CheckReturnValue
576    public static Point2D lerp(@Nonnull Point2D pA, @Nonnull Point2D pB, double t) {
577        return new Point2D.Double(
578                lerp(pA.getX(), pB.getX(), t),
579                lerp(pA.getY(), pB.getY(), t));
580    }
581
582    /**
583     * Round value to granular increment.
584     *
585     * @param v the value to granulize
586     * @param g the granularity
587     * @return the value granulized to the granularity
588     */
589    @CheckReturnValue
590    public static double granulize(double v, double g) {
591        return Math.round(v / g) * g;
592    }
593
594    /**
595     * Round point to horizontal and vertical granular increments.
596     *
597     * @param p  the point to granulize
598     * @param gH the horizontal granularity
599     * @param gV the vertical granularity
600     * @return the point granulized to the granularity
601     */
602    @CheckReturnValue
603    public static Point2D granulize(@Nonnull Point2D p, double gH, double gV) {
604        return new Point2D.Double(granulize(p.getX(), gH), granulize(p.getY(), gV));
605    }
606
607    /**
608     * Round point to granular increment.
609     *
610     * @param p the point to granulize
611     * @param g the granularity
612     * @return the point granulized to the granularity
613     */
614    @CheckReturnValue
615    public static Point2D granulize(@Nonnull Point2D p, double g) {
616        return granulize(p, g, g);
617    }
618
619    /**
620     * Round Rectangle2D to granular increment.
621     *
622     * @param r the rectangle to granulize
623     * @param g the granularity
624     * @return the rectangle granulized to the granularity
625     */
626    @CheckReturnValue
627    public static Rectangle2D granulize(@Nonnull Rectangle2D r, double g) {
628        return new Rectangle2D.Double(
629                granulize(r.getMinX(), g),
630                granulize(r.getMinY(), g),
631                granulize(r.getWidth(), g),
632                granulize(r.getHeight(), g));
633    }
634
635    /**
636     * Calculate the midpoint between two points.
637     *
638     * @param pA the first point
639     * @param pB the second point
640     * @return the midpoint between the two points
641     */
642    @CheckReturnValue
643    public static Point2D midPoint(@Nonnull Point2D pA, @Nonnull Point2D pB) {
644        return lerp(pA, pB, 0.5);
645    }
646
647    /**
648     * Calculate the point 1/3 of the way between two points.
649     *
650     * @param pA the first point
651     * @param pB the second point
652     * @return the point one third of the way from pA to pB
653     */
654    @CheckReturnValue
655    public static Point2D oneThirdPoint(@Nonnull Point2D pA, @Nonnull Point2D pB) {
656        return lerp(pA, pB, 1.0 / 3.0);
657    }
658
659    /**
660     * Calculate the point 2/3 of the way between two points.
661     *
662     * @param pA the first point
663     * @param pB the second point
664     * @return the point two thirds of the way from pA to pB
665     */
666    @CheckReturnValue
667    public static Point2D twoThirdsPoint(@Nonnull Point2D pA, @Nonnull Point2D pB) {
668        return lerp(pA, pB, 2.0 / 3.0);
669    }
670
671    /**
672     * Calculate the point 1/4 of the way between two points.
673     *
674     * @param pA the first point
675     * @param pB the second point
676     * @return the point one fourth of the way from pA to pB
677     */
678    @CheckReturnValue
679    public static Point2D oneFourthPoint(@Nonnull Point2D pA, @Nonnull Point2D pB) {
680        return lerp(pA, pB, 1.0 / 4.0);
681    }
682
683    /**
684     * Calculate the point 3/4 of the way between two points.
685     *
686     * @param pA the first point
687     * @param pB the second point
688     * @return the point three fourths of the way from pA to pB
689     */
690    @CheckReturnValue
691    public static Point2D threeFourthsPoint(@Nonnull Point2D pA, @Nonnull Point2D pB) {
692        return lerp(pA, pB, 3.0 / 4.0);
693    }
694
695    /**
696     * Wrap an int between two values (for example +/- 180 or 0-360 degrees).
697     *
698     * @param inValue the value
699     * @param inMin   the lowest value
700     * @param inMax   the highest value
701     * @return the value wrapped between the lowest and highest values Note:
702     *         THIS IS NOT A PIN OR TRUNCATE; VALUES WRAP AROUND BETWEEN MIN AND
703     *         MAX (And yes, this works correctly with negative numbers)
704     */
705    public static int wrap(int inValue, int inMin, int inMax) {
706        int valueRange = inMax - inMin;
707        return inMin + ((((inValue - inMin) % valueRange) + valueRange) % valueRange);
708    }
709
710    /**
711     * Wrap a double between two values (for example +/- 180 or 0-360 degrees).
712     *
713     * @param inValue the value
714     * @param inMin   the lowest value
715     * @param inMax   the highest value
716     * @return the value wrapped between the lowest and highest values Note:
717     *         THIS IS NOT A PIN OR TRUNCATE; VALUES WRAP AROUND BETWEEN MIN AND
718     *         MAX (And yes, this works correctly with negative numbers)
719     */
720    @CheckReturnValue
721    public static double wrap(double inValue, double inMin, double inMax) {
722        double valueRange = inMax - inMin;
723        return inMin + ((((inValue - inMin) % valueRange) + valueRange) % valueRange);
724    }
725
726    /**
727     * Wrap a value between +/-180.
728     *
729     * @param inValue the value
730     * @return the value wrapped between -180 and +180
731     */
732    @CheckReturnValue
733    public static double wrapPM180(double inValue) {
734        return wrap(inValue, -180.0, +180.0);
735    }
736
737    /**
738     * Wrap a value between +/-360.
739     *
740     * @param inValue the value
741     * @return the value wrapped between -360 and +360
742     */
743    @CheckReturnValue
744    public static double wrapPM360(double inValue) {
745        return wrap(inValue, -360.0, +360.0);
746    }
747
748    /**
749     * Wrap a value between 0 and 360.
750     *
751     * @param inValue the value
752     * @return the value wrapped between -360 and +360
753     */
754    @CheckReturnValue
755    public static double wrap360(double inValue) {
756        return wrap(inValue, 0.0, +360.0);
757    }
758
759    /**
760     * Wrap an angle between 0 and 360.
761     *
762     * @param a the angle
763     * @return the angle wrapped between 0 and 360
764     */
765    @CheckReturnValue
766    public static double normalizeAngleDEG(double a) {
767        return wrap360(a);
768    }
769
770    /**
771     * Calculate the relative difference (+/-180) between two angles.
772     *
773     * @param a the first angle
774     * @param b the second angle
775     * @return the relative difference between the two angles (in degrees)
776     */
777    @CheckReturnValue
778    public static double diffAngleDEG(double a, double b) {
779        return wrapPM180(a - b);
780    }
781
782    /**
783     * Calculate the absolute difference (0-180) between two angles.
784     *
785     * @param a the first angle
786     * @param b the second angle
787     * @return the absolute difference between the two angles (in degrees)
788     */
789    @CheckReturnValue
790    public static double absDiffAngleDEG(double a, double b) {
791        return Math.abs(diffAngleDEG(a, b));
792    }
793
794    /**
795     * Calculate the relative difference (+/-PI) between two angles.
796     *
797     * @param a the first angle
798     * @param b the second angle
799     * @return the relative difference between the two angles (in radians)
800     */
801    @CheckReturnValue
802    public static double diffAngleRAD(double a, double b) {
803        return wrap(a - b, -PI, +PI);
804
805    }
806
807    /**
808     * Calculate the absolute difference (0-PI) between two angles.
809     *
810     * @param a the first angle
811     * @param b the second angle
812     * @return the absolute difference between the two angles (in radians)
813     */
814    @CheckReturnValue
815    public static double absDiffAngleRAD(double a, double b) {
816        return Math.abs(diffAngleRAD(a, b));
817    }
818
819    /**
820     * Pin a value between min and max.
821     *
822     * @param inValue the value
823     * @param inMin   the min
824     * @param inMax   the max
825     * @return the value pinned between the min and max values
826     */
827    public static int pin(int inValue, int inMin, int inMax) {
828        return Math.min(Math.max(inValue, inMin), inMax);
829    }
830
831    /**
832     * Pin a value between min and max.
833     *
834     * @param inValue the value
835     * @param inMin   the min
836     * @param inMax   the max
837     * @return the value pinned between the min and max values
838     */
839    @CheckReturnValue
840    public static double pin(double inValue, double inMin, double inMax) {
841        return Math.min(Math.max(inValue, inMin), inMax);
842    }
843
844    /**
845     * @return a new rectangle {0.0, 0.0, 0.0, 0.0}
846     */
847    @CheckReturnValue
848    public static Rectangle2D zeroRectangle2D() {
849        return new Rectangle2D.Double(0.0, 0.0, 0.0, 0.0);
850    }
851
852    /**
853     * @return a new rectangle {0.0, 0.0, POSITIVE_INFINITY, POSITIVE_INFINITY}
854     */
855    @CheckReturnValue
856    public static Rectangle2D zeroToInfinityRectangle2D() {
857        return new Rectangle2D.Double(0.0, 0.0, POSITIVE_INFINITY, POSITIVE_INFINITY);
858    }
859
860    /**
861     * @return a new rectangle {NEGATIVE_INFINITY, NEGATIVE_INFINITY,
862     *         POSITIVE_INFINITY, POSITIVE_INFINITY}
863     */
864    @CheckReturnValue
865    public static Rectangle2D infinityRectangle2D() {
866        return new Rectangle2D.Double(NEGATIVE_INFINITY, NEGATIVE_INFINITY, POSITIVE_INFINITY, POSITIVE_INFINITY);
867    }
868
869    /**
870     * rectangle2DToString return a string to represent a rectangle
871     *
872     * @param r the rectangle2D
873     * @return the string
874     */
875    @Nonnull
876    public static String rectangle2DToString(@Nonnull Rectangle2D r) {
877        return String.format("{%.2f, %.2f, %.2f, %.2f}",
878                r.getMinX(), r.getMinY(), r.getWidth(), r.getHeight());
879    }
880
881    /**
882     * Convert Rectangle to Rectangle2D.
883     *
884     * @param r the Rectangle
885     * @return the Rectangle2D
886     */
887    @CheckReturnValue
888    public static Rectangle2D rectangleToRectangle2D(@Nonnull Rectangle r) {
889        return new Rectangle2D.Double(r.x, r.y, r.width, r.height);
890    }
891
892    /**
893     * Convert Rectangle2D to Rectangle.
894     *
895     * @param r the Rectangle
896     * @return the Rectangle2D
897     */
898    @CheckReturnValue
899    public static Rectangle rectangle2DToRectangle(@Nonnull Rectangle2D r) {
900        return new Rectangle((int) r.getX(), (int) r.getY(), (int) r.getWidth(), (int) r.getHeight());
901    }
902
903    /**
904     * Get the origin (top left) of the rectangle.
905     *
906     * @param r the rectangle
907     * @return the origin of the rectangle
908     */
909    @CheckReturnValue
910    public static Point2D getOrigin(@Nonnull Rectangle2D r) {
911        return new Point2D.Double(r.getX(), r.getY());
912    }
913
914    /**
915     * Set the origin (top left) of the rectangle.
916     *
917     * @param r      the rectangle
918     * @param origin the origin
919     * @return a new rectangle with the new origin
920     */
921    @CheckReturnValue
922    public static Rectangle2D setOrigin(@Nonnull Rectangle2D r, @Nonnull Point2D origin) {
923        return new Rectangle2D.Double(origin.getX(), origin.getY(), r.getWidth(), r.getHeight());
924    }
925
926    /**
927     * dimensionToString return a string to represent a Dimension
928     *
929     * @param d the Dimension
930     * @return the string
931     */
932    @Nonnull
933    public static String dimensionToString(@Nonnull Dimension d) {
934        return String.format("{%.2f, %.2f}", d.getWidth(), d.getHeight());
935    }
936
937    /**
938     * Get the size of a rectangle.
939     *
940     * @param r the rectangle
941     * @return the size of the rectangle
942     */
943    @CheckReturnValue
944    public static Dimension getSize(@Nonnull Rectangle2D r) {
945        return new Dimension((int) r.getWidth(), (int) r.getHeight());
946    }
947
948    /**
949     * Set the size of a rectangle
950     *
951     * @param r the rectangle
952     * @param d the new size (as dimension)
953     * @return a new rectangle with the new size
954     */
955    @CheckReturnValue
956    public static Rectangle2D setSize(@Nonnull Rectangle2D r, @Nonnull Dimension d) {
957        return new Rectangle2D.Double(r.getMinX(), r.getMinY(), d.getWidth(), d.getHeight());
958    }
959
960    /**
961     * Set the size of a rectangle
962     *
963     * @param r the rectangle
964     * @param s the new size (as Point2D)
965     * @return a new rectangle with the new size
966     */
967    @CheckReturnValue
968    public static Rectangle2D setSize(@Nonnull Rectangle2D r, @Nonnull Point2D s) {
969        return new Rectangle2D.Double(r.getMinX(), r.getMinY(), s.getX(), s.getY());
970    }
971
972    /**
973     * Calculate the center of the rectangle.
974     *
975     * @param r the rectangle
976     * @return the center of the rectangle
977     */
978    @CheckReturnValue
979    public static Point2D center(@Nonnull Rectangle2D r) {
980        return new Point2D.Double(r.getCenterX(), r.getCenterY());
981    }
982
983    /**
984     * Calculate the midpoint of the rectangle.
985     *
986     * @param r the rectangle
987     * @return the midpoint of the rectangle
988     */
989    @CheckReturnValue
990    public static Point2D midPoint(@Nonnull Rectangle2D r) {
991        return center(r);
992    }
993
994    /**
995     * Offset a rectangle by distinct x,y values.
996     *
997     * @param r the rectangle
998     * @param x the horizontal offset
999     * @param y the vertical offset
1000     * @return the offset rectangle
1001     */
1002    @CheckReturnValue
1003    public static Rectangle2D offset(@Nonnull Rectangle2D r, double x, double y) {
1004        return new Rectangle2D.Double(r.getX() + x, r.getY() + y, r.getWidth(), r.getHeight());
1005    }
1006
1007    /**
1008     * Offset a rectangle by a single value.
1009     *
1010     * @param r the rectangle
1011     * @param o the offset
1012     * @return the offset rectangle
1013     */
1014    @CheckReturnValue
1015    public static Rectangle2D offset(@Nonnull Rectangle2D r, @Nonnull Point2D o) {
1016        return offset(r, o.getX(), o.getY());
1017    }
1018
1019    /**
1020     * Inset a rectangle by a single value.
1021     *
1022     * @param r the rectangle
1023     * @param i the inset (positive make it smaller, negative, bigger)
1024     * @return the inset rectangle
1025     */
1026    @CheckReturnValue
1027    public static Rectangle2D inset(@Nonnull Rectangle2D r, double i) {
1028        return inset(r, i, i);
1029    }
1030
1031    /**
1032     * Inset a rectangle by distinct x,y values.
1033     *
1034     * @param r the rectangle
1035     * @param h the horzontial inset (positive make it smaller, negative,
1036     *          bigger)
1037     * @param v the vertical inset (positive make it smaller, negative, bigger)
1038     * @return the inset rectangle
1039     */
1040    @CheckReturnValue
1041    public static Rectangle2D inset(@Nonnull Rectangle2D r, double h, double v) {
1042        return new Rectangle2D.Double(r.getX() + h, r.getY() + v, r.getWidth() - (2 * h), r.getHeight() - (2 * v));
1043    }
1044
1045    /**
1046     * Scale a rectangle.
1047     *
1048     * @param r the rectangle
1049     * @param s the scale
1050     * @return the scaled rectangle
1051     */
1052    //TODO: add test case
1053    @CheckReturnValue
1054    public static Rectangle2D scale(@Nonnull Rectangle2D r, double s) {
1055        return new Rectangle2D.Double(r.getX() * s, r.getY() * s, r.getWidth() * s, r.getHeight() * s);
1056    }
1057
1058    /**
1059     * Center rectangle on point.
1060     *
1061     * @param r the rectangle
1062     * @param p the point
1063     * @return the Point2D
1064     */
1065    @CheckReturnValue
1066    public static Rectangle2D centerRectangleOnPoint(@Nonnull Rectangle2D r, @Nonnull Point2D p) {
1067        Rectangle2D result = r.getBounds2D();
1068        result = offset(r, subtract(p, center(result)));
1069        return result;
1070    }
1071
1072    /**
1073     * Center rectangle on rectangle.
1074     *
1075     * @param r1 the first rectangle
1076     * @param r2 the second rectangle
1077     * @return the first rectangle centered on the second
1078     */
1079    @CheckReturnValue
1080    public static Rectangle2D centerRectangleOnRectangle(@Nonnull Rectangle2D r1, @Nonnull Rectangle2D r2) {
1081        return offset(r1, subtract(center(r2), center(r1)));
1082    }
1083
1084    /**
1085     * Get rectangle at point.
1086     *
1087     * @param p      the point
1088     * @param width  the width
1089     * @param height the height
1090     * @return the rectangle
1091     */
1092    @CheckReturnValue
1093    public static Rectangle2D rectangleAtPoint(@Nonnull Point2D p, Double width, Double height) {
1094        return new Rectangle2D.Double(p.getX(), p.getY(), width, height);
1095    }
1096
1097    // recursive routine to plot a cubic Bezier...
1098    // (also returns distance!)
1099    private static double plotBezier(
1100            GeneralPath path,
1101            @Nonnull Point2D p0,
1102            @Nonnull Point2D p1,
1103            @Nonnull Point2D p2,
1104            @Nonnull Point2D p3,
1105            int depth,
1106            double displacement) {
1107        double result;
1108
1109        // calculate flatness to determine if we need to recurse...
1110        double l01 = distance(p0, p1);
1111        double l12 = distance(p1, p2);
1112        double l23 = distance(p2, p3);
1113        double l03 = distance(p0, p3);
1114        double flatness = (l01 + l12 + l23) / l03;
1115
1116        // depth prevents stack overflow
1117        // (I picked 12 because 2^12 = 2048 is larger than most monitors ;-)
1118        // the flatness comparison value is somewhat arbitrary.
1119        // (I just kept moving it closer to 1 until I got good results. ;-)
1120        if ((depth > 12) || (flatness <= 1.001)) {
1121            Point2D vO = normalize(orthogonal(subtract(p3, p0)), displacement);
1122            if (path.getCurrentPoint() == null) {   // if this is the 1st point
1123                Point2D p0P = add(p0, vO);
1124                path.moveTo(p0P.getX(), p0P.getY());
1125            }
1126            Point2D p3P = add(p3, vO);
1127            path.lineTo(p3P.getX(), p3P.getY());
1128            result = l03;
1129        } else {
1130            // first order midpoints
1131            Point2D q0 = midPoint(p0, p1);
1132            Point2D q1 = midPoint(p1, p2);
1133            Point2D q2 = midPoint(p2, p3);
1134
1135            // second order midpoints
1136            Point2D r0 = midPoint(q0, q1);
1137            Point2D r1 = midPoint(q1, q2);
1138
1139            // third order midPoint
1140            Point2D s = midPoint(r0, r1);
1141
1142            // draw left side Bezier
1143            result = plotBezier(path, p0, q0, r0, s, depth + 1, displacement);
1144            // draw right side Bezier
1145            result += plotBezier(path, s, r1, q2, p3, depth + 1, displacement);
1146        }
1147        return result;
1148    }
1149
1150    /**
1151     * Draw a cubic Bezier curve.
1152     *
1153     * @param g2 the Graphics2D context to draw to (null if just want length)
1154     * @param p0 origin control point
1155     * @param p1 first control point
1156     * @param p2 second control point
1157     * @param p3 terminating control point
1158     *
1159     * @return the length of the Bezier curve
1160     */
1161    public static double drawBezier(
1162            @CheckForNull Graphics2D g2,
1163            @Nonnull Point2D p0,
1164            @Nonnull Point2D p1,
1165            @Nonnull Point2D p2,
1166            @Nonnull Point2D p3) {
1167        GeneralPath path = new GeneralPath();
1168        double result = plotBezier(path, p0, p1, p2, p3, 0, 0.0);
1169        if (g2 != null) {
1170            g2.draw(path);
1171        }
1172        return result;
1173    }
1174
1175    // recursive routine to plot a Bezier curve...
1176    // (also returns distance!)
1177    private static double plotBezier(
1178            GeneralPath path,
1179            @Nonnull Point2D[] points,
1180            int depth,
1181            double displacement) {
1182        int len = points.length, idx, jdx;
1183        double result;
1184
1185        // calculate flatness to determine if we need to recurse...
1186        double outer_distance = 0;
1187        for (idx = 1; idx < len; idx++) {
1188            outer_distance += distance(points[idx - 1], points[idx]);
1189        }
1190        double inner_distance = distance(points[0], points[len - 1]);
1191        double flatness = outer_distance / inner_distance;
1192
1193        // depth prevents stack overflow
1194        // (I picked 12 because 2^12 = 2048 is larger than most monitors ;-)
1195        // the flatness comparison value is somewhat arbitrary.
1196        // (I just kept moving it closer to 1 until I got good results. ;-)
1197        if ((depth > 12) || (flatness <= 1.001)) {
1198            Point2D p0 = points[0], pN = points[len - 1];
1199            Point2D vO = normalize(orthogonal(subtract(pN, p0)), displacement);
1200            if (path.getCurrentPoint() == null) {   // if this is the 1st point
1201                Point2D p0P = add(p0, vO);
1202                path.moveTo(p0P.getX(), p0P.getY());
1203            }
1204            Point2D pNP = add(pN, vO);
1205            path.lineTo(pNP.getX(), pNP.getY());
1206            result = inner_distance;
1207        } else {
1208            // calculate (len - 1) order of points
1209            // (zero'th order are the input points)
1210            Point2D[][] nthOrderPoints = new Point2D[len - 1][];
1211            for (idx = 0; idx < len - 1; idx++) {
1212                nthOrderPoints[idx] = new Point2D[len - 1 - idx];
1213                for (jdx = 0; jdx < len - 1 - idx; jdx++) {
1214                    if (idx == 0) {
1215                        nthOrderPoints[idx][jdx] = midPoint(points[jdx], points[jdx + 1]);
1216                    } else {
1217                        nthOrderPoints[idx][jdx] = midPoint(nthOrderPoints[idx - 1][jdx], nthOrderPoints[idx - 1][jdx + 1]);
1218                    }
1219                }
1220            }
1221
1222            // collect left points
1223            Point2D[] leftPoints = new Point2D[len];
1224            leftPoints[0] = points[0];
1225            for (idx = 0; idx < len - 1; idx++) {
1226                leftPoints[idx + 1] = nthOrderPoints[idx][0];
1227            }
1228            // draw left side Bezier
1229            result = plotBezier(path, leftPoints, depth + 1, displacement);
1230
1231            // collect right points
1232            Point2D[] rightPoints = new Point2D[len];
1233            for (idx = 0; idx < len - 1; idx++) {
1234                rightPoints[idx] = nthOrderPoints[len - 2 - idx][idx];
1235            }
1236            rightPoints[idx] = points[len - 1];
1237
1238            // draw right side Bezier
1239            result += plotBezier(path, rightPoints, depth + 1, displacement);
1240        }
1241        return result;
1242    }
1243
1244    /**
1245     * Plot a Bezier curve.
1246     *
1247     * @param g2 the Graphics2D context to draw to (null if just want length)
1248     * @param p  the control points
1249     * @param displacement right/left to draw a line parallel to the Bezier
1250     * @param fillFlag     false to draw / true to fill
1251     * @return the length of the Bezier curve
1252     */
1253    private static double plotBezier(
1254            @CheckForNull Graphics2D g2,
1255            @Nonnull Point2D[] p,
1256            double displacement,
1257            boolean fillFlag) {
1258        double result;
1259        GeneralPath path = new GeneralPath();
1260        if (p.length == 4) {    // draw cubic bezier?
1261            result = plotBezier(path, p[0], p[1], p[2], p[3], 0, displacement);
1262        } else {    // (nope)
1263            result = plotBezier(path, p, 0, displacement);
1264        }
1265        if (g2 != null) {
1266            if (fillFlag) {
1267                g2.fill(path);
1268            } else {
1269                g2.draw(path);
1270            }
1271        }
1272        return result;
1273    }
1274
1275    /**
1276     * Get the path for a Bezier curve.
1277     *
1278     * @param p            control points
1279     * @param displacement right/left to draw a line parallel to the Bezier
1280     * @return the length of the Bezier curve
1281     */
1282    public static GeneralPath getBezierPath(
1283            @Nonnull Point2D[] p,
1284            double displacement) {
1285        GeneralPath result = new GeneralPath();
1286        if (p.length == 4) {    // draw cubic bezier?
1287            plotBezier(result, p[0], p[1], p[2], p[3], 0, displacement);
1288        } else {    // (nope)
1289            plotBezier(result, p, 0, displacement);
1290        }
1291        return result;
1292    }
1293
1294    /**
1295     * Get the path for a Bezier curve.
1296     *
1297     * @param p control points
1298     * @return the length of the Bezier curve
1299     */
1300    public static GeneralPath getBezierPath(@Nonnull Point2D[] p) {
1301        return getBezierPath(p, 0);
1302    }
1303
1304    /**
1305     * Draw a Bezier curve
1306     *
1307     * @param g2           the Graphics2D context to draw to (null to just
1308     *                     return length)
1309     * @param p            the control points
1310     * @param displacement right/left to draw a line parallel to the Bezier
1311     * @return the length of the Bezier curve
1312     */
1313    public static double drawBezier(
1314            @CheckForNull Graphics2D g2,
1315            @Nonnull Point2D[] p,
1316            double displacement) {
1317        return plotBezier(g2, p, displacement, false);
1318    }
1319
1320    /**
1321     * Fill a Bezier curve.
1322     *
1323     * @param g2           the Graphics2D context to draw to
1324     * @param p            the control points
1325     * @param displacement right/left to draw a line parallel to the Bezier
1326     * @return the length of the Bezier curve
1327     */
1328    public static double fillBezier(
1329            @CheckForNull Graphics2D g2,
1330            @Nonnull Point2D[] p,
1331            double displacement) {
1332        return plotBezier(g2, p, displacement, true);
1333    }
1334
1335    /**
1336     * Draw a Bezier curve.
1337     *
1338     * @param g2 the Graphics2D context to draw to (null to just return length)
1339     * @param p  the control points
1340     * @return the length of the Bezier curve
1341     */
1342    public static double drawBezier(@CheckForNull Graphics2D g2, @Nonnull Point2D[] p) {
1343        return drawBezier(g2, p, 0.0);
1344    }
1345
1346    /**
1347     * Fill a Bezier curve.
1348     *
1349     * @param g2 the Graphics2D context to draw to (null if just want length)
1350     * @param p  the control points
1351     * @return the length of the Bezier curve
1352     */
1353    public static double fillBezier(@CheckForNull Graphics2D g2, @Nonnull Point2D[] p) {
1354        return plotBezier(g2, p, 0.0, true);
1355    }
1356
1357    /**
1358     * computer the bounds of a Bezier curve.
1359     *
1360     * @param p the control points
1361     * @return the bounds of the Bezier curve
1362     */
1363    public static Rectangle2D getBezierBounds(@Nonnull Point2D[] p) {
1364        return getBezierPath(p).getBounds2D();
1365    }
1366
1367    /**
1368     * Find intersection of two lines.
1369     *
1370     * @param p1 the first point on the first line
1371     * @param p2 the second point on the first line
1372     * @param p3 the first point on the second line
1373     * @param p4 the second point on the second line
1374     * @return the intersection point of the two lines or null if one doesn't
1375     *         exist
1376     */
1377    @CheckReturnValue
1378    public static Point2D intersect(
1379            @Nonnull Point2D p1,
1380            @Nonnull Point2D p2,
1381            @Nonnull Point2D p3,
1382            @Nonnull Point2D p4) {
1383        Point2D result = null;  // assume failure (pessimist!)
1384
1385        Point2D delta31 = MathUtil.subtract(p3, p1);    //p
1386        Point2D delta21 = MathUtil.subtract(p2, p1);    //q
1387        Point2D delta43 = MathUtil.subtract(p4, p3);    //r
1388
1389        double det = delta21.getX() * delta43.getY() - delta21.getY() * delta43.getX();
1390        if (!MathUtil.equals(det, 0.0)) {
1391            double t = (delta21.getY() * delta31.getX() - delta21.getX() * delta31.getY()) / det;
1392            result = lerp(p1, p2, t);
1393        }
1394        return result;
1395    }
1396
1397    /**
1398     * get (signed) distance p3 is from line segment defined by p1 and p2
1399     *
1400     * @param p1 the first point on the line segment
1401     * @param p2 the second point on the line segment
1402     * @param p3 the point whose distance from the line segment you wish to
1403     *           calculate
1404     * @return the distance (note: plus/minus determines the (left/right) side
1405     *         of the line)
1406     */
1407    public static double distance(
1408            @Nonnull Point2D p1,
1409            @Nonnull Point2D p2,
1410            @Nonnull Point2D p3) {
1411        double p1X = p1.getX(), p1Y = p1.getY();
1412        double p2X = p2.getX(), p2Y = p2.getY();
1413        double p3X = p3.getX(), p3Y = p3.getY();
1414
1415        double a = p1Y - p2Y;
1416        double b = p2X - p1X;
1417        double c = (p1X * p2Y) - (p2X * p1Y);
1418
1419        return (a * p3X + b * p3Y + c) / Math.sqrt(a * a + b * b);
1420    }
1421
1422    /*==========*\
1423    |* polygons *|
1424    \*==========*/
1425
1426    /**
1427     * return average point in points
1428     *
1429     * @param points to average
1430     * @return the average point
1431     */
1432    public static Point2D midPoint(List<Point2D> points) {
1433        Point2D result = zeroPoint2D();
1434        for (Point2D point : points) {
1435            result = add(result, point);
1436        }
1437        result = divide(result, points.size());
1438        return result;
1439    }
1440
1441    /**
1442     * @param pointT the point
1443     * @param points the polygon
1444     * @return true if pointT is in the polygon made up of the points
1445     */
1446    public static boolean isPointInPolygon(Point2D pointT, List<Point2D> points) {
1447        boolean result = false;
1448
1449        Double pointT_x = pointT.getX(), pointT_y = pointT.getY();
1450
1451        int n = points.size();
1452        for (int i = 0, j = n - 1; i < n; j = i++) {
1453            Point2D pointI = points.get(i), pointJ = points.get(j);
1454            Double pointI_x = pointI.getX(), pointI_y = pointI.getY();
1455            Double pointJ_x = pointJ.getX(), pointJ_y = pointJ.getY();
1456
1457            if ((pointI_y > pointT_y) != (pointJ_y > pointT_y)
1458                    && (pointT_x < (pointJ_x - pointI_x) * (pointT_y - pointI_y) / (pointJ_y - pointI_y) + pointI_x)) {
1459                result = !result;
1460            }
1461        }
1462        return result;
1463    }
1464
1465    /**
1466     * compute convex hull (outline of polygon)
1467     *
1468     * @param points of the polygon
1469     * @return points of the convex hull
1470     */
1471    public static List<Point2D> convexHull(List<Point2D> points) {
1472        if (points.isEmpty()) {
1473            return points;
1474        }
1475
1476        points.sort((p1, p2) -> (int) Math.signum(p1.getX() - p2.getX()));
1477
1478        List<Point2D> results = new ArrayList<>();
1479
1480        // lower hull
1481        for (Point2D pt : points) {
1482            while (results.size() > 1) {
1483                int n = results.size();
1484                if (isCounterClockWise(results.get(n - 2), results.get(n - 1), pt)) {
1485                    break;
1486                } else {
1487                    results.remove(n - 1);
1488                }
1489            }
1490            results.add(pt);
1491        }
1492
1493        // upper hull
1494        int t = results.size(); //terminate while loop when results are this size
1495        for (int i = points.size() - 1; i >= 0; i--) {
1496            Point2D pt = points.get(i);
1497
1498            while (results.size() > t) {
1499                int n = results.size();
1500                if (isCounterClockWise(results.get(n - 2), results.get(n - 1), pt)) {
1501                    break;
1502                } else {
1503                    results.remove(n - 1);
1504                }
1505            }
1506            results.add(pt);
1507        }
1508
1509        results.remove(results.size() - 1);
1510        return results;
1511    }
1512
1513    /**
1514     * isCounterClockWise
1515     *
1516     * @param a the first point
1517     * @param b the second point
1518     * @param c the third point
1519     * @return true if the three points make a counter-clockwise turn
1520     */
1521    public static boolean isCounterClockWise(Point2D a, Point2D b, Point2D c) {
1522        return ((b.getX() - a.getX()) * (c.getY() - a.getY())) > ((b.getY() - a.getY()) * (c.getX() - a.getX()));
1523    }
1524
1525    // private final static org.slf4j.Logger log = org.slf4j.LoggerFactory.getLogger(MathUtil.class);
1526
1527}