benchmarks/polygons/java/code/ConvexPolygon.java

   1
   2 import java.util.ArrayList;
   3 import java.util.Arrays;
   4 import java.util.Collections;
   5
   6 /**
   7  *
   8  * @author romis_000, Johan
   9  */
  10 public class ConvexPolygon {
  11
  12     private ArrayList<PointDouble> points = new ArrayList<PointDouble>();
  13
  14     public ConvexPolygon(ArrayList<PointDouble> points) {
  15         this.points = points;
  16     }
  17
  18     public ArrayList<PointDouble> getPointDoubles() {
  19         return points;
  20     }
  21
  22     public double[] GetXPointDoubles() {
  23         double xpoints[] = new double[this.points.size()];
  24         int c = 0;
  25         for (PointDouble p : this.points) {
  26             xpoints[c] = p.x;
  27             ++c;
  28         }
  29         return xpoints;
  30     }
  31
  32     public double[] GetYPointDoubles() {
  33         double ypoints[] = new double[this.points.size()];
  34         int c = 0;
  35         for (PointDouble p : this.points) {
  36             ypoints[c] = p.y;
  37             ++c;
  38         }
  39         return ypoints;
  40     }
  41
  42     public double[][] getVertices() {
  43         double[][] vertices = new double[points.size()][2];
  44         for (int i = 0; i < points.size(); ++i) {
  45             vertices[i][0] = points.get(i).x;
  46             vertices[i][1] = points.get(i).y;
  47         }
  48         return vertices;
  49     }
  50
  51     /**
  52      * Returns the axis corresponding to the edges of the polygon, used to check
  53      * for detection collision
  54      */
  55     public PointDouble[] Getaxes() {
  56         PointDouble[] axes = new PointDouble[this.points.size()];
  57         for (int i = 0; i < this.points.size(); i++) {
  58             // get the current vertex
  59             PointDouble v1 = new PointDouble(this.points.get(i).getX(), this.points.get(i).getY());
  60             // get the next vertex
  61             PointDouble v2 = new PointDouble(this.points.get(i + 1 == this.points.size() ? 0 : i + 1).getX(), this.points.get(i + 1 == this.points.size() ? 0 : i + 1).getY());
  62             // subtract the two to get the edge vector
  63             PointDouble edge = new PointDouble((v1.x + (-v2.x)), (v1.y + (-v2.y)));
  64             // get either perpendicular vector
  65             PointDouble normal = new PointDouble((-edge.y), edge.x);
  66             // the perp method is just (x, y) => (-y, x) or (y, -x)
  67             axes[i] = normal;
  68         }
  69         return axes;
  70     }
  71
  72     /**
  73      * Checks if the polygon is convex
  74      */
  75     public boolean isConvex() {
  76         PointDouble prev = points.get(points.size() - 2);
  77         PointDouble curr = points.get(points.size() - 1);
  78         PointDouble next = points.get(0);
  79         // Are the first two selected edges making a turnleft ?
  80         boolean isCCW = turnLeft(prev, curr, next);
  81         // Verify if all the edges are making the same type of angle as the first two
  82         for (int i = 1; i < points.size(); i++) {
  83             prev = curr;
  84             curr = next;
  85             next = points.get(i);
  86             if (turnLeft(prev, curr, next) != isCCW) {
  87                 return false;
  88             }
  89         }
  90         return true;
  91     }
  92
  93     /**
  94      * Checks if a given point is within the polygon
  95      */
  96     public boolean contain(PointDouble p) {
  97         PointDouble prev = points.get(points.size() - 1);
  98         PointDouble curr = p;
  99         PointDouble next = points.get(0);
 100         // Is the point left or right of the selected edge ?
 101         boolean isCCW = turnLeft(prev, curr, next);
 102         // Is the point the same side of every other edges of the polygon ?
 103         for (int i = 1; i < points.size(); i++) {
 104             prev = next;
 105             next = points.get(i);
 106             if (turnLeft(prev, curr, next) != isCCW) {
 107                 return false;
 108             }
 109         }
 110         return true;
 111     }
 112
 113     /**
 114      * Check the sign of the angle between vectors [p1, p2] and [p2, p3]
 115      * with the cross product
 116      */
 117     public boolean turnLeft(PointDouble p1, PointDouble p2, PointDouble p3) {
 118         return ((p2.getX() - p1.getX()) * (p3.getY()
 119                 - p2.getY()) - (p3.getX() - p2.getX()) * (p2.getY() - p1.getY())) > 0;
 120     }
 121
 122     /**
 123      * Checks if the vertices of the polygon are in counter-clock wise order
 124      * The vertices of the polygon need to be sorted for this test
 125      */
 126     public boolean isCCW() {
 127         double min = points.get(0).getY();
 128         int minIndex = 0;
 129         for (int i = 1; i < points.size() - 1; i++) {
 130             if (points.get(i).getY() < min) {
 131                 min = points.get(i).getY();
 132                 minIndex = i;
 133             }
 134         }
 135         PointDouble prev = points.get((minIndex - 1 + points.size()) % points.size());
 136         PointDouble next = points.get((minIndex + 1) % points.size());
 137         return turnLeft(prev, points.get(minIndex), next);
 138     }
 139
 140     /**
 141      * Calculates the convex hull of list of points
 142      * Using the monotone chain algorithm
 143      */
 144     public ConvexPolygon convexHull(ArrayList<PointDouble> points) {
 145         Collections.sort(points, new PointXCompare());
 146         int n = points.size();
 147
 148         ArrayList<PointDouble> pl1 = new ArrayList<PointDouble>();
 149         ArrayList<PointDouble> pl2 = new ArrayList<PointDouble>();
 150         for (int i = 0; i < n; i++) {
 151             while (pl2.size() >= 2 && !(turnLeft(pl2.get(pl2.size() - 2), pl2.get(pl2.size() - 1), points.get(i)))) {
 152                 pl2.remove(pl2.get(pl2.size() - 1));
 153             }
 154             pl2.add(points.get(i));
 155         }
 156         for (int i = n - 1; i >= 0; i--) {
 157             while (pl1.size() >= 2 && !(turnLeft(pl1.get(pl1.size() - 2), pl1.get(pl1.size() - 1), points.get(i)))) {
 158                 pl1.remove(pl1.get(pl1.size() - 1));
 159             }
 160             pl1.add(points.get(i));
 161         }
 162         pl1.remove(pl1.size() - 1);
 163         pl2.remove(pl2.size() - 1);
 164         pl2.addAll(pl1);
 165         return new ConvexPolygon(pl2);
 166     }
 167
 168     /**
 169      * Translates the polygon from the given numbers
 170      */
 171     public void translate(double x, double y) {
 172         for (PointDouble p : this.points) {
 173             p.x += x;
 174             p.y += y;
 175         }
 176     }
 177
 178     /**
 179      * Checks for an intersection between the polygon and the second given
 180      * polygon
 181      */
 182     public Boolean intersects(ConvexPolygon pol2) {
 183         PointDouble[] axes1 = this.Getaxes();
 184         PointDouble[] axes2 = pol2.Getaxes();
 185         for (int i = 0; i < axes1.length; i++) {
 186             PointDouble axis = axes1[i];
 187             // project both shapes onto the axis
 188             Projection p1 = this.project(axis);
 189             Projection p2 = pol2.project(axis);
 190             // do the projections overlap?
 191             if (!p1.overlap(p2)) {
 192                 // then we can guarantee that the shapes do not overlap
 193                 return false;
 194             }
 195         }
 196         for (int i = 0; i < axes2.length; i++) {
 197             PointDouble axis = axes2[i];
 198             Projection p1 = this.project(axis);
 199             Projection p2 = pol2.project(axis);
 200             if (!p1.overlap(p2)) {
 201                 return false;
 202             }
 203         }
 204         return true;
 205     }
 206
 207     /**
 208      * Generates a projection of an edge of the polygon on a given axis
 209      */
 210     public Projection project(PointDouble axis) {
 211         double min = ((axis.x * this.points.get(0).x) + (axis.y * this.points.get(0).y));
 212         double max = min;
 213         for (int i = 1; i < this.points.size(); i++) {
 214             double p = ((axis.x * this.points.get(i).x) + (axis.y * this.points.get(i).y));
 215             if (p < min) {
 216                 min = p;
 217             } else if (p > max) {
 218                 max = p;
 219             }
 220         }
 221         Projection proj = new Projection(min, max);
 222         return proj;
 223     }
 224
 225     public Boolean hasVertex(PointDouble pt) {
 226         for (int i = 0; i < this.points.size(); i++) {
 227             //for (int i = 0; i < this.points.size() - 1; i++) {
 228             if (this.points.get(i).equals(pt)) {
 229                 return true;
 230             }
 231         }
 232         return false;
 233     }
 234
 235     public Boolean deleteVertex(PointDouble pt) {
 236         if (this.points.size() > 3) {
 237             for (int i = 0; i < this.points.size(); i++) {
 238                 if (this.points.get(i).equals(pt)) {
 239                     this.points.remove(i);
 240                     return true;
 241                 }
 242             }
 243         }
 244         return false;
 245     }
 246
 247     /**
 248      * Sorts the vertices of the polygon in an order specified by the sorter
 249      * used
 250      */
 251     public void sortVertices(PolygonSorter sorter) {
 252         PointDouble[] arrPointDoubles = points.toArray(new PointDouble[points.size()]);
 253         Arrays.sort(arrPointDoubles, sorter);
 254         this.points.clear();
 255         points.addAll(Arrays.asList(arrPointDoubles));
 256     }
 257
 258     /*
 259     * Add a vertex to the polygon
 260     * Return true if the vertex is added to the polygon
 261     * Return false otherwise, which means that the addition
 262     * of the vertex would have made it concave.
 263     */
 264     public Boolean addVertex(PointDouble pt) {
 265         // Make a temporary list to check some properties of the new polygon
 266         ArrayList<PointDouble> tempList = new ArrayList<>(Arrays.asList(this.points.toArray(new PointDouble[this.points.size()])));
 267         tempList.add(pt);
 268         // Create a temporary polygon
 269         ConvexPolygon tempPolygon = new ConvexPolygon(tempList);
 270         // Sort it
 271         tempPolygon.sortVertices(new AntiClockSort(tempPolygon.getVertices()));
 272         // We need the new polygon to be convex, or we can't accept to add the new vertex.
 273         if (tempPolygon.isConvex()) {
 274             this.points = tempPolygon.points;
 275             return true;
 276         } else {
 277             return false;
 278         }
 279     }
 280 }