Java 给定四个坐标检查它是否形成一个正方形
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18006377/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Given four coordinates check whether it forms a square
提问by luckysing_noobster
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.
所以我想写一个简单的方法，它接受一组四个坐标并决定它们是否形成一个正方形。我的方法是从一个点开始计算其他三个点与基点之间的距离。由此我们可以获得具有相同值的两条边和一条对角线。然后我使用毕达哥拉斯定理来查找边平方是否等于对角线。如果是isSquare方法返回true else 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;
}
}
回答by tbodt
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;
}
回答by masotann
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.)
如果 dist1 是正方形的对角线距离呢？（我假设这 4 点的顺序是任意的。）
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;
回答by James Waldby - jwpat7
If you add an else if(dist2 == dist3){...}alternative (as suggested in another answer also) then it is true that your isSquaremethod 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,3values are 2, 1, 1, respectively, which will satisfy the tests in the dist2 == dist3case.
如果您添加一个else if(dist2 == dist3){...}替代方案（也如另一个答案中所建议的那样），那么isSquare当四个点形成一个正方形时，您的方法确实会识别一个正方形。但是，您的代码也会将一些非正方形报告为正方形。例如，考虑点集 {(0,0), (1,1), (0,-1), (-1,0)}。那么你的distance1,2,3值分别是 2、1、1，这将满足dist2 == dist3案例中的测试。
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.
任何非退化四边形共有六个角间距离。知道其中的五个距离会将剩余的距离限制为两个值中的任何一个；也就是说，它不会唯一地限制它。所以我想基于角间距离的平方测试方法必须计算和测试所有六个。
回答by akalenuk
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)
第一个是真的 P3 = P1 + (P2-P1) + (P4-P1)
And the second when (P2-P1)*(P4-P1) = 0
第二个当 (P2-P1)*(P4-P1) = 0
Where A*Bis a dot product (A.x * B.x + A.y * B.y)
A*B点积在哪里(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=Byou should consider using something like abs(A-B) < Ewhere Eis small enough for your case.
这里唯一的问题是计算错误。您不能期望浮点数完全相等，因此A=B您应该考虑使用诸如abs(A-B) < Ewhere 之类的东西E对于您的情况来说足够小。
回答by ???? ????
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
回答by Geobits
Your function doesn't take everything into account. You're only checking one point against the others. jwpat7mentions this, so here's an example:
您的函数并未考虑所有内容。你只是检查一个点与其他点。jwpat7提到了这一点，所以这里有一个例子：
Assume the points are in this order: (red, yellow, green, blue), and each block on the grid is one.
假设点的顺序是：（红、黄、绿、蓝），网格上的每个块都是一个。
Your distance1and distance2will both be equal to 4, so you're essentially saying that the last point can be anypoint where distance3 = 8. This is the blue line. If the last point is anywhere on that line, you just approved it as square.
你distance1和distance2都将是等于4，所以你基本上说，最后一点可能是任何地步distance3 = 8。这是蓝线。如果最后一个点在该线上的任何位置，则您只是将其批准为正方形。
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 definitelya square.
您可以通过执行相同的检查轻松解决此问题，但使用下一个坐标作为“基础”，而不是 0。如果您的检查通过了两个点，则它肯定是一个正方形。
Alternative:
选择：
You can check if it's nota square. In a valid square, there are only two valid distances, side length(s), and diagonal length(d).
您可以检查它是否不是正方形。在一个有效的正方形中，只有两个有效距离，边长（s）和对角线长度（d）。
Since you're using squared distance, d = s * 2
由于您使用的是平方距离， d = s * 2
If anydistance(there are only six) does not equal either dor s, it cannotbe a square. If all sixdo, it mustbe a square.
如果任何距离（只有六个）不等于d或s，则它不能是正方形。如果六个都这样，它一定是一个正方形。
The advantage is that if you check to prove it isa square, you have to do all six distance checks. If you want to prove it's nota 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;
}
回答by codeaperature
If you use something like (my C code), where I use squared distance (to avoid sqrt):
如果你使用类似（我的 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);
}
where Point is simply:
其中 Point 很简单：
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:
在您的代码中，计算每个角彼此的排列，找到最小/最大边（以平方值表示），然后您可以检查是否有 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");
You could change the errorvalue to handle floating points errors -- if you'd like to convert this routine to handle floating point values.
您可以更改该error值以处理浮点错误——如果您想将此例程转换为处理浮点值。
Note: If all points are at the same location, I consider this a point (not a square).
注意：如果所有点都在同一位置，我认为这是一个点（不是一个正方形）。
