我一直在寻找一种合适的方法来确定两条线段(每组 2 组 x,y 坐标)是否相交。我见过很多(包括:你如何检测两条线段相交的位置?),但我见过的所有线段都有缺陷。主要是如果线平行但彼此重叠,它们不会检测到碰撞。
我也不需要返回交点,只需一个布尔值就可以了。
如果有人能指出我正确的方向,我将不胜感激,因为我显然不擅长几何。:(
我一直在寻找一种合适的方法来确定两条线段(每组 2 组 x,y 坐标)是否相交。我见过很多(包括:你如何检测两条线段相交的位置?),但我见过的所有线段都有缺陷。主要是如果线平行但彼此重叠,它们不会检测到碰撞。
我也不需要返回交点,只需一个布尔值就可以了。
如果有人能指出我正确的方向,我将不胜感激,因为我显然不擅长几何。:(
当然有数学上优雅的方法可以做到这一点,但如果你正在寻找一个使用基本代数的易于理解的算法,试试这个(这不是代码):
让我们通过端点定义两条线段:
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 (不过,您只需要对另一条线进行测试)
希望这可以帮助。祝你好运!
这是我最近写的一个小班。斜率和角度的 +/- 可能并不总是正确的(例如,当角度应该为 -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
希望这会有所帮助!