4

我一直在寻找一种合适的方法来确定两条线段(每组 2 组 x,y 坐标)是否相交。我见过很多(包括:你如何检测两条线段相交的位置?),但我见过的所有线段都有缺陷。主要是如果线平行但彼此重叠,它们不会检测到碰撞。

我也不需要返回交点,只需一个布尔值就可以了。

如果有人能指出我正确的方向,我将不胜感激,因为我显然不擅长几何。:(

4

2 回答 2

5

当然有数学上优雅的方法可以做到这一点,但如果你正在寻找一个使用基本代数的易于理解的算法,试试这个(这不是代码):

让我们通过端点定义两条线段:

l0 : { (x0, y0), (x1, y1) }
l1 : { (x2, y2), {x3, y3) }

首先,获得每条线的斜截形式。您可以查找 m、b 的公式或自己推导它们:

l0 : m0 * x + b0
l1 : m1 * x + b1

如果(m0 != m1)线不平行。要找到潜在的交点,请求解l0 = l1

x = (b1 - b0) / (m0 - m1)
y = m0 * x + b0

当且仅当(x, y)位于两个线段上时,线段才会相交。请注意,仅检查 x 坐标就足够了,因为我们已经(x, y)在两条线上建立了 x 坐标:

[编辑以反映来自@KenoguLabz 的出色输入]

(x0 <= x <= x1) AND (x2 <= x <= x3) AND (y0 <= y <= y1) AND (y2 <= y <= y3)

min(x0, x1) <= x <= max(x0, x1) AND min(x2, x3) <= x <= max(x2, x3)

如果这些线是平行的,并且您想知道它们是否重叠,请将一条线的端点替换为上面的 x (不过,您只需要对另一条线进行测试)

希望这可以帮助。祝你好运!

于 2012-10-19T00:45:38.257 回答
2

这是我最近写的一个小班。斜率和角度的 +/- 可能并不总是正确的(例如,当角度应该为 -90 时,它返回 90,但我使用的三角函数不受此影响)。您可能最感兴趣的函数是 GetIntersection,它对平行线返回 Nothing (null),否则返回 Point。这是代码:

Public Class LineData
    Public Property Point1() As Point
    Public Property Point2() As Point
    Public ReadOnly Property Slope() As Double
        Get
            # 0=Horizontal Line, NaN=Vertical Line
            Return If(Me.Point1.X = Me.Point2.X, Double.NaN, (Me.Point1.Y - Me.Point2.Y) / (Me.Point1.X - Me.Point2.X))
        End Get
    End Property
    Public ReadOnly Property YIntercept() As Double
        Get
            Return If(Double.IsNaN(Me.Slope), Double.NaN, Me.Point1.Y - Me.Slope * Me.Point1.X)
        End Get
    End Property
    Public ReadOnly Property Angle() As Double
        Get
            Return If(Double.IsNaN(Me.Slope), Math.PI / 2, Math.Atan(Me.Slope))
        End Get
    End Property

    Public Sub New(pt1 As Point, pt2 As Point)
        Me.Point1 = pt1
        Me.Point2 = pt2
    End Sub
    Public Sub New(x1 As Double, y1 As Double, x2 As Double, y2 As Double)
        Me.Point1 = New Point(x1, y1)
        Me.Point2 = New Point(x2, y2)
    End Sub
    Public Sub New(ln As Line)
        Me.New(ln.X1, ln.Y1, ln.X2, ln.Y2)
    End Sub

    Public Function GetParallel(spacing As Double) As LineData
        Return Me.GetParallel(spacing, ParallelPosition.Below)
    End Function

    Public Function GetParallel(spacing As Double, pos As ParallelPosition) As LineData
        If Me.Slope = 0 Then # Horizontal Line
            If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Left Then : Return If(Me.Point2.X > Me.Point1.X, New LineData(Me.Point1.X - spacing, Me.Point1.Y - spacing, Me.Point2.X + spacing, Me.Point2.Y - spacing), New LineData(Me.Point1.X + spacing, Me.Point1.Y - spacing, Me.Point2.X - spacing, Me.Point2.Y - spacing))
            Else : Return If(Me.Point2.X > Me.Point1.X, New LineData(Me.Point1.X - spacing, Me.Point1.Y + spacing, Me.Point2.X + spacing, Me.Point2.Y + spacing), New LineData(Me.Point1.X + spacing, Me.Point1.Y + spacing, Me.Point2.X - spacing, Me.Point2.Y + spacing))
            End If
        ElseIf Double.IsNaN(Me.Slope) Then # Vertical Line
            If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Left Then : Return If(Me.Point2.Y > Me.Point1.Y, New LineData(Me.Point1.X - spacing, Me.Point1.Y - spacing, Me.Point2.X - spacing, Me.Point2.Y + spacing), New LineData(Me.Point1.X - spacing, Me.Point1.Y + spacing, Me.Point2.X - spacing, Me.Point2.Y - spacing))
            Else : Return If(Me.Point2.Y > Me.Point1.Y, New LineData(Me.Point1.X + spacing, Me.Point1.Y - spacing, Me.Point2.X + spacing, Me.Point2.Y + spacing), New LineData(Me.Point1.X + spacing, Me.Point1.Y + spacing, Me.Point2.X + spacing, Me.Point2.Y - spacing))
            End If
        Else #Sloped Line
            Dim verticalshift As Double = Math.Abs(spacing / Math.Cos(-Me.Angle))
            Dim horizontalshift As Double = Math.Abs(spacing / Math.Sin(-Me.Angle))
            If Math.Sign(Me.Slope) = -1 Then
                If Me.Point2.X > Me.Point1.X Then
                    If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Left Then : Return New LineData(Me.Point1.X - horizontalshift, Me.Point1.Y, Me.Point2.X, Me.Point2.Y - verticalshift)
                    Else : Return New LineData(Me.Point1.X, Me.Point1.Y + verticalshift, Me.Point2.X + horizontalshift, Me.Point2.Y)
                    End If
                Else
                    If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Left Then : Return New LineData(Me.Point1.X, Me.Point1.Y - verticalshift, Me.Point2.X - horizontalshift, Me.Point2.Y)
                    Else : Return New LineData(Me.Point1.X + horizontalshift, Me.Point1.Y, Me.Point2.X, Me.Point2.Y + verticalshift)
                    End If
                End If
            Else
                If Me.Point2.X > Me.Point1.X Then
                    If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Right Then : Return New LineData(Me.Point1.X, Me.Point1.Y - verticalshift, Me.Point2.X + horizontalshift, Me.Point2.Y)
                    Else : Return New LineData(Me.Point1.X - horizontalshift, Me.Point1.Y, Me.Point2.X, Me.Point2.Y + verticalshift)
                    End If
                Else
                    If pos = ParallelPosition.Above OrElse pos = ParallelPosition.Right Then : Return New LineData(Me.Point1.X + horizontalshift, Me.Point1.Y, Me.Point2.X, Me.Point2.Y - verticalshift)
                    Else : Return New LineData(Me.Point1.X, Me.Point1.Y + verticalshift, Me.Point2.X - horizontalshift, Me.Point2.Y)
                    End If
                End If
            End If
        End If
    End Function

    Public Function CalculateX(y As Double) As Double
        If Me.Slope = 0 Then # Horizontal Line
            If y = Me.Point1.Y OrElse y = Me.Point2.Y Then Return 0 Else Return Double.NaN
        ElseIf Double.IsNaN(Me.Slope) Then # Vertical Line
            Return Me.Point1.X
        Else
            Return (y - Me.YIntercept) / Me.Slope
        End If
    End Function
    Public Function CalculateY(x As Double) As Double
        If Me.Slope = 0 Then # Horizontal Line
            Return Me.Point1.Y
        ElseIf Double.IsNaN(Me.Slope) Then # Vertical Line
            If x = Me.Point1.X OrElse x = Me.Point2.X Then Return 0 Else Return Double.NaN
        Else
            Return Me.Slope * x + Me.YIntercept
        End If
    End Function

    Public Function GetIntersection(ln As LineData) As Point
        If Me.Slope = ln.Slope OrElse (Double.IsNaN(Me.Slope) AndAlso Double.IsNaN(ln.Slope)) Then : Return Nothing
        Else
            If Double.IsNaN(Me.Slope) Then : Return New Point(Me.Point1.X, ln.CalculateY(Me.Point1.X))
            ElseIf Double.IsNaN(ln.Slope) Then : Return New Point(ln.Point1.X, Me.CalculateY(ln.Point1.X))
            ElseIf Me.Slope = 0 Then : Return New Point(ln.CalculateX(Me.Point1.Y), Me.Point1.Y)
            ElseIf ln.Slope = 0 Then : Return New Point(Me.CalculateX(ln.Point1.Y), ln.Point1.Y)
            Else
                Dim x As Double = (Me.YIntercept - ln.YIntercept) / (ln.Slope - Me.Slope)
                Return New Point(x, Me.CalculateY(x))
            End If
        End If
    End Function

    Public Function GetLine() As Line
        Dim templine As New Line
        templine.X1 = Me.Point1.X
        templine.Y1 = Me.Point1.Y
        templine.X2 = Me.Point2.X
        templine.Y2 = Me.Point2.Y
        Return templine
    End Function
End Class

Public Enum ParallelPosition As Byte
    Above
    Below
    Left
    Right
End Enum

希望这会有所帮助!

于 2013-02-26T18:51:22.857 回答