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 回答