有没有简单的方法来检测线段交点？ [英] Is there an easy way to detect line segment intersections?

问题描述

这比起初看起来要复杂得多。我有一个巨大的数组，其中包含更多的数组，其中包含点[以数组x，y的形式），如下所示：

 <阵列（
 [0] =>阵列（
 [0] =>0,9，
 [1] =>0,0 ，
 [2] =>9,0，
 [3] =>9,9，
 [4] =>0,9
 
 [1] =>数组（
 [0] =>1,5，
 [1] =>1,6，
 [2] =>3,6，
 [3] =>3,8，
 [4] =>4,8
）
 ...等等... 
）
  

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

我是考虑在处理它们时绘制细分。因此，像遍历数组绘制每个点在虚拟网格上的每个点，然后每个数组之后将计算它是否与另一个已经绘制的段相交，如果这是有道理的，但似乎仍然可能需要同时计算阵列中是否有很多线段。看起来我正在做的是针对数组中的每个段，计算它是否与之前的任何段相交（因为理论上它可能与它所在的同一个数组中的段相交）。必须有一个更简单的方法来做到这一点，对吗？

我无法真正想到这个应该属于PHP以外的标签。如果您想到任何问题，请随时重新提交。

解决方案

这是一个简单的方法，如果点数在每个列表中很小：

1. 取数组中的前两个线段和检查它们是否相交。
   
2. 如果不是，根据以前的线段检查下一个线段。
   
3. 继续到最后一点并重申另一个数组（我假设您正在为每个子数组执行此检查）。

这是 O（n ² ） / em>是所有子阵列中的点数---如果 n 小 - 真棒，如果没有，请告诉我们。

更新：如果 O（n ² ）不够好...

扫描线交叉点算法 - 据说是O（n log（n））

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

$ b 输出： S.

This is a lot more complicated than it might seem at first. What I have is a giant array which consists of more arrays which contain points [in the form of an array "x,y"] like so:

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 ...
)

So what I need to do is process through all the points and see if any point in an array, say $points[0][1] to $points[0][2], intersects with any other line segment that could exist in the array. All the line segments are consecutive following the order they are in within each of their respective arrays. So in the first array, "0,9" goes to "0,0" and no other point in that array. The last point in an array does not loop back around to the first point in an array. Also, it should not be considered an intersection if a line segment ends at the intersection of another line segment, it actually needs to cross the line segment it intersects.

I was thinking of plotting the segments as I processed them. So like run through the arrays plotting each point on a 'virtual' grid per say and then each array after that would calculate if it intersects another segment which is already plotted, if that makes any sense, but that still seems like it might take a while to calculate if there are a lot of line segments in the array. It seems like what I'd be doing is for each segment in an array, calculate if it intersects any segments previous to it (because theoretically it could intersect a segment in the same array it is in). There has got to be a simpler way to do this, right?

P.S. I couldn't really think of what tags this should fall under other than PHP. If you think of any please feel free to retag it.

解决方案

Here's a simple method which would be acceptable if the number of points in each list is small:

1. Take the first two line segments in your array and check if they intersect.
2. If not, check the next line segment against the previous line segments
3. Continue till the last point and reiterate for another array (I'm assuming this check you're doing is for each sub array).

This is O(n²) where n is the number of points in all your subarrays --- if n is small - awesome, if not, let us know.

Update: If O(n²) is not good enough ...

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

Input: A set of line segments in the plane.

Output: The set of intersection points among the segments in S.

这篇关于有没有简单的方法来检测线段交点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！