在点列表中检测正方形 [英] Detect square in a List of Points
问题描述
我想测试Point对象列表中是否有一个正方形.
I want to test if there is a square in a list of Point object or not.
这是我的Point课:
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());
}
}
我可以测试四个Point是否为正方形:
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;
}
但是我没有找到在Point点列表中搜索正方形的最佳方法.
But I didn't found the best way to search the square in a list of Point.
你能帮帮我吗！
推荐答案
已更新为还检测到旋转正方形
我喜欢以上Egor Skriptunoff的回答，但让我尝试给出 另一个答案.我认为复杂度仅为O(N ^ 2).
I like Egor Skriptunoff's answer above, but let me try to give another answer. I think the complexity is only O(N^2).
算法
对于任意一对点(P0，P1)(其中有N ^ 2个)，找出 从P0到P1的向量V01，然后将该向量旋转90 度(变为V12).将其添加到P1，看看是否可以找到一个点 那里? (这可以通过哈希映射查找完成-参见下文) 那么您拥有P2，然后继续执行该过程.
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.
再将向量旋转90度(变为V23)，将其添加到
P2，看看是否可以在那里找到要点? (再次，通过哈希图查找)
如果是这样，则您拥有P3，然后继续执行该步骤.
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.
再将向量旋转90度(变为V34).加上它 到P3，看看是否可以找到一个点? (再次，通过哈希图查找). 如果是这样，还检查该点P4是否与P0相同.如果是这样的话 您刚刚检测到一个正方形.
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.
下图说明了这个想法.
数据结构
如果正方形是可旋转的，则Point的x和y坐标 必须为浮点数(双精度)，并且不能为整数.因为 很多计算会给您不合理的数字(例如sqrt(2))
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))
但是，双精度表示形式不能精确地表示为整数， 所以我们要小心点 将两个足够接近的双精度数视为同一个双精度数 价值.在我的代码中，我使用epsilon作为我们允许的公差 表示近似当量".我选择1E-3作为epsilon.
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.
public class Point2 {
private double x;
private double y;
private final double eps = 1E-3;
public double getEps() {
return eps;
}
然后在有关equals()和hashCode()的所有计算中，
确保使用x和y的快照"值，而不是它们的原始值
双重表示. (从图形上您可以像您这样想象
图形编辑器为您提供捕捉到网格"功能，并具有网格大小
正在epsilon).另外，您还需要注意，在双重表示中
有正0和负0，您也应该将它们视为
相同的值.
And then in all computation regarding equals() and hashCode(),
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.
类似这样的东西:
public long getXsnapped() {
return Math.round(this.getX()/this.getEps());
}
public long getYsnapped() {
return Math.round(this.getY()/this.getEps());
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
long temp;
temp = Double.doubleToLongBits(eps);
result = prime * result + (int) (temp ^ (temp >>> 32));
if (Math.abs(this.getX())>this.getEps()) {
// include X only if it is larger than eps
temp = this.getXsnapped();
result = prime * result + (int) (temp ^ (temp >>> 32));
}
if (Math.abs(this.getY())>this.getEps()) {
temp = this.getYsnapped();
result = prime * result + (int) (temp ^ (temp >>> 32));
}
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point2 other = (Point2) obj;
if (Double.doubleToLongBits(eps) != Double.doubleToLongBits(other.eps))
return false;
boolean answer = true;
if (Math.abs(this.getX())>this.getEps()
|| Math.abs(other.getX())>this.getEps()) {
// compare value and sign only if X of both points are larger than eps
if (this.getXsnapped()!= other.getXsnapped())
answer = false;
}
if (Math.abs(this.getY())>this.getEps()
|| Math.abs(other.getY())>this.getEps()) {
// compare value and sign only if Y of both points are larger than eps
if (this.getYsnapped()!= other.getYsnapped())
answer &= false;
}
boolean isDebug = false;
Util.debugPrint(isDebug, "p1 %s; p2 %s: %b (eps is %.9f)%n"
, this, other, answer, this.getEps());
return answer;
}
此外，每个正方形都有四个点.您可以在其中添加规则 您的程序说这四个点必须按顺序使用 具有设定角度关系的算法(P0-> P1-> P2-> P3) (请参见上面的算法).但是，您还需要注意 在给定相同的四个点的情况下，有四个选项可供选择 起点.因此，您的Square对象代码必须对待 这四个点指定的以下平方等价:
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:
P0->P1->P2->P3
P1->P2->P3->P0
P2->P3->P0->P1
P3->P0->P1->P2
这可以在Square对象的构造函数中完成，并且始终 通过规范化"输入 选择具有特定特征的点 作为起点(例如，选择x最低的点，然后 如果其x值与另一个点关联，则选择具有最低点的点 x和小于y的对)
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)
测试输入1
-1.4142, 9.8995
-5.6569, 15.5563
1.4142, 9.8995
-1.4142, 14.1421
-2.1213, 14.8492
1.4142, 14.1421
0.0000, 15.5563
-2.1213, 17.6777
7.0711, 11.3137
5.6569, 12.7279
4.2426, 14.1421
6.3640, 10.6066
7.0711, 14.1421
5.6569, 15.5563
1.4142, 19.7990
7.7782, 14.8492
测试结果1
===== Given a set of following points from file src\detectSquare\inputSet1_45_1_1_0_0.txt =====
1: Point2 [x=-1.4142, y=9.8995]
2: Point2 [x=-5.6569, y=15.5563]
3: Point2 [x=1.4142, y=9.8995]
4: Point2 [x=-1.4142, y=14.1421]
5: Point2 [x=-2.1213, y=14.8492]
6: Point2 [x=1.4142, y=14.1421]
7: Point2 [x=0.0000, y=15.5563]
8: Point2 [x=-2.1213, y=17.6777]
9: Point2 [x=7.0711, y=11.3137]
10: Point2 [x=5.6569, y=12.7279]
11: Point2 [x=4.2426, y=14.1421]
12: Point2 [x=6.3640, y=10.6066]
13: Point2 [x=7.0711, y=14.1421]
14: Point2 [x=5.6569, y=15.5563]
15: Point2 [x=1.4142, y=19.7990]
16: Point2 [x=7.7782, y=14.8492]
===== The following squares have been found =====
1: SquareRotatable [points=[Point2 [x=4.2427, y=14.1421], Point2 [x=5.6569, y=12.7279], Point2 [x=7.0711, y=14.1421], Point2 [x=5.6569, y=15.5563]]]
测试输入2
0.0000, 0.0000
-0.7071, 0.7071
-1.4142, 1.4142
0.7071, 0.7071
0.0000, 1.4142
-0.7071, 2.1213
1.4142, 1.4142
0.7071, 2.1213
0.0000, 2.8284
测试结果2
===== Given a set of following points from file src\detectSquare\inputSet2_45_0_0_0_0.txt =====
1: Point2 [x=0.0000, y=0.0000]
2: Point2 [x=-0.7071, y=0.7071]
3: Point2 [x=-1.4142, y=1.4142]
4: Point2 [x=0.7071, y=0.7071]
5: Point2 [x=0.0000, y=1.4142]
6: Point2 [x=-0.7071, y=2.1213]
7: Point2 [x=1.4142, y=1.4142]
8: Point2 [x=0.7071, y=2.1213]
9: Point2 [x=0.0000, y=2.8284]
===== The following squares have been found =====
1: SquareRotatable [points=[Point2 [x=-1.4142, y=1.4142], Point2 [x=0.0000, y=0.0000], Point2 [x=1.4142, y=1.4142], Point2 [x=0.0000, y=2.8284]]]
2: SquareRotatable [points=[Point2 [x=-0.7071, y=0.7071], Point2 [x=0.7071, y=0.7071], Point2 [x=0.7071, y=2.1213], Point2 [x=-0.7071, y=2.1213]]]
3: SquareRotatable [points=[Point2 [x=-1.4142, y=1.4142], Point2 [x=-0.7071, y=0.7071], Point2 [x=0.0000, y=1.4142], Point2 [x=-0.7071, y=2.1213]]]
4: SquareRotatable [points=[Point2 [x=-0.7071, y=2.1213], Point2 [x=0.0000, y=1.4142], Point2 [x=0.7071, y=2.1213], Point2 [x=-0.0000, y=2.8284]]]
5: SquareRotatable [points=[Point2 [x=-0.7071, y=0.7071], Point2 [x=0.0000, y=0.0000], Point2 [x=0.7071, y=0.7071], Point2 [x=0.0000, y=1.4142]]]
6: SquareRotatable [points=[Point2 [x=0.0000, y=1.4142], Point2 [x=0.7071, y=0.7071], Point2 [x=1.4142, y=1.4142], Point2 [x=0.7071, y=2.1213]]]
JUnit测试程序测试Point2#getXsnapped()(仅限片段)
JUnit Test Program testing Point2#getXsnapped() (fragment only)
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Ignore;
import org.junit.Test;
public class Point2Test {
private List<Point2> points = new ArrayList<>();
@Before
public void setUp() throws Exception {
points.add(new Point2(0.49999999f, 0));
points.add(new Point2(0.50000001f, 0));
}
...
@Test
public void testGetXsnapped() {
System.out.format("testing xSnapped of two points: %s and %s%n"
, points.get(0), points.get(1));
System.out.format("and they are %d and %d respectively%n"
, points.get(0).getXsnapped()
, points.get(1).getXsnapped());
System.out.format("(Note: epsilon is %f)%n"
, points.get(0).getEps());
assertEquals(points.get(0).getXsnapped()
, points.get(1).getXsnapped());
}
}
JUnit测试的输出
testing xSnapped of two points: Point2 [x=0.5000, y=0.0000] and Point2 [x=0.5000, y=0.0000]
and they are 500 and 500 respectively
(Note: epsilon is 0.001000)
注意事项
埃里克·杜米尼尔(Eric Duminil)指出可能存在 2个点任意彼此靠近，仍然被捕捉到网格上的不同点.
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!
例如
@Before
public void setUp() throws Exception {
Point2 dummy = new Point2(0, 0); // just to get epsilon
points.add(new Point2(dummy.getEps()*0.5, 0));
points.add(new Point2(dummy.getEps()*0.49999999999999, 0));
}
添加了以下调试代码:
public long getXsnapped() {
boolean isDebug = true;
String _ = " "; // indent
double X = this.getX();
Util.debugPrint(isDebug, _ + "X is %E (long bits is 0x%x)%n"
, X, Double.doubleToLongBits(X));
double eps = this.getEps();
Util.debugPrint(isDebug, _ + "eps is %E%n", eps);
double fraction = X/eps;
Util.debugPrint(isDebug, _ + "fraction is %E (long bits is 0x%x)%n"
, fraction, Double.doubleToLongBits(fraction));
long answer = Math.round(fraction);
Util.debugPrint(isDebug, _ + "xSnapped is %d%n", answer);
return answer;
}
Util.debugPrint():
Util.debugPrint():
public static void debugPrint(boolean isDebug, String format, Object... args) {
if (!isDebug) {
return; // don't print
}
System.out.format(format, args);
}
我将得到以下输出-两点被认为是不同的！
I would get following output -- the two points are considered different!
testing xSnapped of two points: Point2 [x=0.0005, y=0.0000] and Point2 [x=0.0005, y=0.0000]
X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9fc)
eps is 1.000000E-03
fraction is 5.000000E-01 (long bits is 0x3fe0000000000000)
xSnapped is 1
X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9a0)
eps is 1.000000E-03
fraction is 5.000000E-01 (long bits is 0x3fdfffffffffff4c)
xSnapped is 0
and they are 1 and 0 respectively
(Note: epsilon is 0.001000)
delta between the two x (as double) is 9.974660E-18
X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9fc)
eps is 1.000000E-03
fraction is 5.000000E-01 (long bits is 0x3fe0000000000000)
xSnapped is 1
X is 5.000000E-04 (long bits is 0x3f40624dd2f1a9a0)
eps is 1.000000E-03
fraction is 5.000000E-01 (long bits is 0x3fdfffffffffff4c)
xSnapped is 0
这篇关于在点列表中检测正方形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
