php - 有没有一种简单的方法来检测线段相交？

Question

这比乍一看要复杂得多。我拥有的是一个巨大的数组，它由更多的数组组成，其中包含点[以数组“x，y”的形式]，如下所示:

Array (
    [0] => Array (
        [0] => "0,9",
        [1] => "0,0",
        [2] => "9,0",
        [3] => "9,9",
        [4] => "0,9"
        )
    [1] => Array (
        [0] => "1,5",
        [1] => "1,6",
        [2] => "3,6",
        [3] => "3,8",
        [4] => "4,8"
    )
    ... and so on ...
)

所以我需要做的是处理所有点并查看数组中是否有任何点，例如 $points[0][1] 到 $points[0][ 2]，与数组中可能存在的任何其他线段相交。所有线段按照它们在各自数组中的顺序连续。因此，在第一个数组中，“0,9”变为“0,0”，并且该数组中没有其他点。数组中的最后一个点不会循环回数组中的第一个点。另外，如果一条线段终止于另一条线段的交点，则不应将其视为交点，它实际上需要穿过与其相交的线段。

我正在考虑在处理这些片段时绘制它们。因此，就像遍历数组一样，在“虚拟”网格上绘制每个点，然后每个数组都会计算它是否与已经绘制的另一个线段相交，如果这有意义的话，但这似乎仍然需要花费一些时间while 计算数组中是否有很多线段。看起来我要做的是对于数组中的每个段，计算它是否与它之前的任何段相交(因为理论上它可以与它所在的同一数组中的一个段相交)。必须有一种更简单的方法来做到这一点，对吗？

附注除了 PHP 之外，我实在想不出这应该属于什么标签。如果您想到任何请随时重新标记它。

Answer 1

这是一个简单的方法，如果每个列表中的点数很少，则可以接受:

1. 取数组中的前两条线段和 check if they intersect .
2. 如果没有，请对照前一个线段检查下一个线段
3. 继续直到最后一点并对另一个数组重复(我假设您正在针对每个子数组执行此检查)。

这是O(n²)，其中n是所有子数组中的点数 --- 如果n 很小 - 很棒，如果不是，请告诉我们。

更新:如果O(n²)不够好...

Sweep line algorithm for segment intersection - 据说O(n log (n))

输入:平面中的一组线段。

输出: S 中各段之间的交点集合。