java - 由于浮点精度误差导致的分割平方问题

Question

我有一个问题(在 JAVA 中)由于浮点精度错误而无法解决。

我有一个轴对齐的方形类，它通过指定 2 个点来定义。在构造函数中，确定最大距离是多少(在 x 或 y 方向)，这用于创建正方形，点与中心的距离相等。这意味着点在边界上。

例如，如果我用点 (0, 2) 和 (3, 3) 定义一个正方形，最大距离是 x 距离 (3)，正方形将定义如下:

• 左下角 = (0, 1)
• 右上角点 = (3, 4)

可以看出点在边缘，点的中点正好是正方形(1.5，2.5)的中心。

我创建了一个方法来检查正方形是否包含某个点，它看起来像这样:

see added code sample below

这意味着如果一个点在边界上，它就被“包含”。

现在我想将正方形分割为 4 个“相等”大小的部分(东北、西北、西南和东南)，逻辑上定义原始正方形的初始点必须至少包含在 1的部分。但是当单元测试它失败的随机点时，看起来是因为 double 浮点错误。

我尝试了不同的解决方法，最后一次迭代如下:

• 使用初始点定义正方形的中点 (p0)
• 用初始点+中点定义正方形的4个角点(p1,p2,p3 p4顺时针方向，从左下角开始)

这保证包含原始点，我可以轻松创建分割，我认为如果我确保不执行数学运算，它保证至少包含 1 个部分的原始点关于定义正方形的点的特征(因为它们在边界上)。我的分割套路如下:

see added code sample below

但是当使用随机点运行大量迭代的单元测试时，几乎每 16 次中就有 1 次仍然失败，而且我不知道为什么边缘点会发生变化。在所有这些测试中，初始包含检查(父方 block 是否包含点，尽管它们位于边缘)通过 100%。

编辑显示我的实现的一些实际代码:

public class Point implements IPoint {
    double x, y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public double x() {
        return x;
    }

    @Override
    public double y() {
        return y;
    }

    @Override
    public IPoint midPoint(IPoint other) {
        return new Point((x() + other.x()) / 2, (y() + other.y()) / 2);
    }
}

public class Rectangle implements IRectangle {
    IPoint p0, p1, p2, p3, p4;

    public Rectangle(IPoint v1, IPoint v2) {
        double dx, dy, dl;
        IPoint v0;

        // calculate dominant length
        dx = Math.abs(v1.x() - v2.x());
        dy = Math.abs(v1.y() - v2.y());
        dl = dx >= dy ? dx : dy;

        if (dx >= dy) {
            // make sure v0 = left-most
            if (v1.x() <= v2.x()) {
                v0 = v1;
                v1 = v2;
            } else {
               v0 = v2;
            }
        } else {
            // make sure v0 = bottom-most
            if (v1.y() <= v2.y()) {
                v0 = v1;
                v1 = v2;
            } else {
                v0 = v2;
            }
        }

        this.p0 = v0.midPoint(v1);
        if (dx >= dy) {
            // this way v0 and v1 are always on the vertical boundaries
            this.p1 = new Point(v0.x(), this.p0.y() - dl / 2);
            this.p2 = new Point(v0.x(), this.p0.y() + dl / 2);
            this.p3 = new Point(v1.x(), this.p0.y() + dl / 2);
            this.p4 = new Point(v1.x(), this.p0.y() - dl / 2);
        } else {
            // this way v0 and v1 are always on the horizontal boundaries
            this.p1 = new Point(this.p0.x() - dl / 2, v0.y());
            this.p2 = new Point(this.p0.x() - dl / 2, v1.y());
            this.p3 = new Point(this.p0.x() + dl / 2, v1.y());
            this.p4 = new Point(this.p0.x() + dl / 2, v0.y());
        }
    }

    @Override
    public boolean contains(IPoint p) {
        if (p.x() < p1.x() || p.x() > p4.x()) return false;
        if (p.y() < p1.y() || p.y() > p2.y()) return false;
        return true;
    }

    @Override
    public IRectangle[] subdivide() {
        return new Rectangle[] {
            new Rectangle(p0, p2),
            new Rectangle(p0, p3),
            new Rectangle(p0, p4),
            new Rectangle(p0, p1)
        };
    }
}

这是测试用例:

@Test
public void testMassedSubdivide() throws Exception {
    Random r = new Random();
    IPoint p1, p2;
    IRectangle[] rects;
    boolean check1, check2;
    for (int i = 0; i < 100000; i++) {
        p1 = new Point(r.nextDouble(), r.nextDouble());
        p2 = new Point(r.nextDouble(), r.nextDouble());
        q = new Rectangle(p1, p2);
        assertTrue(q.contains(p1));
        assertTrue(q.contains(p2));

        rects = q.subdivide();
        check1 = rects[0].contains(p1) || rects[1].contains(p1) || rects[2].contains(p1) || rects[3].contains(p1);
        check2 = rects[0].contains(p2) || rects[1].contains(p2) || rects[2].contains(p2) || rects[3].contains(p2);
        assertTrue(check1);
        assertTrue(check2);
    }
}

我的随机测试导致的失败案例之一:

p1 = (0.31587198758298796,  0.12796964677511913)
p2 = (0.04837609765424089,  0.6711236142940149)

这个失败了，因为 p1 应该在东南扇区，但是那个定义为:

p0=(0.31791253449833834,    0.2637581386548431),    
p1=(0.18212404261861442,    0.12796964677511916), <- wrong, last 6 should be 3  
p2=(0.18212404261861442,    0.39954663053456707),   
p3=(0.4537010263780623,     0.39954663053456707),   
p4=(0.4537010263780623,     0.12796964677511916)  <- wrong, last 6 should be 3

Answer 1

查看您的代码后，它会失败没有任何意义，因为据我所知，您没有对失败中的 Y 值应用任何操作案例 - 你只是在没有任何操作的情况下通过它，所以浮点精度损失是无关紧要的。但是，当 p1-p4 可以表示任何角时，我有点难以理解，所以我重写了 Rectangle 类如下，希望更清楚一点:

public class Rectangle implements IRectangle {
    IPoint centroid, bottomLeft, topLeft, bottomRight, topRight;

    public Rectangle(IPoint v0, IPoint v1) {
        IPoint bottomLeft = new Point(Math.min(v0.x, v1.x), Math.min(v0.y, v1.y));
        IPoint topRight   = new Point(Math.max(v0.x, v1.x), Math.max(v0.y, v1.y));

        // calculate dominant length
        double dx = topRight.x - bottomLeft.x;
        double dy = topRight.y - bottomLeft.y;  // Assumes (0, 0) is in the bottom-left.
        double dl = dx >= dy ? dx : dy;

        this.centroid = bottomLeft.midPoint(topRight);
        if (dx >= dy) {
            // this way bottomLeft and topRight are always on the vertical boundaries
            this.bottomLeft  = new Point(bottomLeft.x(), this.centroid.y() - dl / 2);
            this.topLeft     = new Point(bottomLeft.x(), this.centroid.y() + dl / 2);
            this.bottomRight = new Point(topRight.x(), this.centroid.y() - dl / 2);
            this.topRight    = new Point(topRight.x(), this.centroid.y() + dl / 2);
        } else {
            // this way bottomLeft and topRight are always on the horizontal boundaries
            this.bottomLeft  = new Point(this.centroid.x() - dl / 2, bottomLeft.y());
            this.topLeft     = new Point(this.centroid.x() - dl / 2, topLeft.y());
            this.bottomRight = new Point(this.centroid.x() + dl / 2, bottomLeft.y());
            this.topRight    = new Point(this.centroid.x() + dl / 2, topLeft.y());
        }
    }

    @Override
    public boolean contains(IPoint p) {
        if (p.x() < bottomLeft.x() || p.x() > topRight.x()) return false;
        if (p.y() < bottomLeft.y() || p.y() > topRight.y()) return false;
        return true;
    }

    @Override
    public IRectangle[] subdivide() {
        return new Rectangle[] {
            new Rectangle(centroid, bottomLeft),
            new Rectangle(centroid, topLeft),
            new Rectangle(centroid, bottomRight),
            new Rectangle(centroid, topRight)
        };
    }
}

如果这不能解决问题，也许某些日志记录会在 0.12796964677511913 更改为 0.12796964677511916

时出现