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”，该数组中没有其他点。数组中的最后一个点不会循环回到数组中的第一个点。此外，如果一条线段在另一条线段的交点处结束，则不应将其视为相交，它实际上需要与与其相交的线段相交。

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

附注我真的想不出除了 PHP 之外应该属于哪些标签。如果您想到任何，请随时重新标记。

Answer 1

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

取数组中的前两条线段和 check if they intersect .

如果不是，请对照前面的线段检查下一条线段

继续到最后一点并重复另一个数组(我假设您正在执行的此检查是针对每个子数组)。

这是 O(n2)，其中 n 是所有子数组中的点数 --- 如果 n 很小 - 很棒，如果不是，请告诉我们。
更新:如果 O(n2) 不够好......
Sweep line algorithm for segment intersection - 应该是 O(n log (n))
输入:平面中的一组线段。
输出:S 中各段之间的交点集。