java - 为什么 Opencv Imgproc.minAreaRect 以不同的顺序对相同的点(构成不对称三角形)给出不同的结果？

Question

当我运行时:

    @Test
    public void funkyTriangleContour2_forStack_works() {
        final var points = new Point[]{new Point(), new Point(1, 0), new Point(1, 2)};
        final var contour = new MatOfPoint2f(points);

        final var minRect = Imgproc.minAreaRect(contour);


        System.out.println("center: " + minRect.center);
        System.out.println("rotation: " + minRect.angle);
        System.out.println("width: " + minRect.size.width + " height: " + minRect.size.height);


        assertThat(minRect.size.area(), is(lessThan(2.0)));
        assertThat(minRect.size.area(), is(greaterThan(1.0)));
    }

它通过并给出:

center: {0.9000000953674316, 0.800000011920929}
rotation: 63.43495178222656
width: 2.2360680103302 height: 0.8944271206855774

但是当我改变不应该改变最小边界矩形的点的顺序时，我得到了不同的答案:

    @Test
    public void funkyTriangleContour2_forStack_fails() {
        final var points = new Point[]{new Point(1, 0), new Point(1, 2), new Point()};
        final var contour = new MatOfPoint2f(points);

        final var minRect = Imgproc.minAreaRect(contour);

        System.out.println("center: " + minRect.center);
        System.out.println("rotation: " + minRect.angle);
        System.out.println("width: " + minRect.size.width + " height: " + minRect.size.height);


        assertThat(minRect.size.area(), is(lessThan(2.0)));
        assertThat(minRect.size.area(), is(greaterThan(1.0)));
    }

失败并给出:

center: {0.5, 1.0}
rotation: 90.0
width: 2.0 height: 1.0

我对例程的理解是它给出了一个可以旋转的边界矩形以保持它包含所有点的小，所以点的顺序应该无关紧要。即使它指的是轮廓，旋转点也不应改变结果。

知道为什么会这样吗？

谢谢

Answer 1

这个问题实际上有两种不同的解决方案，如下图所示:

h 是 altitude to the hypotenuse p + q，其公式为h = (a * b)/(p + q)。

如果我们稍微重新排列一下，我们会得到 h * (p + q) = a * b -- 左侧现在代表绿色矩形的区域，右侧代表区域的红色矩形。因此，两个矩形的面积相同。

---

您看到的差异是由 float 的有限精度造成的。

我还没有研究算法，但似乎提供点的顺序决定了选择可能的多个解决方案中的哪一个，进而决定了错误是否会累积以及累积了多少(或者仅仅是由以下原因引起的)无法准确表示解的所有参数)。

---

事实上，事实证明该算法在 OpenCV 的历史上被多次修改——我能够从 3 个不同版本的 OpenCV 中获得 3 个不同的结果，对于相同顺序的完全相同的点。这里的部分问题还在于，如何使用 5 元组 OpenCV 描述同一个矩形有多种方法(我只通过宽度、高度和旋转角度看到了 4)。