代码之家 › 专栏 › 技术社区 › animuson

有没有一种简单的方法来检测线段交点?

geometry php

2

animuson · 技术社区 · 16 年前

这比一开始看起来要复杂得多。我得到的是一个巨大的数组,它由更多的数组组成,这些数组包含点[以数组“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之外,这个应该属于什么标签。如果您有任何想法,请随时重新标记。

2 回复 | 直到 16 年前

1

2

Community Mohan Dere 6 年前

以下是一个简单的方法,如果每个列表中的点数较少,则可以接受:

取数组中的前两条线段 check if they intersect .
继续到最后一点,并对另一个数组重复(我假设您所做的检查是针对每个子数组)。

这是 O(无) ^2. ) 哪里 N N 很小-太棒了,如果不是,请告诉我们。

O(无) ) 还不够好。。。

Sweep line algorithm for segment intersection O(n对数(n))

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

输出:

2

1

Jerry Coffin 16 年前

这相当容易。首先计算每条线的方程(斜率和Y截距)。坡度为(Y _1. _2. _1. -十 _2. ). Y截距是Y _1. _1.

一旦你为一对线计算了它们,你就计算出它们的位置线 _1. X+b公司 _1. =米 _2. _2. . 你可以通过隔离X来解这个方程。例如,给定两条线Y=3x+5和Y=.5x+2:

3x+5 = .5x+2 // subtract 5 from both sides
3x = .5x - 3 // subtract .5x fro both sides
2.5x = -3    // divide by 2.5
x = -3/2.5   // reduce term
x = -1.2

现在我们已经确定了两者的交点 ,但我们不知道这两段是否都延伸到足够远的地方来包含这一点。为此,我们需要检查X值是否在X之间和X _2. 对于两条线段。

许多