Help with intersecting line segments

BlitzMax Forums/BlitzMax Programming/Help with intersecting line segments

GfK(Posted 2009) [#1]
I'm using this code (which is mine): http://www.blitzbasic.com/codearcs/codearcs.php?code=2597

I wrote it a while ago but only just got around to needing it. My original code was for intersecting infinite lines - not segments.

Some chap has kindly added code for detecting segments and I've modified this slightly as below:
Function Between:Byte(X:Double, B:Double, T:Double)
	If T >= B
		If X >= B And X <= T
			Return 1
		EndIf
	Else
		If X >= T And X <= B
			Return 1
		EndIf
	EndIf
	Return 0
End Function

The implementation of this is given on the code archive page but I'm not convinced that this is correct. It often works - but not always. My line intersection code seems to work fine, but its when I started wanting to check line segments (which have a defined start and end point) that I started having problems. For instance, its telling me occasionally that two line segments don't intersect when they clearly do, yet if I move them a few pixels closer together, it works.

Ideas?


Jasu(Posted 2009) [#2]
So far I haven't needed a function that would determine intersect point for line segments, since I have next two functions.
Function Intersect:Int(x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float, x4:Float, y4:Float)
	Return (Sgn((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) <> Sgn((x2 - x1) * (y4 - y1) - (x4 - x1) * (y2 - y1))) And (Sgn((x4 - x3) * (y1 - y3) - (x1 - x3) * (y4 - y3)) <> Sgn((x4 - x3) * (y2 - y3) - (x2 - x3) * (y4 - y3)))
End Function

The above returns True if line segments intersect at some point. It's very fast.
If the line segments intersect, then I use intersect calculation for infinite lines.
Infinity doesn't matter since I know the segments intersect.
Function IntersectPoint (x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float, x4:Float, y4:Float, RX:Float Var, RY:Float Var)
	'Function returns the X,Y position of the two intersecting lines.
	'The lines are infinite, is line1 goes through x1,y1,x2,y2 and line2 goes through x3,y3,x4,y4.
	'For finite lines you must check if the lines truly intersect with the function Intersect% before you use this.
	
	Local dx1:Float = x2 - x1
	Local dx2:Float = x4 - x3
	'Local dx3:Float = x1 - x3
	
	Local dy1:Float = y2 - y1
	'Local dy2:Float = y1 - y3
	Local dy3:Float = y4 - y3
	
	Local R:Float = dx1 * dy3 - dy1 * dx2
	
	If R <> 0 Then
		R = ((y1 - y3) * dx2 - (x1 - x3) * dy3) / R
		rx = x1 + R * dx1
		ry = y1 + R * dy1
	Else
		If ((dx1 * (y3 - y1) - (x3 - x1) * dy1) = 0) Then
			rx = x3
			ry = y3
		Else
			rx = x4
			ry = y4
		EndIf
	EndIf
	
End Function


They should work with double precision too, I think.
I haven't had any problems with these.

I know this isn't exactly what you wanted (you want to reinvent the wheel, which is pretty much what I like to do too), but maybe these will give you ideas.


GfK(Posted 2009) [#3]
Thanks, that seems to work perfectly. I have lots of testing to do that's going to keep me here for a few hours yet, but thanks for your help (and put that in the code archives!)


Kurator(Posted 2009) [#4]
Hera an more OO-stylish solution :)

SuperStrict

Local point1:TPoint2D = TPoint2D.Create(1, 1)
Local point2:TPoint2D = TPoint2D.Create(10, 10)

Local point3:TPoint2D = TPoint2D.Create(10, 1)
Local point4:TPoint2D = TPoint2D.Create(1, 10)

Local line1:TLine2D = TLine2D.Create(point1, point2)
Local line2:TLine2D = TLine2D.Create(point3, point4)
Local line3:TLine2D = TLine2D.Create(point1, point3)
Local line4:TLine2D = TLine2D.Create(point2, point4)

If line1.intersects(line2) Then Print "Yes, intersects"
If line2.intersects(line1) Then Print "Yes, intersects"
If Not line3.intersects(line4) Then Print "No, does not intersect"
If Not line4.intersects(line3) Then Print "No, does not intersect"

Local point10:TPoint2D = TPoint2D.Create(4,4)
Local point11:TPoint2D = TPoint2D.Create(6,6)
Local line100:TLine2D  = TLine2D.Create(point10, point11)

Local point20:TPoint2D = TPoint2D.Create(4,6)
Local point21:TPoint2D = TPoint2D.Create(6,4)
Local line200:TLine2D  = TLine2D.Create(point20, point21)

Print "Intersects X:"+line100.getIntersectionPoint2D(line200).GetX()
Print "Intersects Y:"+line100.getIntersectionPoint2D(line200).GetY()

Type TPoint2D
	Field _x:Double
	Field _y:Double
	
	Function Create:TPoint2d(x:Double, y:Double)
		Local point:TPoint2D = New TPoint2D
		point._x = x
		point._y = y
		Return point
	EndFunction
	
	Method getX:Double()
		Return _x
	EndMethod
	
	Method getY:Double()
		Return _y
	EndMethod
EndType

Type TLine2D
	Field _p1:TPoint2D
	Field _p2:TPoint2D
	
	Function Create:TLine2D(p1:TPoint2D, p2:TPoint2D)
		Local line:TLine2D = New TLine2D
		line._p1 = p1
		line._p2 = p2
		Return line
	EndFunction
	
	Method getP1:TPoint2D()
		Return _p1
	EndMethod

	Method getP2:TPoint2D()
		Return _p2
	EndMethod	

	Method intersects:Int(other:TLine2D)
		Return (Sgn((Self.getP2().getX() - Self.getP1().getX()) * (other.getP1().getY() - Self.getP1().getY()) - (other.getP1().getX() - Self.getP1().getX()) * (Self.getP2().getY() - Self.getP1().getY())) <> Sgn((Self.getP2().getX() - Self.getP1().getX()) * (other.getP2().getY() - Self.getP1().getY()) - (other.getP2().getX() - Self.getP1().getX()) * (Self.getP2().getY() - Self.getP1().getY()))) And (Sgn((other.getP2().getX() - other.getP1().getX()) * (Self.getP1().getY() - other.getP1().getY()) - (Self.getP1().getX() - other.getP1().getX()) * (other.getP2().getY() - other.getP1().getY())) <> Sgn((other.getP2().getX() - other.getP1().getX()) * (Self.getP2().getY() - other.getP1().getY()) - (Self.getP2().getX() - other.getP1().getX()) * (other.getP2().getY() - other.getP1().getY())))
	EndMethod
	
	Method getIntersectionPoint2D:TPoint2D(other:TLine2D)
		Local result:TPoint2D = Null
		
		If Self.intersects(other)
		
			Local dx1:Double = Self.getP2().getX() - Self.getP1().getX()
			Local dx2:Double = Other.getP2().getX() - Other.getP1().getX()
			
			Local dy1:Double = Self.getP2().getY() - Self.getP1().getY()
			Local dy2:Double = Other.getP2().getY() - Other.getP1().getY()
			
			Local R:Double = dx1 * dy2 - dy1 * dx2
			
			If R <> 0 Then
				R = ((Self.getP1().getY() - Other.getP1().getY()) * dx2 - (Self.getP1().getX() - Other.getP1().getX()) * dy2) / R
				result = TPoint2D.Create(Self.getP1().getX() + R * dx1, Self.getP1().getY() + R * dy1)
			Else
				If ((dx1 * (Other.getP1().getY() - Self.getP1().getY()) - (Other.getP1().getX() - Self.getP1().getX()) * dy1) = 0) Then
					result = TPoint2D.Create(Other.getP1().getX(), Other.getP1().getY())
				Else
					result = TPoint2D.Create(Other.getP2().getX(), Other.getP2().getY())
				EndIf
			EndIf		
		EndIf
		Return result
	EndMethod

EndType



Jesse(Posted 2009) [#5]
Hera an more OO-stylish solution :)

All of those method calls. yak! I don't think I would sacrifice performance over that. Overkill, me thinks :)


Jasu(Posted 2010) [#6]
The OO version is like going to an expensive restaurant and asking for ketchup for your meal. Ketchup may be great, but demolishes the original idea.

These kind of math functions are supposed to work lightning fast, so you can call them millions of times per second without having to worry about performance. I hate it when schools teach us OOP is some sort of a god. As far as I see it, it's a good aid, but bad host. Thinking about all the s**t we put CPU to do with all this excess OOP crap. It makes me so mad.

Enough ranting, nothing personal, sorry...


Czar Flavius(Posted 2010) [#7]
Rant.Stop()


Jasu(Posted 2010) [#8]
:D
Better just set it as null and wait for garbage collector to lock this thread.


matibee(Posted 2010) [#9]
Sorry for the bump, this just made me laugh out loud..

Thinking about all the s**t we put CPU to do with all this excess OOP crap. It makes me so mad.


Rant.Stop()


If that was intentional Czar, you're a genius :D


RemiD(Posted 2016) [#10]
@Jasu>>thanks for sharing !