--- /dev/null
+
+/**
+ *
+ * @author Johan
+ * @source
+ * http://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order
+ */
+public class AntiClockSort extends PolygonSorter {
+
+ public AntiClockSort(double[][] points) {
+ super(points);
+ }
+
+ /**
+ * Compare polygon vertices in counter-clock wise order starting at six
+ * hour. If two points share the same rad, then the farest to the center is
+ * chosen.
+ *
+ * @param a: a point to compare
+ * @param b: a second point to compare
+ * @return
+ */
+ @Override
+ public int compare(PointDouble a, PointDouble b) {
+ if (a.x - center.x >= 0 && b.x - center.x < 0) {
+ return -1;
+ }
+ if (a.x - center.x < 0 && b.x - center.x >= 0) {
+ return +1;
+ }
+ if (a.x - center.x == 0 && b.x - center.x == 0) {
+ if (a.y - center.y >= 0 || b.y - center.y >= 0) {
+ return (a.y > b.y) ? -1 : +1;
+ }
+ return (b.y > a.y) ? -1 : +1;
+ }
+
+ // compute the cross product of vectors (center -> a) x (center -> b)
+ double det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
+ if (det < 0) {
+ return -1;
+ }
+ if (det > 0) {
+ return +1;
+ }
+
+ // points a and b are on the same line from the center
+ // check which point is closer to the center
+ double d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
+ double d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
+ return (d1 > d2) ? -1 : +1;
+ }
+}
--- /dev/null
+import java.io.BufferedWriter;
+import java.io.File;
+import java.io.FileWriter;
+import java.io.IOException;
+import java.text.SimpleDateFormat;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Date;
+import java.util.Random;
+
+/**
+ *
+ * @author Johan Kayser, Romain Chanoir
+ */
+/**
+ * Runs the benchmarks for the most important operations and generates a file
+ * with time execution results
+ */
+public class BenchPolygon {
+
+ public static void main(String[] args) throws IOException {
+ int n = 0;
+ if(args[1] != null){
+ n = Integer.parseInt(args[1]);
+ }else {
+ n = 100000;
+ }
+ switch (args[0]){
+ case "add_vertex":
+ testAddVertex(n);
+ break;
+ case "sort_vertices":
+ testSortVertices(n);
+ break;
+ case "intersection":
+ testIntersects(n);
+ break;
+ case "convex_hull":
+ testConvexHull(n);
+ break;
+ case "convexity":
+ testIsConvex(n);
+ break;
+ case "contain":
+ testContain(n);
+ break;
+ default:
+ break;
+ }
+ }
+
+ /**
+ * addVertex bench: adds a vertex to a polygon with the given number of
+ * vertices
+ */
+ public static void testAddVertex(int nb) throws IOException {
+ ArrayList<PointDouble> points = new ArrayList<>();
+ ArrayList<PointDouble> randomPoints = new ArrayList<>();
+ randomPoints = generatePoints(nb + 1);
+
+ for (int i = 0; i < nb; ++i) {
+ points.add(randomPoints.remove(0));
+ }
+ ConvexPolygon test = new ConvexPolygon(points);
+ test.sortVertices(new AntiClockSort(test.getVertices()));
+
+ test.addVertex(randomPoints.remove(0));
+ }
+
+ /**
+ * sortVertices bench: sorts the given number of vertices in the ArrayList
+ * of a polygon
+ */
+ public static void testSortVertices(int nb) throws IOException {
+ ArrayList<PointDouble> randomPoints = new ArrayList<>();
+ randomPoints = generatePoints(nb);
+ Collections.shuffle(randomPoints);
+
+ ConvexPolygon test = new ConvexPolygon(randomPoints);
+ test.sortVertices(new AntiClockSort(test.getVertices()));
+
+ }
+
+ /**
+ * intersects bench: tests the intersection between two polygons with the
+ * given number of vertices
+ */
+ public static void testIntersects(int nb) throws IOException {
+ ArrayList<PointDouble> points1 = new ArrayList<>();
+ ArrayList<PointDouble> points2 = new ArrayList<>();
+ points1 = generatePoints(nb);
+ points2 = generatePoints(nb);
+ ConvexPolygon test1 = new ConvexPolygon(points1);
+ ConvexPolygon test2 = new ConvexPolygon(points2);
+ test1.sortVertices(new AntiClockSort(test1.getVertices()));
+ test2.sortVertices(new AntiClockSort(test2.getVertices()));
+
+ Boolean rez = test1.intersects(test2);
+ }
+
+ /**
+ * convexHull bench: gets the convex hull of the given number of points
+ */
+ public static void testConvexHull(int nb) throws IOException {
+ ArrayList<PointDouble> randomPoints = new ArrayList<>();
+ randomPoints = generatePoints(nb);
+ Collections.shuffle(randomPoints);
+ ConvexPolygon test = new ConvexPolygon(randomPoints);
+
+ ConvexPolygon rez = test.convexHull(randomPoints);
+ }
+
+ /**
+ * isConvex bench: checks if the polygon with the given number of vertices
+ * is convex (we test the worst case -> polygon vertices are ordered)
+ */
+ public static void testIsConvex(int nb) throws IOException {
+ ArrayList<PointDouble> randomPoints = new ArrayList<>();
+ randomPoints = generatePoints(nb);
+ ConvexPolygon test = new ConvexPolygon(randomPoints);
+ test.sortVertices(new AntiClockSort(test.getVertices()));
+
+ Boolean rez = test.isConvex();
+ }
+
+ /**
+ * contain bench: checks if the polygon with the given number of vertices
+ * contains a randomly generated point
+ */
+ public static void testContain(int nb) throws IOException {
+ ArrayList<PointDouble> randomPoints = new ArrayList<>();
+ randomPoints = generatePoints(nb);
+ ConvexPolygon test = new ConvexPolygon(randomPoints);
+ test.sortVertices(new AntiClockSort(test.getVertices()));
+
+ Boolean rez = test.contain(new PointDouble(0.0, 0.0));
+ }
+
+ /**
+ * generates some points making it easier to use convex polygons
+ */
+ public static ArrayList<PointDouble> generatePoints(int nb) {
+ ArrayList<PointDouble> pts = new ArrayList<>();
+ pts = PointDouble.getNPointsOnCircle(100.0, nb);
+ return pts;
+ }
+}
--- /dev/null
+
+/**
+ *
+ * @author Johan
+ */
+public class ClockSort extends PolygonSorter {
+
+ public ClockSort(double[][] points) {
+ super(points);
+ }
+
+ /**
+ * Compare polygon vertices in clock wise order starting at six hour. If two
+ * points share the same rad, then the farest to the center is chosen.
+ *
+ * @param a: a point to compare
+ * @param b: a second point to compare
+ * @return
+ */
+ @Override
+ public int compare(PointDouble a, PointDouble b) {
+ if (a.x - center.x >= 0 && b.x - center.x < 0) {
+ return +1;
+ }
+ if (a.x - center.x < 0 && b.x - center.x >= 0) {
+ return -1;
+ }
+ if (a.x - center.x == 0 && b.x - center.x == 0) {
+ if (a.y - center.y >= 0 || b.y - center.y >= 0) {
+ return (a.y > b.y) ? +1 : -1;
+ }
+ return (b.y > a.y) ? +1 : -1;
+ }
+
+ // compute the cross product of vectors (center -> a) x (center -> b)
+ double det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
+ if (det < 0.0d) {
+ return +1;
+ }
+ if (det > 0.0d) {
+ return -1;
+ }
+
+ // points a and b are on the same line from the center
+ // check which point is closer to the center
+ double d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
+ double d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
+ return (d1 > d2) ? +1 : -1;
+ }
+}
--- /dev/null
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+
+/**
+ *
+ * @author romis_000, Johan
+ */
+public class ConvexPolygon {
+
+ private ArrayList<PointDouble> points = new ArrayList<PointDouble>();
+
+ public ConvexPolygon(ArrayList<PointDouble> points) {
+ this.points = points;
+ }
+
+ public ArrayList<PointDouble> getPointDoubles() {
+ return points;
+ }
+
+ public double[] GetXPointDoubles() {
+ double xpoints[] = new double[this.points.size()];
+ int c = 0;
+ for (PointDouble p : this.points) {
+ xpoints[c] = p.x;
+ ++c;
+ }
+ return xpoints;
+ }
+
+ public double[] GetYPointDoubles() {
+ double ypoints[] = new double[this.points.size()];
+ int c = 0;
+ for (PointDouble p : this.points) {
+ ypoints[c] = p.y;
+ ++c;
+ }
+ return ypoints;
+ }
+
+ public double[][] getVertices() {
+ double[][] vertices = new double[points.size()][2];
+ for (int i = 0; i < points.size(); ++i) {
+ vertices[i][0] = points.get(i).x;
+ vertices[i][1] = points.get(i).y;
+ }
+ return vertices;
+ }
+
+ /**
+ * Returns the axis corresponding to the edges of the polygon, used to check
+ * for detection collision
+ */
+ public PointDouble[] Getaxes() {
+ PointDouble[] axes = new PointDouble[this.points.size()];
+ for (int i = 0; i < this.points.size(); i++) {
+ // get the current vertex
+ PointDouble v1 = new PointDouble(this.points.get(i).getX(), this.points.get(i).getY());
+ // get the next vertex
+ 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());
+ // subtract the two to get the edge vector
+ PointDouble edge = new PointDouble((v1.x + (-v2.x)), (v1.y + (-v2.y)));
+ // get either perpendicular vector
+ PointDouble normal = new PointDouble((-edge.y), edge.x);
+ // the perp method is just (x, y) => (-y, x) or (y, -x)
+ axes[i] = normal;
+ }
+ return axes;
+ }
+
+ /**
+ * Checks if the polygon is convex
+ */
+ public boolean isConvex() {
+ PointDouble prev = points.get(points.size() - 2);
+ PointDouble curr = points.get(points.size() - 1);
+ PointDouble next = points.get(0);
+ // Are the first two selected edges making a turnleft ?
+ boolean isCCW = turnLeft(prev, curr, next);
+ // Verify if all the edges are making the same type of angle as the first two
+ for (int i = 1; i < points.size(); i++) {
+ prev = curr;
+ curr = next;
+ next = points.get(i);
+ if (turnLeft(prev, curr, next) != isCCW) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Checks if a given point is within the polygon
+ */
+ public boolean contain(PointDouble p) {
+ PointDouble prev = points.get(points.size() - 1);
+ PointDouble curr = p;
+ PointDouble next = points.get(0);
+ // Is the point left or right of the selected edge ?
+ boolean isCCW = turnLeft(prev, curr, next);
+ // Is the point the same side of every other edges of the polygon ?
+ for (int i = 1; i < points.size(); i++) {
+ prev = next;
+ next = points.get(i);
+ if (turnLeft(prev, curr, next) != isCCW) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Check the sign of the angle between vectors [p1, p2] and [p2, p3]
+ * with the cross product
+ */
+ public boolean turnLeft(PointDouble p1, PointDouble p2, PointDouble p3) {
+ return ((p2.getX() - p1.getX()) * (p3.getY()
+ - p2.getY()) - (p3.getX() - p2.getX()) * (p2.getY() - p1.getY())) > 0;
+ }
+
+ /**
+ * Checks if the vertices of the polygon are in counter-clock wise order
+ * The vertices of the polygon need to be sorted for this test
+ */
+ public boolean isCCW() {
+ double min = points.get(0).getY();
+ int minIndex = 0;
+ for (int i = 1; i < points.size() - 1; i++) {
+ if (points.get(i).getY() < min) {
+ min = points.get(i).getY();
+ minIndex = i;
+ }
+ }
+ PointDouble prev = points.get((minIndex - 1 + points.size()) % points.size());
+ PointDouble next = points.get((minIndex + 1) % points.size());
+ return turnLeft(prev, points.get(minIndex), next);
+ }
+
+ /**
+ * Calculates the convex hull of list of points
+ * Using the monotone chain algorithm
+ */
+ public ConvexPolygon convexHull(ArrayList<PointDouble> points) {
+ Collections.sort(points, new PointXCompare());
+ int n = points.size();
+
+ ArrayList<PointDouble> pl1 = new ArrayList<PointDouble>();
+ ArrayList<PointDouble> pl2 = new ArrayList<PointDouble>();
+ for (int i = 0; i < n; i++) {
+ while (pl2.size() >= 2 && !(turnLeft(pl2.get(pl2.size() - 2), pl2.get(pl2.size() - 1), points.get(i)))) {
+ pl2.remove(pl2.get(pl2.size() - 1));
+ }
+ pl2.add(points.get(i));
+ }
+ for (int i = n - 1; i >= 0; i--) {
+ while (pl1.size() >= 2 && !(turnLeft(pl1.get(pl1.size() - 2), pl1.get(pl1.size() - 1), points.get(i)))) {
+ pl1.remove(pl1.get(pl1.size() - 1));
+ }
+ pl1.add(points.get(i));
+ }
+ pl1.remove(pl1.size() - 1);
+ pl2.remove(pl2.size() - 1);
+ pl2.addAll(pl1);
+ return new ConvexPolygon(pl2);
+ }
+
+ /**
+ * Translates the polygon from the given numbers
+ */
+ public void translate(double x, double y) {
+ for (PointDouble p : this.points) {
+ p.x += x;
+ p.y += y;
+ }
+ }
+
+ /**
+ * Checks for an intersection between the polygon and the second given
+ * polygon
+ */
+ public Boolean intersects(ConvexPolygon pol2) {
+ PointDouble[] axes1 = this.Getaxes();
+ PointDouble[] axes2 = pol2.Getaxes();
+ for (int i = 0; i < axes1.length; i++) {
+ PointDouble axis = axes1[i];
+ // project both shapes onto the axis
+ Projection p1 = this.project(axis);
+ Projection p2 = pol2.project(axis);
+ // do the projections overlap?
+ if (!p1.overlap(p2)) {
+ // then we can guarantee that the shapes do not overlap
+ return false;
+ }
+ }
+ for (int i = 0; i < axes2.length; i++) {
+ PointDouble axis = axes2[i];
+ Projection p1 = this.project(axis);
+ Projection p2 = pol2.project(axis);
+ if (!p1.overlap(p2)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Generates a projection of an edge of the polygon on a given axis
+ */
+ public Projection project(PointDouble axis) {
+ double min = ((axis.x * this.points.get(0).x) + (axis.y * this.points.get(0).y));
+ double max = min;
+ for (int i = 1; i < this.points.size(); i++) {
+ double p = ((axis.x * this.points.get(i).x) + (axis.y * this.points.get(i).y));
+ if (p < min) {
+ min = p;
+ } else if (p > max) {
+ max = p;
+ }
+ }
+ Projection proj = new Projection(min, max);
+ return proj;
+ }
+
+ public Boolean hasVertex(PointDouble pt) {
+ for (int i = 0; i < this.points.size(); i++) {
+ //for (int i = 0; i < this.points.size() - 1; i++) {
+ if (this.points.get(i).equals(pt)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public Boolean deleteVertex(PointDouble pt) {
+ if (this.points.size() > 3) {
+ for (int i = 0; i < this.points.size(); i++) {
+ if (this.points.get(i).equals(pt)) {
+ this.points.remove(i);
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Sorts the vertices of the polygon in an order specified by the sorter
+ * used
+ */
+ public void sortVertices(PolygonSorter sorter) {
+ PointDouble[] arrPointDoubles = points.toArray(new PointDouble[points.size()]);
+ Arrays.sort(arrPointDoubles, sorter);
+ this.points.clear();
+ points.addAll(Arrays.asList(arrPointDoubles));
+ }
+
+ /*
+ * Add a vertex to the polygon
+ * Return true if the vertex is added to the polygon
+ * Return false otherwise, which means that the addition
+ * of the vertex would have made it concave.
+ */
+ public Boolean addVertex(PointDouble pt) {
+ // Make a temporary list to check some properties of the new polygon
+ ArrayList<PointDouble> tempList = new ArrayList<>(Arrays.asList(this.points.toArray(new PointDouble[this.points.size()])));
+ tempList.add(pt);
+ // Create a temporary polygon
+ ConvexPolygon tempPolygon = new ConvexPolygon(tempList);
+ // Sort it
+ tempPolygon.sortVertices(new AntiClockSort(tempPolygon.getVertices()));
+ // We need the new polygon to be convex, or we can't accept to add the new vertex.
+ if (tempPolygon.isConvex()) {
+ this.points = tempPolygon.points;
+ return true;
+ } else {
+ return false;
+ }
+ }
+}
--- /dev/null
+
+import java.util.ArrayList;
+import java.util.Random;
+
+/**
+ * Represents a 2d point with double coordinates
+ *
+ * @author Johan
+ */
+public class PointDouble {
+
+ double x;
+ double y;
+
+ public PointDouble() {
+ this(0.0d, 0.0d);
+ }
+
+ public PointDouble(double x, double y) {
+ this.x = x;
+ this.y = y;
+ }
+
+ public double getX() {
+ return this.x;
+ }
+
+ public double getY() {
+ return this.y;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj == null || getClass() != obj.getClass()) {
+ return false;
+ }
+ final PointDouble other = (PointDouble) obj;
+ if (Double.doubleToLongBits(this.x) != Double.doubleToLongBits(other.x)) {
+ return false;
+ }
+ if (Double.doubleToLongBits(this.y) != Double.doubleToLongBits(other.y)) {
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * returns a array of n points on a circle
+ */
+ public static ArrayList<PointDouble> getNPointsOnCircle(double radius, int n) {
+ ArrayList<PointDouble> points = new ArrayList<>();
+ Random generator = new Random(0);
+ for(int i = 0; i < n; i++){
+ double angle = generator.nextFloat() * Math.PI * 2;
+ PointDouble p = new PointDouble(Math.cos(angle) * radius, Math.sin(angle) * radius);
+ points.add(p);
+ }
+ return points;
+ }
+}
--- /dev/null
+
+import java.util.Comparator;
+
+/**
+ *
+ * @author romis_000
+ */
+class PointXCompare
+ implements Comparator<PointDouble> {
+
+ @Override
+ public int compare(final PointDouble a, final PointDouble b) {
+ if (a.x == b.x) {
+ //return (int) (a.y - b.y);
+ return (a.y > b.y) ? -1 : +1;
+ } else {
+ //return (int)(a.x - b.x);
+ return (a.x > b.x) ? -1 : +1;
+ }
+ }
+}
--- /dev/null
+
+import java.util.Comparator;
+
+/**
+ * An utility class to sort the polygon vertices, is extended by AntiClockSort
+ * and ClockSort
+ *
+ * @author Johan
+ */
+public abstract class PolygonSorter implements Comparator<PointDouble> {
+
+ PointDouble center;
+
+ public PolygonSorter(double[][] podoubles) {
+ this.center = calcCenter(podoubles);
+ }
+
+ /**
+ * returns the point representing the center of a polygon
+ */
+ final PointDouble calcCenter(double[][] podoubles) {
+ double sumx = 0;
+ double sumy = 0;
+ for (double[] podouble : podoubles) {
+ sumx += podouble[0];
+ sumy += podouble[1];
+ }
+ return new PointDouble(sumx / podoubles.length, sumy / podoubles.length);
+ }
+
+ @Override
+ public abstract int compare(PointDouble a, PointDouble b);
+}
--- /dev/null
+
+/**
+ * An utility class to store a projection of an edge on an axis, used by the
+ * intersects operation
+ *
+ * @author Johan
+ */
+public class Projection {
+
+ private double min;
+ private double max;
+
+ public Projection(double min, double max) {
+ this.min = min;
+ this.max = max;
+ }
+
+ public Boolean overlap(Projection p2) {
+ return !(this.min > p2.max || p2.min > this.max);
+ }
+}
nitlanguage / nit.git / commitdiff