由于浮点精度错误导致的java细分平方问题

3 周 Questions & Answers 109

我有一个问题（在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个部分中。但是，当单元测试这一点时，随机点失败了，看起来是因为双精度浮点错误

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

使用初始点定义正方形的中点（p0）
使用初始点+中点定义正方形的4个角点（顺时针方向的p1、p2、p3和p4，从左下角开始）

这保证了原始点被包含，并且我可以轻松创建细分，并且如果我确保没有对定义正方形的点的特征进行数学运算（因为它们位于边界上），它保证原始点被包含在至少一个部分中。我的细分程序如下：

see added code sample below

但是，当使用随机点运行大量迭代的单元测试时，几乎每16个点中就有1个仍然失败，我不知道为什么会更改边缘点。在所有这些测试中，初始包容检查（无论父正方形是否包含点，尽管它们位于边缘）通过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

Tags:

共 (2) 个答案

# 1 楼答案

我修好了！感谢您对0x24a537r9的所有帮助，因为这让它更清晰了。我添加了您的代码（并修复了一个拼写错误），但我们仍然错过了一个特殊情况，即它是一个完美的正方形，因此dx==dy

如果dx==dy，我们知道正方形的所有点，它们可以不使用dl相加。在我的失败案例中，它是一个完美的正方形，因此它将在第一个if子句中结束，并因此使用dl计算2个新的角点（这将导致浮点错误）

从逻辑上讲，它最终会变成一个正方形，因为我强迫它是正方形的

我的最终构造函数代码如下所示：

IPoint centroid, bottomLeft, topLeft, topRight, bottomRight;

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)  // special case where it is square <- important, because this one fixes the errors
    {
        this.bottomLeft = bottomLeft;
        this.topLeft = new Point(bottomLeft.x(), topRight.y());
        this.topRight = topRight;
        this.bottomRight = new Point(topRight.x(), bottomLeft.y());
    }
    else 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, topRight.y());
        this.bottomRight = new Point(this.centroid.x() + dl / 2, bottomLeft.y());
        this.topRight    = new Point(this.centroid.x() + dl / 2, topRight.y());
    }
}

# 2 楼答案

在查看代码之后，没有任何理由认为它会失败，因为据我所知，在这种失败的情况下，您没有对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时出现一些日志记录

Python中文网

有 Java 编程相关的问题?

由于浮点精度错误导致的java细分平方问题

共 (2) 个答案

# 1 楼答案

# 2 楼答案