我想测试Point对象列表中是否有一个正方形。
这是我的Point课:
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是否为正方形:
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点列表中搜索正方形的最佳方法。
你能帮助我吗 !!!
最佳答案
已更新为还检测到旋转的正方形
我喜欢上面的Egor Skriptunoff的答案，但让我尝试给出
另一个答案。我认为复杂度仅为O(N ^ 2)。
算法
对于任意一对点(P0，P1)(其中有N ^ 2个)，找出
从P0到P1的 vector V01，然后将该 vector 旋转90
度(变为V12)。将其添加到P1，看看是否可以找到一个点
那里？ (这可以通过哈希映射查找来完成-参见下文)
则您拥有P2，然后继续该过程。
将 vector 再旋转90度(变为V23)，将其添加到
P2，看看是否可以在那里找到要点？ (同样，通过hashmap查找)
如果是这样，则您拥有P3，然后继续执行该步骤。
将 vector 再旋转90度(变为V34)。加上它
到P3，看看是否可以找到一个点？ (同样，通过哈希图查找)。
如果是这样，还检查该点P4是否与P0相同。如果是这样的话
您刚刚检测到一个正方形。
下图说明了这种想法。
数据结构
如果正方形是可旋转的，则Point的x和y坐标
必须为浮点数( double )，并且不能为整数。因为
大量的计算会给您不合理的数字(例如sqrt(2))
但是， double 表示形式不能精确地表示为整数，
所以我们要小心点
将两个足够接近的 double 数视为同一个 double 数
值(value)。在我的代码中，我使用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的“快照”值，而不是它们的原始值
双重表示。 (从图形上您可以像您这样想象
图形编辑器为您提供“捕捉到网格”功能，并具有网格大小
正在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()) {
// 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对象代码必须对待
这四个点指定的以下平方等价:
P0->P1->P2->P3
P1->P2->P3->P0
P2->P3->P0->P1
P3->P0->P1->P2
这可以在Square对象的构造函数中完成，并且始终
通过“规范化”输入
选择具有特定特征的点
作为起点(例如，选择x最低的点，然后
如果其x值与另一个点关联，则选择具有最低点的点
绑定(bind)对中的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)指出可能存在
2个点任意靠近，但仍被捕捉到网格上的不同点。
我不知道该如何解决这个问题。意见建议
受欢迎的!
例如。
@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():
public static void debugPrint(boolean isDebug, String format, Object... args) {
if (!isDebug) {
return; // don't print
}
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
关于java - 在点列表中检测正方形，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41199862/