更新以便还能检测旋转的正方形
我喜欢Egor Skriptunoff上面的答案,但让我试着给出另一个答案。我认为复杂度只有O(N^2)。
算法
对于任意一对点(P0, P1)(共有N^2个),找出从P0到P1的向量V01,然后将该向量旋转90度(变成V12)。将其添加到P1中,并查看是否可以在那里找到一个点?(这可以通过哈希表查找来完成--请参见下文)如果是,则您有P2,并继续该过程。
将向量再旋转90度(变成V23),将其添加到P2中,并查看是否可以在那里找到一个点?(同样,通过哈希表查找)
如果是,则您有P3,并继续该过程。
将向量再旋转90度(变成V34)。将其添加到P3中,并查看是否可以在那里找到一个点?(同样,通过哈希表查找)如果是,则检查此点P4是否与P0相同。如果是,则您刚刚检测到一个正方形。
下图说明了这个想法。
![enter image description here](https://istack.dev59.com/8pBOt.webp)
数据结构
如果方块是可旋转的,那么点的x和y坐标必须为浮点数(double),不能是整数。因为很多计算会得到无理数(例如sqrt(2))。
然而,双精度表示不能像整数一样精确,因此我们必须小心地将两个足够接近的双精度数视为相同的双精度值。在我的代码中,我使用一个epsilon作为“近似等价”的公差容限。我选择了1E-3作为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的“捕捉”值,而不是它们的原始double表示。 (从图形上来看,您可以想象这就像您的图形编辑器提供了一个“对齐网格”功能,网格大小为epsilon)。此外,您需要注意,在双重表示中存在正0和负0,并且您还应将它们视为相同的值。
类似这样:
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()) {
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()) {
if (this.getXsnapped()!= other.getXsnapped())
answer = false;
}
if (Math.abs(this.getY())>this.getEps()
|| Math.abs(other.getY())>this.getEps()) {
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对象代码必须将由这四个点指定的以下正方形视为等效:
P0->P1->P2->P3
P1->P2->P3->P0
P2->P3->P0->P1
P3->P0->P1->P2
这可以在Square对象的构造函数中完成,并始终通过选择具有某些显著特征的点作为起点(例如,选择x最小的点,如果它的x值与另一个点相等,则选择x和y较小的点)来“规范化”输入。
测试输入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()
(仅片段)
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指出两个点可以任意接近,但仍然会被捕捉到网格上的不同点。
就我而言,我不知道如何解决这个问题。欢迎提出建议!
例如:
@Before
public void setUp() throws Exception {
Point2 dummy = new Point2(0, 0);
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 _ = " ";
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():
public static void debugPrint(boolean isDebug, String format, Object... args) {
if (!isDebug) {
return;
}
System.out.format(format, args);
}
我将得到以下输出——这两个点被认为是不同的!
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