I want to test if there is a square in a list of 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 test if four Point is a 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 didn't found the best way to search the square in a list of Point.
Can you help me !!!
Updated to also detected rotated squares
I like Egor Skriptunoff's answer above, but let me try to give another answer. I think the complexity is only O(N^2).
Algorithm
For any pair of points (P0, P1) (there are N^2 of them), find out the vector V01 from P0 to P1, and then rotate this vector by 90 degrees (it becomes V12). Add it to P1, and see if you can find a point there? (this can be done by a hashmap lookup -- see more below) If so then you have P2, and continue the procedure.
Rotate the vector by another 90 degrees (it become V23), Add it to P2, and see if you can find a point there? (Again, by a hashmap lookup)
If so, then you have P3, and continue the procedure.
Rotate the vector by another 90 degrees (it becomes V34). Add it to P3, and see if can find a point there? (Again, by a hashmap lookup). If so, check also if this point P4 is the same as P0. If so, then you have just detected a square.
The following diagram illustrates the idea.
Data Structure
If the squares are rotatable, then the x and y coordinates of Point must be in floating point (double) and cannot be integer. Because a lot of computation will give you irrational numbers (e.g. sqrt(2))
However, a double representation cannot be precise as an integer, so we have to be careful to treat two double numbers that are close enough as the same double value. In my code, I use an epsilon as the tolerance that we allow for "approximate equivalence". I picked 1E-3 as the epsilon.
And then in all computation regarding
equals()andhashCode(), make sure you use a "snapped" value of x and y, not their original double representations. (Graphically you can imagine this like your graphical editor give you a "snap to grid" feature, with the grid size being epsilon). Also you need to be careful that in double reprsentations there are positive 0 and negative 0, and you should also treat them as the same value.Something like this:
Furthermore, each square has four points. You can add a rule in your program saying that the four points must be in order as used in the algorithm (P0->P1->P2->P3) with the set angular relationship (see the algorithm above). However, you also need to be careful that the given the same four points there are four options to choose the start point. So your Square object code must treat the following squares specified by these four points as equivalent:
This can be done in the constructor of the Square object and always "canonicalize" the input by picking a point with a certain sailent feature as the starting point (e.g. pick the point having the lowest x, and if its x value tie with another point, then pick the point having the lowest x and smaller y among the tied pair)
Test Input 1
Test Result 1
Test Input 2
Test Result 2
JUnit Test Program testing
Point2#getXsnapped()(fragment only)Output of JUnit Test
Caveat
Eric Duminil is correct in pointing out that there can be 2 points arbitrarily close to one another, and still be snapped to different points on the grid.
Off the top of my head, I don't know how to solve this problem. Suggestions are welcome!
E.g.
With these added debugging code:
Util.debugPrint():
I would get following output -- the two points are considered different!