benchmarks/polygons/java/code/AntiClockSort.java

   1
   2 /**
   3  *
   4  * @author Johan
   5  * @source
   6  * http://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order
   7  */
   8 public class AntiClockSort extends PolygonSorter {
   9
  10     public AntiClockSort(double[][] points) {
  11         super(points);
  12     }
  13
  14     /**
  15      * Compare polygon vertices in counter-clock wise order starting at six
  16      * hour. If two points share the same rad, then the farest to the center is
  17      * chosen.
  18      *
  19      * @param a: a point to compare
  20      * @param b: a second point to compare
  21      * @return
  22      */
  23     @Override
  24     public int compare(PointDouble a, PointDouble b) {
  25         if (a.x - center.x >= 0 && b.x - center.x < 0) {
  26             return -1;
  27         }
  28         if (a.x - center.x < 0 && b.x - center.x >= 0) {
  29             return +1;
  30         }
  31         if (a.x - center.x == 0 && b.x - center.x == 0) {
  32             if (a.y - center.y >= 0 || b.y - center.y >= 0) {
  33                 return (a.y > b.y) ? -1 : +1;
  34             }
  35             return (b.y > a.y) ? -1 : +1;
  36         }
  37
  38         // compute the cross product of vectors (center -> a) x (center -> b)
  39         double det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
  40         if (det < 0) {
  41             return -1;
  42         }
  43         if (det > 0) {
  44             return +1;
  45         }
  46
  47         // points a and b are on the same line from the center
  48         // check which point is closer to the center
  49         double d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
  50         double d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
  51         return (d1 > d2) ? -1 : +1;
  52     }
  53 }