Given four coordinates check whether it forms a sq

问题:

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;

}
}

回答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.

回答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;

回答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;
}

回答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.

回答5:

You are not using the Pythagorean Theorem correctly. The Pythagorean Theorem states that the sum of the squares of two legs is the square of the diagonal, and you are interpreting it to mean that the sum of the two legs is equal to the diagonal. You should use this for the Pythagorean Theorem testing:

if (distance3 == Math.sqrt(distance1*distance1 + distance2*distance2)) {
    return true;
}

回答6:

Does this make sense?

<script>

function isSquare(p1,p2,p3,p4){
  if ((areACorner(p1,p2,p3) && areACorner(p4,p2,p3))
   || (areACorner(p1,p2,p4) && areACorner(p3,p2,p4))
   || (areACorner(p1,p3,p4) && areACorner(p2,p3,p4))) return true

  return false
}

function areACorner(p1,p2,p3){
  //pivot point is p1
  return Math.abs(p2.y - p1.y) == Math.abs(p3.x - p1.x) 
      && Math.abs(p2.x - p1.x) == Math.abs(p3.y - p1.y)
}

</script>

Output:

console.log(isSquare({x:0,y:0},{x:1,y:1},{x:0,y:1},{x:1,y:0}))
true

console.log(isSquare({x:0,y:0},{x:1,y:1},{x:-1,y:-1},{x:1,y:0}))
false

回答7:

If you use something like (my C code), where I use squared distance (to avoid sqrt):

int sqDist(Point p1, Point p2) {
    int x = p1.x - p2.x;
    int y = p1.y - p2.y;
    return(x*x + y*y);
}

where Point is simply:

typedef struct {
    int x, y;
} Point;

`

In your code, calculate the permutations of each corner to one another, find the smallest / largest edges (in squared values), then you can check that you have 4 sides and 2 diagonals:

int squares[6];

squares[0] = sqDist(p[0], p[1]);
squares[1] = sqDist(p[0], p[2]);
squares[2] = sqDist(p[0], p[3]);
squares[3] = sqDist(p[1], p[2]);
squares[4] = sqDist(p[1], p[3]);
squares[5] = sqDist(p[2], p[3]);

int side = squares[0];
int diagonal = squares[0];
int i = 0;
while((++i <= 4) && (side >= diagonal)) {
    if(squares[i] < side) side = squares[i];
    if(squares[i] > diagonal) diagonal = squares[i];
}
int diagonal_cnt = 0;
int side_cnt = 0;
int error = 0;
for(int i = 0; i < 6; i++) {
   if(abs(side - squares[i]) <= error) side_cnt++;
   if(abs(diagonal - squares[i]) <= error) diagonal_cnt++;
}
printf("Square = %s\n", ((side_cnt == 4) && (diagonal_cnt == 2)) ? "true" : "false");

You could change the error value to handle floating points errors -- if you'd like to convert this routine to handle floating point values.

Note: If all points are at the same location, I consider this a point (not a square).