我有一个由两个点 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。 应该相当不言自明。
我建议先提出一个数学解决方案，验证它，然后尝试将其迁移到计算机程序。
有两种解决方案，每种解决方案都有自己的优势：
1. 数学解
从 p1 和 p2 两个点，可以很容易地推导出与这两点相交的线的公式y = m*x + b。使用由 (p1， p2( 和 (p3， p4( 定义的线的公式，再次很容易通过均衡来计算它们的交集。剩下要做的就是检查交点是否是两条线段的一部分，这是相当明显的。
2. 算法解决方案
另一种方法是应用扫描线算法：按各自的 x 坐标对所有点进行排序。然后，对于 x 顺序中的每个点，想象一条从一个点跳到另一个点的垂直线。
如果在访问线段 A 的所有点后到达线段 B 的第一个点，则没有交点。
否则，你的第一点来自线段A，第二点来自线段B.因此，你的第三点和第四点分别属于A和B或B和A。将注意力集中在 y 坐标上，并自行解决此解决方案的最后一部分。;-)
编辑：或者更简单，询问维基百科的线段交叉点。
对于角度计算，与其使用复杂的方法，将 x 和 y 差异的平方相加，然后取和的平方根，然后对该值进行平方，然后使用 acos，可以使用 atan2 根据 x 和 y 差异计算适当象限的角度。 这比acos方法更快，问题更少。
但是，根本不需要计算任何角度。 相反，如果重叠不可行，请首先测试。 也就是说，如果((x₁≤x₃≤x₂ || x₁≤x₄≤x₂ || x₃≤x₁≤x₄ || x₃≤x₂≤x₄) && (y≤y₃≤y₂ || y₁≤y₄≤y₂ || y₃≤y₁≤y₄ || y₃≤y₂≤y₄))为假，则返回No。 (设 p₁，p₂ 是一个段的端点，p₃，p₄ 是另一个段的端点。
如果情况并非不可行，则可以通过查看三角形 p₁、p₂、p₃ 和 p₁，p₂，p₄ 的面积符号是否不同来测试是否发生交集。 p₁，p₂，p₃ 的面积为 ±(x₁·y₂-x₂·y₁ + x₃·(y₂-y₁( + y₃·(x₂-x₁((/2，并且 1/2 的因子可以忽略，因为它不会影响符号。 也就是说，对于可行的情况，您可以计算t = x₁·y₂-x₂·y₁ u = t + x₃·(y₂-y₁) + y₃·(x₂-x₁) v = t + x₄·(y₂-y₁) + y₄·(x₂-x₁)如果u·v ≤ 0，则返回Yes，否则No。 使用此类方法的要点是避免检查垂直或水平线、平行线或重合线等出现的所有特殊情况。 如果预计会发生退化行，则报告Yes如果u·v < 0，或No如果u·v > 0，否则测试一行是否在另一行上具有端点。