1

我有一条由两点 p1 和 p2 组成的线段，以及由点 p3 和 p4 组成的第二条线段。我试图弄清楚它们是否相交，到目前为止，我还没有运气。到目前为止，这是我的代码：

public static double angle(Point p1, Point p2, Point p3) {
    double AB = length(p2, p1);
    double BC = length(p2, p3);
    double AC = length(p3, p1);
    return Math.acos((sqr(BC) + sqr(AB) - sqr(AC)) / (2 * BC * AB)) * (180 / Math.PI);
}

public static boolean doIntersect(Point p1, Point p2, Point p3, Point p4) {
    double a = angle(p4, p3, p2);
    double b = angle(p3, p2, p1);
    double c = 180 - b - a;

    System.out.println("a: " + a + ", b: " + b + ", c:" + c);

    if((length(p3, p2) * Math.sin(a)) / Math.sin(c) > length(p2, p1)) return false;
    if((length(p3, p2) * Math.sin(b)) / Math.sin(c) > length(p3, p4)) return false;
    return true;
}

public static double length(Point point1, Point point2) {
    return Math.sqrt(sqr(point1.x - point2.x) + sqr(point1.y - point2.y));
}

public static double sqr(double doub) {
    return Math.pow(doub, 2);
}

但这行不通。有时，角度“c”甚至是负数。

此外，Point 是一个自定义类，有两个参数：x 和 y。应该是不言自明的。

4

3 回答 3

0
于 2013-11-18T18:29:51.433 回答
0

我建议先提出一个数学解决方案，对其进行验证，然后尝试将其迁移到计算机程序中。

于 2013-11-18T16:09:48.643 回答
0

有两种解决方案，每种都有自己的优势：

1. 数学解

从两点 p1 和 p2，可以很容易地推导出y = m*x + b穿过这两个点的线的公式。使用由 (p1, p2) 和 (p3, p4) 定义的线的公式，通过均衡计算它们的交点也很容易。剩下要做的就是检查交点是否是两条线段的一部分，这是相当明显的。

2.算法解决方案

另一种方法是应用扫描线算法：按它们各自的 x 坐标对所有点进行排序。然后对于 x 顺序中的每个点，想象一条从一个点跳到另一个点的垂直线。

如果您在访问线段 A 的所有点之后到达线段 B 的第一个点，则没有交点。

否则，您的第一个点来自线段 A，而您的第二个点来自线段 B。因此，您的第三个和第四个点分别属于 A 和 B 或 B 和 A。将注意力集中在 y 坐标上，并自行解决该解决方案的最后一部分。;-)

编辑：或者更简单，询问维基百科在线段交点。

于 2013-11-18T18:01:33.170 回答