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}