Given four coordinates check whether it forms a square

Question

So I am trying to write a simple method which takes in set of four coordinates and decide whether they form a square or not.My approach is start with a point and calculate the distance between the other three points and the base point.From this we can get the two sides which have same value and the one which is a diagonal.Then I use Pythagoras theorem to find if the sides square is equal to the diagonal.If it is the isSquare method return true else false.The thing I want to find out is there some cases I might be missing out on or if something is wrong with the approach.Thanks for the all the help.

public class CoordinatesSquare {

public static boolean isSquare(List<Point> listPoints) {
    if (listPoints != null && listPoints.size() == 4) {
        int distance1 = distance(listPoints.get(0), listPoints.get(1));
        int distance2 = distance(listPoints.get(0), listPoints.get(2));
        int distance3 = distance(listPoints.get(0), listPoints.get(3));

        if (distance1 == distance2) {
            // checking if the sides are equal to the diagonal
            if (distance3 == distance1 + distance2) {
                return true;
            }

        } else if (distance1 == distance3) {
            // checking if the sides are equal to the diagonal
            if (distance2 == distance1 + distance3) {
                return true;
            }

        }
    }
    return false;
}

private static int distance(Point point, Point point2) {
              //(x2-x1)^2+(y2-y1)^2
    return (int) (Math.pow(point2.x - point.x, 2) + (Math.pow(point2.y
            - point.y, 2)));
}

public static void main(String args[]) {
    List<Point> pointz = new ArrayList<Point>();
    pointz.add(new Point(2, 2));
    pointz.add(new Point(2, 4));
    pointz.add(new Point(4, 2));
    pointz.add(new Point(4, 4));
    System.out.println(CoordinatesSquare.isSquare(pointz));
}
}


//Point Class
 public class Point {
Integer x;
Integer y;
boolean isVisited;

public Point(Integer x, Integer y) {
    this.x = x;
    this.y = y;
}

@Override
public boolean equals(Object obj) {
    if(obj!=null && obj.getClass().equals(this.getClass())){
        return ((Point) obj).x.equals(this.x)&&((Point) obj).y.equals(this.y);
    }
    return false;

}
}

Solution 1

You know, you can do the same check much easier. You just have to check two things: "four points make a parallelogram" and "one of its angles is right".

First is true when P3 = P1 + (P2-P1) + (P4-P1)

And the second when (P2-P1)*(P4-P1) = 0

Where A*B is a dot product (A.x * B.x + A.y * B.y)

The only catch here is computational error. You can't expect floats to be exactly equal, so instead of A=B you should consider using something like abs(A-B) < E where E is small enough for your case.

Solution 2

Here's a corner case:

What if dist1 is the diagonal distance of the square? (I'm assuming the 4 points are in arbitrary order.)

You probably need to do another check for the distances:

if(dist1 == dist2){
    //do stuff
}
else if(dist1 == dist3){
    //do stuff
}
else if(dist2 == dist3){
    //do stuff
}
else return false;

Solution 3

Your function doesn't take everything into account. You're only checking one point against the others. jwpat7 mentions this, so here's an example:

Assume the points are in this order: (red, yellow, green, blue), and each block on the grid is one.

Your distance1 and distance2 will both be equal to 4, so you're essentially saying that the last point can be any point where distance3 = 8. This is the blue line. If the last point is anywhere on that line, you just approved it as square.

You can fix this easily by doing the same check , but using the next coordinate as the 'base', instead of 0. If your check passes for two points, it's definitely a square.

---

Alternative:

You can check if it's not a square. In a valid square, there are only two valid distances, side length(s), and diagonal length(d).

Since you're using squared distance, d = s * 2

If any distance(there are only six) does not equal either d or s, it cannot be a square. If all six do, it must be a square.

The advantage is that if you check to prove it is a square, you have to do all six distance checks. If you want to prove it's not a square, you can just stop after you find a bad one.

So, it depends on your data. If you're expecting more squares than non-squares, you might want to check for squareness. If you expect more non-squares, you should check for non-squareness. That way you get a better average case, even though the worst case is slower.

public static boolean isSquare(List<Point> points){
    if(points == null || points.size() != 4)
        return false;
    int dist1 = sqDistance(points.get(0), points.get(1));
    int dist2 = sqDistance(points.get(0), points.get(2));
    if(dist1 == dist2){ //if neither are the diagonal
        dist2 = sqDistance(points.get(0), points.get(3));
    }
    int s = Math.min(dist1, dist2);
    int d = s * 2;

    for(int i=0;i<points.size;i++){
        for(int j=i+1;j<points.size();j++){
            int dist = sqDistance(points.get(i), points.get(j));
            if(dist != s && dist != d))
                return false;
        }
    }
    return true;
}

Solution 4

If you add an else if(dist2 == dist3){...} alternative (as suggested in another answer also) then it is true that your isSquare method will recognize a square when the four points form a square. However, your code will also report some non-squares as being squares. For example, consider the set of points {(0,0), (1,1), (0,-1), (-1,0)}. Then your distance1,2,3 values are 2, 1, 1, respectively, which will satisfy the tests in the dist2 == dist3 case.

Any non-degenerate quadrilateral has a total of six inter-corner distances. Knowing five of those distances constrains the remaining distance to either of two values; that is, it doesn't uniquely constrain it. So I imagine that a square-testing method based on inter-corner distances will have to compute and test all six of them.

View more solutions

Comments

[collapsar]

In fact, he does - his distance Function actually Computes the square distance.

[tbodt]

@collapsar I didn't see that

[luckysing_noobster]

the distance method squares the distance.

[collapsar]

you need to be sure that p1, p2 are not adjacent. nonetheless, +1

[Geobits]

To make sure the points are in the right order, see stackoverflow.com/q/18084065/752320