java - 如何检测 3D 世界中的矩形？

Question

我有一组点。每个点都有三个坐标:X、Y 和 Z。我希望能够检测到矩形(!不是立方体!)的 角 的四个点:

1. 所有这些矩形的点可以有相同的 Z(因此，矩形没有绘制深度，只有 X 和 Y 改变)
2. 所有这些矩形的点可以具有相同的 Y(因此，矩形是按深度绘制的，只有 X 和 Z 发生变化)
3. 等等
4. 特别地，所有这些矩形的点都可以有变化的 X、Y 和 Z(即:矩形以“对角线”绘制)。

记住:“所有这些矩形的点”=“四个矩形的角”。

---

我的解决方案(仅适用于二维世界)

我写了一个算法来检测四个矩形的角，但目前它只适用于具有 2 个坐标(X 和 Y)的点。

算法是:

1. 我取集合的一个点A，我假设它是一个角
2. 我取集合的下一个点 B(如果 X 和 Y 与 A 的不同)，我假设它是对角线角
3. 我取下一个点 C，并检查它的 X 或 Y 是否与 A 或 B 相同'各自的 X 或 Y :如果是，我决定它是第三个角。我在第四个角再次这样做。

这就是要点。现在，源代码(最后有​​一些解释)。

    List<Point> returned_rectangle = new ArrayList<>();
    List<StorableData> sorted_abscissa_aligned_points = this.preTreatment();

    Point current_point_not_delete, neighbour_cupple_of_current_point, absc, ord, other_point;
    for(StorableData current_store_data : sorted_abscissa_aligned_points) { // Diagonal's points

        current_point_not_delete = (Point) current_store_data;

        for (StorableData neighbour_storable_data_of_current_cupple : sorted_abscissa_aligned_points) { // Diagonal's points
        if(neighbour_storable_data_of_current_cupple == null) {
        continue;
        }

        neighbour_cupple_of_current_point = (Point) neighbour_storable_data_of_current_cupple;

        if(Math.abs(neighbour_cupple_of_current_point.getNumber(0) - current_point_not_delete.getNumber(0)) <= PRECISION_DIAGONAL
        || Math.abs(neighbour_cupple_of_current_point.getNumber(1) - current_point_not_delete.getNumber(1)) <= PRECISION_DIAGONAL) {
          continue;
        }


        absc = null;
        ord = null;

        for(StorableData other_point_storable_data : sorted_abscissa_aligned_points) { // Abs and ord rectangle's points
            other_point = (Point) other_point_storable_data;
            if(other_point == null) {
            continue;
            }

            if(Math.abs(other_point.getNumber(0) - current_point_not_delete.getNumber(0)) <= PRECISION
            && Math.abs(other_point.getNumber(1) - neighbour_cupple_of_current_point.getNumber(1)) <= PRECISION) {

                absc = other_point;

            } else if(Math.abs(other_point.getNumber(0) - neighbour_cupple_of_current_point.getNumber(0)) <= PRECISION
            && Math.abs(other_point.getNumber(1) - current_point_not_delete.getNumber(1)) <= PRECISION) {

                ord = other_point;

            }

            if(absc != null && ord != null) {
                break;
            }
        }

        if(absc != null && ord != null) {
                returned_rectangle.add(absc);
                returned_rectangle.add(current_point_not_delete);
                returned_rectangle.add(ord);
                returned_rectangle.add(neighbour_cupple_of_current_point);
                return returned_rectangle;
        }

        }

        sorted_abscissa_aligned_points.set(sorted_abscissa_aligned_points.indexOf(current_point_not_delete), null);
    }

真正的检测是在第三个for中完成的(从代码顶部算起)。 getNumber(0) 表示“读取 X 坐标”，getNumber(1) Y 一个，2 : Z。

---

我的问题

如您所知，如果在 X 和 Y 坐标中绘制矩形但不考虑深度 (Z)，则我的算法运行良好。

我如何扩展它？也许我将不得不使用 cos 和其他类似的东西。

Answer 1

先说一点。我相信您当前的算法仅适用于检测 2D 空间中的矩形，其中边平行/垂直于 x/y 轴。换句话说，将不会检测到已“旋转”(对角线，如您所描述的)的矩形。

我建议使用一种适用于 2D 和 3D 的不同算法。这是代码的粗略草稿:

List<Point> points;
// Assign list ...

// Iterate for first point...
for (int i = 0; i < points.size() - 3; ++i) {
    // Second point...
    for (int j = i + 1; j < points.size() - 2; ++j) {
        // Third point...
        for (int k = j + 1; k < points.size() - 1; ++k) {
            // Get the three points
            Point p1 = points.get(i);
            Point p2 = points.get(j);
            Point p3 = points.get(k);
            // Array for corner point and its two adjacent points if there's a 90° angle
            Point[] angle;
            if ((angle = checkRightAngle(p1, p2, p3)) != null) {
                // Calculate which point would form a rectangle with the given 3 points
                Point remainingCorner = translate(angle[0], angle[1], angle[2]);
                // Check the remaining points and see if any match the remaining corver
                for (int l = k + 1; l < points.size(); ++l) {
                    Point p4 = points.get(l);
                    if (distanceWithinPrecision(remainingCorner, p4) {
                        // p1, p2, p3 and p4 form a rectangle; use the result as needed
                    }
                }
            }
        }
    }
}

Point[] checkRightAngle(Point p1, Point p2, Point p3) {
    // For each of the three points, check if it forms a 90° angle with the other two points
    // If such a point is found, return an array with the corner point in the first index 
    // and the remaining to points in the other indexes
    // If no such point is found, return null
}

Point translate(Point source, Point other1, Point other2) {
    // Calculate the vectors from source to other1 and source to other2
    // Create a new Point that has the coordinates resulting from translating source by
    // the two vectors and return it
}

让我们看一下这个。这三个循环将导致遍历三个点减去最后一个(稍后将检查)的每个组合，而不重复一组点。检查组合中的三个点是否形成直角。

方法 checkRightAngle 应该检查给定的 3 个点中的每一个是否与其他两个点形成 90° 角。如果没有 90° 角，它只返回 null。如果有这样一个 90° 角，它应该返回一个 Point 数组，第一个元素是位于 90° 角的 Point ，第二个和第三个元素是其他两个 Points (它们的顺序无关紧要)。要计算 3 个维度中两条相交线段之间的角度，您应该可以轻松地在网上找到公式。请注意，这里有机会进行一些优化。假设您已经检查了 2 个点的角度作为角，但都不是 90°，那么您可以检查它们的总和是否为 90°；在三角形中，所有三个角的角之和为 180°，因此如果两个角的角和为 90°，则根据定义，剩下的角必须为 90°。所以你最多需要检查两个角度。

如果这三个点形成直角，则使用方法translate 来确定形成矩形的剩余点应该是什么。这样做的方法是取 90° 角的角点(角度 [0] 数组元素)，使用剩余的两个点(角度 1 和角度 [2])创建两个 vector 并创建一个新点是这两个 vector 对角点的平移。

这是通过观察得出的，如果你取任何一点，两个 vector 分别平移产生的两个点和两个 vector 平移产生的一个点，这些点将形成一个平行四边形。

在我们的例子中，两个 vector 已经确定为垂直(90° 角)，因此结果将是一个矩形。

实际上，您需要做的就是在角点和其中一个非角点之间建立 vector ，并将其添加到另一个角点。所以在上面的例子中，假设p1的坐标是(x1,y1,z2)，p2的坐标是(x2,y2,z2)，p3的坐标是(x3,y3,z3)。从 p1 到 p2 的 vector 是 (x2 - x1, y2 - y1, z2 - z1)。您将其添加到 (x3, y3, z3)，得到 (x2 - x1 + x3, y2 - y1 + y3, z2 - z1 + z3)。这会产生您剩余的矩形点。

最后要做的是计算这个所需的第 4 个点与输入中任何剩余点之间的距离是否低于某个阈值，以得出这个剩余点与其他三个点形成一个矩形的结论。