Define a square in a list of points

Question

I want to check if a square is in the list of a Point object or not.

This is my Point class:

class Point { private int x; private int y; public Point(int x, int y) { this.x = x; this.y = y; } public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } public int distanceSquare(Point q) { return (x - q.getX()) * (x - q.getX()) + (y - q.getY()) * (y - q.getY()); } } 

I can check if four points are square or not:

 static boolean isSquare(Point p1, Point p2, Point p3, Point p4) { int d2 = p1.distanceSquare(p2); // from p1 to p2 int d3 = p1.distanceSquare(p3); // from p1 to p3 int d4 = p1.distanceSquare(p4); // from p1 to p4 if (d2 == d3 && 2 * d2 == d4) { int d = p2.distanceSquare(p4); return (d == p3.distanceSquare(p4) && d == d2); } if (d3 == d4 && 2 * d3 == d2) { int d = p2.distanceSquare(p3); return (d == p2.distanceSquare(p4) && d == d3); } if (d2 == d4 && 2 * d2 == d3) { int d = p2.distanceSquare(p3); return (d == p3.distanceSquare(p4) && d == d2); } return false; } 

But I did not find a better way to find a square in the Point list.

Can you help me?

Answer 1

Take all pairs of points; for each pair, its angle, its length and midpoint are calculated. It takes O time (n ^ 2).
For each set of pairs having the same midpoint and the same length, sort these pairs by angle, this will take the total time O (n ^ 2 * log (n)). This will help you find two orthogonal diagonals with the same length, having the same midpoint (i.e. a square!).
The total time complexity of the algorithm is O (n ^ 2 * log (n)).

Answer 2

Here is the O (n ^ 2 log (n)) -time and O (n) -space algorithm. If you specify the vertices by the angle, then for each pair {A, B} you can find both angles OC and OD.

 compute angle for every point -- O(n) sort point by angles -- O(n*lg(n)) for each pair -- O(n^2*lg(n)) if (Bx > Ax) && (By > Ay) compute positions of C and D compute angles of C and D for C and D if there is a pair of points with same angles and same positions return true return false 

How to find the coordinates of C:

 Xc = Xb - (Yb - Ya) Yc = Yb + (Xb - Xa) 

Answer 3

Updated and discovered spinning square

I like Yegor Skriptunov, answer above, but let me try to give a different answer. I think complexity is only O (N ^ 2).

Algorithm

For any pair of points (P0, P1) (of which N ^ 2), find out the vector V01 from P0 to P1, and then rotate this vector 90 degrees (it becomes V12). Add it to P1 and see if you can find the point there? (this can be done by hashmap search - see below) If so, then you have P2 and continue the procedure.

Rotate the vector another 90 degrees (it will become V23), add it to P2, and see if you can find the item there? (Again, by searching the hashmap)
If yes, then you have P3 and continue the procedure.

Rotate the vector 90 degrees (it will become V34). Add it to P3, and see if it can find a point there? (Again, using a hashmap search). If yes, check also if this point P4 is the same as P0. If so, then you just discovered a square.

The following diagram illustrates the idea.

Data structure

If the squares rotate, then the x and y coordinates of the point must be in floating point (double) and cannot be an integer. Because a lot of calculations will give you irrational numbers (e.g. sqrt (2))

However, a double representation cannot be exact as an integer, so we must be careful to treat two double numbers that are close enough, cost. In my code, I use epsilon as the tolerance we allow for "approximate equivalence." I chose 1E-3 as epsilon.

 public class Point2 { private double x; private double y; private final double eps = 1E-3; public double getEps() { return eps; } 

And then in all calculations regarding equals() and hashCode() , make sure that you use the "cut off" value of x and y, and not their original double representations. (Graphically, you can imagine this as your graphic editor provides you with a "snap to grid" function with an epsilon mesh size). You also need to be careful that double reviewers have positive 0s and negative 0s, and you should also treat them as the same value.

Something like that:

 public long getXsnapped() { return Math.round(this.getX()/this.getEps()); } public long getYsnapped() { return Math.round(this.getY()/this.getEps()); } @Override public int hashCode() { final int prime = 31; int result = 1; long temp; temp = Double.doubleToLongBits(eps); result = prime * result + (int) (temp ^ (temp >>> 32)); if (Math.abs(this.getX())>this.getEps()) { // include X only if it is larger than eps temp = this.getXsnapped(); result = prime * result + (int) (temp ^ (temp >>> 32)); } if (Math.abs(this.getY())>this.getEps()) { temp = this.getYsnapped(); result = prime * result + (int) (temp ^ (temp >>> 32)); } return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Point2 other = (Point2) obj; if (Double.doubleToLongBits(eps) != Double.doubleToLongBits(other.eps)) return false; boolean answer = true; if (Math.abs(this.getX())>this.getEps() || Math.abs(other.getX())>this.getEps()) { // compare value and sign only if X of both points are larger than eps if (this.getXsnapped()!= other.getXsnapped()) answer = false; } if (Math.abs(this.getY())>this.getEps() || Math.abs(other.getY())>this.getEps()) { // compare value and sign only if Y of both points are larger than eps if (this.getYsnapped()!= other.getYsnapped()) answer &= false; } boolean isDebug = false; Util.debugPrint(isDebug, "p1 %s; p2 %s: %b (eps is %.9f)%n" , this, other, answer, this.getEps()); return answer; } 

In addition, each square has four points. You can add a rule to your program that says the four points should be in order, as used in the algorithm (P0-> P1-> P2-> P3) with the angular relation (see algorithm above). However, you also need to be careful that, provided that there are four options for selecting the starting point at the same four points. Thus, your square object code should process the following squares indicated by these four points as equivalent:

 P0->P1->P2->P3 P1->P2->P3->P0 P2->P3->P0->P1 P3->P0->P1->P2 

You can do this in the constructor of the Square object and always “canonize” the input, select a point with a certain function as the starting point (for example, select the point that has the lowest x, and if its value x is connected to another point, then select the point that has the lowest x and less than y among a couple)

Test Input 1

 -1.4142, 9.8995 -5.6569, 15.5563 1.4142, 9.8995 -1.4142, 14.1421 -2.1213, 14.8492 1.4142, 14.1421 0.0000, 15.5563 -2.1213, 17.6777 7.0711, 11.3137 5.6569, 12.7279 4.2426, 14.1421 6.3640, 10.6066 7.0711, 14.1421 5.6569, 15.5563 1.4142, 19.7990 7.7782, 14.8492 

Test result 1

 ===== Given a set of following points from file src\detectSquare\inputSet1_45_1_1_0_0.txt ===== 1: Point2 [x=-1.4142, y=9.8995] 2: Point2 [x=-5.6569, y=15.5563] 3: Point2 [x=1.4142, y=9.8995] 4: Point2 [x=-1.4142, y=14.1421] 5: Point2 [x=-2.1213, y=14.8492] 6: Point2 [x=1.4142, y=14.1421] 7: Point2 [x=0.0000, y=15.5563] 8: Point2 [x=-2.1213, y=17.6777] 9: Point2 [x=7.0711, y=11.3137] 10: Point2 [x=5.6569, y=12.7279] 11: Point2 [x=4.2426, y=14.1421] 12: Point2 [x=6.3640, y=10.6066] 13: Point2 [x=7.0711, y=14.1421] 14: Point2 [x=5.6569, y=15.5563] 15: Point2 [x=1.4142, y=19.7990] 16: Point2 [x=7.7782, y=14.8492] ===== The following squares have been found ===== 1: SquareRotatable [points=[Point2 [x=4.2427, y=14.1421], Point2 [x=5.6569, y=12.7279], Point2 [x=7.0711, y=14.1421], Point2 [x=5.6569, y=15.5563]]] 

Test Input 2

 0.0000, 0.0000 -0.7071, 0.7071 -1.4142, 1.4142 0.7071, 0.7071 0.0000, 1.4142 -0.7071, 2.1213 1.4142, 1.4142 0.7071, 2.1213 0.0000, 2.8284 

Test result 2

 ===== Given a set of following points from file src\detectSquare\inputSet2_45_0_0_0_0.txt ===== 1: Point2 [x=0.0000, y=0.0000] 2: Point2 [x=-0.7071, y=0.7071] 3: Point2 [x=-1.4142, y=1.4142] 4: Point2 [x=0.7071, y=0.7071] 5: Point2 [x=0.0000, y=1.4142] 6: Point2 [x=-0.7071, y=2.1213] 7: Point2 [x=1.4142, y=1.4142] 8: Point2 [x=0.7071, y=2.1213] 9: Point2 [x=0.0000, y=2.8284] ===== The following squares have been found ===== 1: SquareRotatable [points=[Point2 [x=-1.4142, y=1.4142], Point2 [x=0.0000, y=0.0000], Point2 [x=1.4142, y=1.4142], Point2 [x=0.0000, y=2.8284]]] 2: SquareRotatable [points=[Point2 [x=-0.7071, y=0.7071], Point2 [x=0.7071, y=0.7071], Point2 [x=0.7071, y=2.1213], Point2 [x=-0.7071, y=2.1213]]] 3: SquareRotatable [points=[Point2 [x=-1.4142, y=1.4142], Point2 [x=-0.7071, y=0.7071], Point2 [x=0.0000, y=1.4142], Point2 [x=-0.7071, y=2.1213]]] 4: SquareRotatable [points=[Point2 [x=-0.7071, y=2.1213], Point2 [x=0.0000, y=1.4142], Point2 [x=0.7071, y=2.1213], Point2 [x=-0.0000, y=2.8284]]] 5: SquareRotatable [points=[Point2 [x=-0.7071, y=0.7071], Point2 [x=0.0000, y=0.0000], Point2 [x=0.7071, y=0.7071], Point2 [x=0.0000, y=1.4142]]] 6: SquareRotatable [points=[Point2 [x=0.0000, y=1.4142], Point2 [x=0.7071, y=0.7071], Point2 [x=1.4142, y=1.4142], Point2 [x=0.7071, y=2.1213]]] 

Testing the testing program JUnit Point2#getXsnapped() (fragment only)

 import org.junit.Before; import org.junit.BeforeClass; import org.junit.Ignore; import org.junit.Test; public class Point2Test { private List<Point2> points = new ArrayList<>(); @Before public void setUp() throws Exception { points.add(new Point2(0.49999999f, 0)); points.add(new Point2(0.50000001f, 0)); } ... @Test public void testGetXsnapped() { System.out.format("testing xSnapped of two points: %s and %s%n" , points.get(0), points.get(1)); System.out.format("and they are %d and %d respectively%n" , points.get(0).getXsnapped() , points.get(1).getXsnapped()); System.out.format("(Note: epsilon is %f)%n" , points.get(0).getEps()); assertEquals(points.get(0).getXsnapped() , points.get(1).getXsnapped()); } } 

JUnit test output

 testing xSnapped of two points: Point2 [x=0.5000, y=0.0000] and Point2 [x=0.5000, y=0.0000] and they are 500 and 500 respectively (Note: epsilon is 0.001000) 

Caveat

Eric Duminal is right in pointing out that there can be 2 points arbitrarily close to each other and still tied to different points in the grid.

Above, I do not know how to solve this problem. Suggestions are welcome!

eg.

 @Before public void setUp() throws Exception { Point2 dummy = new Point2(0, 0); // just to get epsilon points.add(new Point2(dummy.getEps()*0.5, 0)); points.add(new Point2(dummy.getEps()*0.49999999999999, 0)); } 

With this added debugging code:

 public long getXsnapped() { boolean isDebug = true; String _ = " "; // indent double X = this.getX(); Util.debugPrint(isDebug, _ + "X is %E (long bits is 0x%x)%n" , X, Double.doubleToLongBits(X)); double eps = this.getEps(); Util.debugPrint(isDebug, _ + "eps is %E%n", eps); double fraction = X/eps; Util.debugPrint(isDebug, _ + "fraction is %E (long bits is 0x%x)%n" , fraction, Double.doubleToLongBits(fraction)); long answer = Math.round(fraction); Util.debugPrint(isDebug, _ + "xSnapped is %d%n", answer); return answer; } 

Util.debugPrint ():

 public static void debugPrint(boolean isDebug, String format, Object... args) { if (!isDebug) { return; // don't print } System.out.format(format, args); } 

I would get the following conclusion - two points are considered different!

 testing xSnapped of two points: Point2 [x=0.0005, y=0.0000] and Point2 [x=0.0005, y=0.0000] X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9fc) eps is 1.000000E-03 fraction is 5.000000E-01 (long bits is 0x3fe0000000000000) xSnapped is 1 X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9a0) eps is 1.000000E-03 fraction is 5.000000E-01 (long bits is 0x3fdfffffffffff4c) xSnapped is 0 and they are 1 and 0 respectively (Note: epsilon is 0.001000) delta between the two x (as double) is 9.974660E-18 X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9fc) eps is 1.000000E-03 fraction is 5.000000E-01 (long bits is 0x3fe0000000000000) xSnapped is 1 X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9a0) eps is 1.000000E-03 fraction is 5.000000E-01 (long bits is 0x3fdfffffffffff4c) xSnapped is 0