我怎样才能改进这个解决缺失坐标的算法？

Question

用户输入3个space分隔的坐标，可以在xy平面上组成一个矩形。该算法 return 必须是形成矩形的第 4 个点。

示例：“5 5”、“5 7”和“7 5”，换行分隔，应该 return “7 7”。

下面的算法适用于提供的测试用例，但我没有通过其他用例，而且我不明白为什么。谁能建议一种方法让我的算法包含所有可能的输入 - 假设提供的 3 个输入实际上形成了矩形的 3 个角？


import java.io.*;

public class cetvrta {

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String point1 = reader.readLine(); // 5 5
        String point2 = reader.readLine(); // 5 7
        String point3 = reader.readLine(); // 7 5
        String[] cord1 = point1.split(" "); // ["5","5"]
        String[] cord2 = point2.split(" "); // ["5", "7"]
        String[] cord3 = point3.split(" "); // ["7", "5"]
        int x4 = 0;
        int y4 = 0;
        int x1 = Integer.parseInt(cord1[0]); // 5
        int y1 = Integer.parseInt(cord1[1]); // 5
        int x2 = Integer.parseInt(cord2[0]);
        int y2 = Integer.parseInt(cord2[1]);
        int x3 = Integer.parseInt(cord3[0]);
        int y3 = Integer.parseInt(cord3[1]);

        if (y1 == y2) {
            if (x3 == x1) {
                x4 = x2;
                y4 = y3;
            }
            if (x3 == x2) {
                x4 = x1;
                y4 = y3;
            }
        }
        if (y3 == y2) {
            if (x2 == x3) {
                x4 = x1;
                y4 = y2;
            }
            if (x2 == x1) {
                x4 = x3;
                y4 = y2;
            }
        }
        if (y1 == y3) {
            if (x2 == x1) {
                x4 = x3;
                y4 = y2;
            }
            if (x2 == x3) {
                x4 = x1;
                y4 = y2;
            }
        }
        System.out.println(x4 + " " + y4);
    }

}

Answer 1

这很奇怪，重新考虑一下：

if (y3 == y2) {
    if (x2 == x3) { // <---
        x4 = x1; // <---
        y4 = y2; // <---
    }
    if (x2 == x1) {
        x4 = x3;
        y4 = y2; // <---
    }
}

Answer 2

没有硬性规定“矩形的 2 个点的 x 坐标必须匹配，y 坐标也必须匹配”。请考虑下图以便更好地理解。

我们可以看到，虽然存在一个完美的矩形，但没有两个点具有相同的 x 和 y 坐标：

修复： 我建议您稍微更改算法以按以下方式进行。给定这三个点，找到不是角点的点（根据其他 2 个点不通过对角线的那个点）。从这一点开始，计算剩余点的斜率并假设第 4 个角为 (x,y)；画出2个基因座。满足slope1 * slope 2=-1。这 2 个位点一起解决将给出第 4 个点。

Answer 3

最好用基本的向量代数来解决这个问题：

计算三个已知点之间的向量
定义给定的三个中的哪一个点是直角（90°）的顶点——如果有的话这可以利用两个垂直向量的标量积为 0 的事实来完成：v1.x * v2.x + v1.y * v2.0 == 0
通过将从该顶点出射到其他两个已知点的两个向量添加到直角顶点来找到第四个点。

示例实现可能如下所示：

// auxiliary classes
class Point {
    int x, y;
    
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    Point add(Vector v) {
        return new Point(this.x + v.x, this.y + v.y);
    }
    
    @Override
    public String toString() {
        return String.format("(%d, %d)", x, y);
    }
}

class Vector {
    int x, y;
    
    Vector(int x, int y) {
        this.x = x;
        this.y = y;
    }

    Vector(Point p1, Point p2) {
        this(p2.x - p1.x, p2.y - p1.y);
    }
    
    static boolean isRightAngle(Vector v1, Vector v2) {
        return 0 == (v1.x * v2.x + v1.y * v2.y);
    }
    
    Vector add(Vector v) {
        return new Vector(this.x + v.x, this.y + v.y);
    }
}

求直角顶点的方法：

static int rightAngleVertexIndex(Point ... p) {
    assert p.length == 3;
    Vector v01 = new Vector(p[0], p[1]);
    Vector v12 = new Vector(p[1], p[2]);
    Vector v20 = new Vector(p[2], p[0]);
    
    if (Vector.isRightAngle(v01, v12)) {
        return 1;
    } else if (Vector.isRightAngle(v12, v20)) {
        return 2;
    } else if (Vector.isRightAngle(v20, v01)) {
        return 0;
    } else {
        return -1;
    }
}

寻找矩形第4个点的方法（return null如果没有矩形是可能的）：

static Point findFourthVertex(Point ... points) {
    assert points.length == 3;

    final int[][] otherVertices = {
        {1, 2},
        {0, 2},
        {0, 1},
    };

    Point result = null;    
    int rightAngleIx = rightAngleVertexIndex(points);
    if (rightAngleIx != -1) {
        Point rightAngle = points[rightAngleIx];
        Point p1 = points[otherVertices[rightAngleIx][0]];
        Point p2 = points[otherVertices[rightAngleIx][1]];
        
        result = rightAngle.add(new Vector(rightAngle, p1).add(new Vector(rightAngle, p2)));
        System.out.println("The fourth vertex of the rectangle: " + result);
    } else {
        System.out.println("No right angle found between any of the points " + Arrays.toString(points));
    }
    return result;
}

测试：

findFourthVertex(new Point(1, 1), new Point(5, 1), new Point(1, 4));
findFourthVertex(new Point(-1, -1), new Point(5, 0), new Point(6, 5));

输出：

The fourth vertex of the rectangle: (5, 4)
No right angle found between any of the points [(-1, -1), (5, 0), (6, 5)]

我怎样才能改进这个解决缺失坐标的算法？

How can I improve this algorithm that solves for a missing coordinate?

java

plot

split

if-statement

coordinates