查找与 Ax+By+C=0 形式的给定直线垂直的直线的算法

Question

如果所有直线的形式都是 Ax+By+C=0，有没有办法找到与给定直线垂直的直线？

我想出了一个需要二次运行时间的解决方案。有没有更好的方法？

这是我的代码：

public class Perpendicular {
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n=in.nextInt();
    ArrayList<Line> list_of_lines=new ArrayList<Line>();
    for(long i=0;i<n;i++){
        long a=in.nextLong();
        long b=in.nextLong();
        long c=in.nextLong();
       list_of_lines.add(new Line(a,b,c));
    }
    long p[]=new long[n];
    Arrays.fill(p,0);
    for(int i=0;i<n;i++){
        for(int j=1;j<n;j++){
            if(list_of_lines.get(i).slope()*list_of_lines.get(j).slope()== -1){
                p[i]++;//num of perpendicular lines to i
                p[j]++;//num of perpendicular lines to j
            }
        }
    }
}

}

class Line{
public long a,b,c;
public Line(long a,long b,long c){
    this.a=a;
    this.b=b;
    this.c=c;
}
public double slope(){
    return a/b;
}

}

Answer 1

由方程 -Bx + Ay + D = 0 引导的任何直线都是垂直于给定线族 (Ax + By + C = 0) 的直线集。

你只需要检查并确保它们的斜率的乘积等于-1。

因此，具有-Bx + Ay + D = 0 性质的线族将满足此标准。

现在检查所有线族非常容易，比您预期的二次解容易得多。

编辑：-

你不需要运行你的循环以这种方式。只要确保当您检查了两条线之间的垂直性时，您就不会再次执行可交换检查。前任;您检查了 1 和 2 之间的垂直度，那么您不需要重复检查 2 和 1 之间的垂直度的工作。这应该通过 j = i+1; 改进第二个循环初始化来在您的代码中避免。
使用建议的编辑，您也不需要检查相同的线是否垂直，因为那是不可能的。因此，线 k 不应与自身一起进行垂直度检查。使用提示 1 本身可以轻松解决此问题。

Answer 2

将方程转换为 y = m*x + c 的形式，m 是斜率，c 是 y 轴截距。现在，垂直于这组线的所有线的斜率为 -1/m（垂直线的斜率积为 -1），这应该给出等式。

Answer 3

如果你有一条直线Ax + By + C = 0，那么垂线A1x + B1y + C1 = 0应该符合点积v * v1 = 0（*在这里是dot product）。所以(A, B) * (A1 * B1) = A1 * A + B1 * B = 0。其中一个解决方案是 A = -B1、B = A1.

所以你的线的形式是 Bx - Ay + C1 = 0，其中 C1 是任意一点。这意味着它是 O(1).

Answer 4

如果两条直线的斜率相乘为 -1，则两条直线垂直。（假设 none 其中 horizontal/vertical）

您可以根据 O(n log n) 的斜率对线进行分组。对于每对具有垂直斜率的组，其中的每对线都是一个答案，您可以对其进行迭代。 O(n lg n + num_of_answers)

因此算法为 O(n lg n + num_of_answers).

请注意，可能有 O(n^2) 个这样的对；但是如果你只需要找到这样的对的数量，它可以在 O(n lg n) 中找到。

查找与 Ax+By+C=0 形式的给定直线垂直的直线的算法

Algorithm to find lines perpendicular to a given line of the form Ax+By+C=0

algorithm

math

line