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