在点列表中检测正方形

一尘不染

在点列表中检测正方形

algorithm

我想测试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点列表中搜索正方形的最佳方法。

你能帮助我吗！！！

阅读 260

2020-07-28

共1个答案

一尘不染

更新为还检测到旋转的正方形

我喜欢上面的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相同。如果是这样，则您刚刚检测到一个正方形。

下图说明了这种想法。

数据结构

如果正方形是可旋转的，则Point的x和y坐标必须在浮点中（双精度），并且不能为整数。因为大量的计算会给您不合理的数字（例如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的“快照”值，而不是它们的原始双精度表示形式。（在图形上，您可以想象这就像您的图形编辑器为您提供了“捕捉到栅格”功能，栅格大小为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对象的构造函数中完成此操作，并始终通过选择具有特定Sailent特征的点作为起点来“规范化”输入（例如，选择具有最低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);    // 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

2020-07-28