2

所以我想写一个简单的方法，它接受四个坐标并决定它们是否形成一个正方形。我的方法是从一个点开始，计算其他三个点与基点之间的距离。由此我们可以得到具有相同值的两条边和一条对角线。然后我使用毕达哥拉斯定理来确定边平方是否等于对角线。如果是 isSquare 方法返回 true 否则为 false。我想要的东西找出我可能会错过的某些情况，或者该方法是否有问题。感谢您的所有帮助。

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;

}
}
4

7 回答 7

7

您知道，您可以更轻松地进行相同的检查。您只需要检查两件事：“四个点构成一个平行四边形”和“其中一个角度是正确的”。

首先是真的P3 = P1 + (P2-P1) + (P4-P1)

第二个什么时候(P2-P1)*(P4-P1) = 0

A*B点积在哪里(A.x * B.x + A.y * B.y)

这里唯一的问题是计算错误。您不能期望浮点数完全相等，因此A=B您应该考虑使用类似abs(A-B) < Ewhere Eis small enough for your case 之类的东西。

于 2013-08-02T05:41:26.030 回答
3

这是一个角落案例：

如果 dist1 是正方形的对角线距离怎么办？（我假设这 4 个点是任意顺序的。）

您可能需要再次检查距离：

if(dist1 == dist2){
    //do stuff
}
else if(dist1 == dist3){
    //do stuff
}
else if(dist2 == dist3){
    //do stuff
}
else return false;
于 2013-08-01T23:42:42.353 回答
2

您的功能并未考虑所有因素。你只是在检查一个点与其他点。jwpat7提到了这一点，所以这里有一个例子：

坏广场！

假设这些点的顺序是：（红​​、黄、绿、蓝），并且网格上的每个块都是一个。

你的distance1和distance2都等于 4，所以你本质上是说最后一点可以是distance3 = 8. 这是蓝线。如果最后一点在该线上的任何位置，您只需将其批准为正方形。

您可以通过执行相同的检查轻松解决此问题，但使用下一个坐标作为“基础”，而不是 0。如果您的检查通过了两个点，那么它肯定是一个正方形。

选择：

您可以检查它是否不是正方形。在一个有效的正方形中，只有两个有效距离，边长（s）和对角线长度（d）。

由于您使用的是平方距离，d = s * 2

如果任何距离（只有六个）不等于d或s，则它不能是正方形。如果所有六个都这样做，它必须是一个正方形。

好处是如果你检查以证明它是一个正方形，你必须做所有六次距离检查。如果你想证明它不是一个正方形，你可以在找到一个坏的之后停下来。

所以，这取决于你的数据。如果您期望的正方形多于非正方形，则可能需要检查正方形。如果您期望更多的非正方形，则应检查非正方形。这样，即使最坏的情况速度较慢，您也会得到更好的平均情况。

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;
}
于 2013-08-03T05:34:19.457 回答
1

如果您添加else if(dist2 == dist3){...}替代方案（如另一个答案中所建议的那样），那么当四个点形成一个正方形时，您的方法确实isSquare会识别一个正方形。但是，您的代码也会将一些非正方形报告为正方形。例如，考虑点集 {(0,0), (1,1), (0,-1), (-1,0)}。那么您的distance1,2,3值分别为 2、1、1，这将满足dist2 == dist3案例中的测试。

任何非退化四边形总共有六个角间距离。知道其中五个距离会将剩余距离限制为两个值之一；也就是说，它不会唯一地约束它。所以我想基于角间距离的平方测试方法必须计算和测试所有六个。

于 2013-08-02T01:08:51.850 回答
0

这有意义吗？

<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>

输出：

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
于 2013-08-02T15:21:28.157 回答
0

您没有正确使用勾股定理。勾股定理指出，两条腿的平方和是对角线的平方，您将其解释为两条腿的和等于对角线。您应该将其用于勾股定理测试：

if (distance3 == Math.sqrt(distance1*distance1 + distance2*distance2)) {
    return true;
}
于 2013-08-01T23:35:39.443 回答
0

如果您使用类似（我的 C 代码）之类的东西，我使用平方距离（以避免 sqrt）：

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

其中 Point 很简单：

typedef struct {
    int x, y;
} Point;

`

在您的代码中，计算每个角的排列，找到最小/最大边（平方值），然后您可以检查您是否有 4 条边和 2 条对角线：

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");

您可以更改该error值以处理浮点错误——如果您想将此例程转换为处理浮点值。

注意：如果所有点都在同一个位置，我认为这是一个点（不是正方形）。

于 2016-03-06T05:46:16.467 回答