检测点列表中的正方形

Question

检测点列表中的正方形

6

我希望测试一个点对象列表中是否存在一个正方形。

这是我的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());
    }
}

我可以测试四个点是否构成正方形：

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;
    }

但我没有找到在一个点列表中搜索正方形的最佳方法。

你能帮帮我吗！！！

- Mohamed

1

列表中形成正方形的点是连续的吗？ - StaticBeagle

3个回答

1

这是一个时间复杂度为O(n^2 lg(n))，空间复杂度为O(n)的算法。如果按角度对顶点进行预排序，则对于每对{A,B}，您可以找到OC和OD两个角度。

compute angle for every point -- O(n)
sort point by angles -- O(n*lg(n))
for each pair -- O(n^2*lg(n))
    if (B.x > A.x) && (B.y > A.y)
        compute positions of C and D
        compute angles of C and D
        for C and D
            if there is a pair of points with same angles and same positions
                return true
return false

如何找到C的坐标：

Xc = Xb - (Yb - Ya)
Yc = Yb + (Xb - Xa)

- Yola

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相同。如果是，则您刚刚检测到一个正方形。

下图说明了这个想法。

数据结构

如果方块是可旋转的，那么点的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()) {
        // 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值与另一个点相等，则选择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

- leeyuiwah

不好意思，那是一个很好的观点。我会看看是否能够稍后提供更新的答案。 - leeyuiwah

感谢指出正方形可能需要旋转的要求。我已经更新了上面的答案。 - leeyuiwah

@Eric -- 我不确定你所说的是否正确。我刚刚添加了一个JUnit测试用例（并将其添加到我的答案中）。我认为我的Point2#getXsnapped()表现如预期 - 它将不精确的double坐标转换为精确的long，以便在equals()和hashCode()中使用是安全的。 - leeyuiwah

1

@leeyuiwah：抱歉，我选错了例子。a=eps*0.5;和b=eps*0.49999999999999;。a和b相差1E-17，但没有被捕捉到同一点。我认为这就是你的O(n**2)的来源。你的算法将会输出错误的结果。 - Eric Duminil

1

我不确定，但我认为 https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search 或 https://en.wikipedia.org/wiki/Quadtree 可以帮助你。 - Eric Duminil

显示剩余5条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Egor Skriptunoff · Accepted Answer

对于所有点对，计算它们的角度、长度和中间点。这将需要O(n^2)时间。
对于每组具有相同中间点和相同长度的点对，按照角度排序，总共需要O(n^2*log(n))的时间。这将帮助您找到两条长度相同且中间点相同的正交对角线（即正方形！）。
算法的总时间复杂度为O(n^2*log(n))。