Connecting Lines

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|581\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> Concept/Design -> Connecting Lines
Mon, 21 Apr 2008, 08:37
Jayenkai	A while ago, I posted this.. Graphics 800,600,32,2 SetBuffer BackBuffer() Dim coord(4,2) For n=1 To 4 coord(n,1)=Rand(0,800) coord(n,2)=Rand(0,600) Next move=0 Repeat Cls For n=2 To 5 If KeyDown(n) Then move=n-1 Next If move>0 Then coord(move,1)=MouseX():coord(move,2)=MouseY() If MouseDown(1) Then move=0 ;"Debug mode" is the 1, right at the end of this line! collision=LinesCollide(coord(1,1),coord(1,2),coord(2,1),coord(2,2),coord(3,1),coord(3,2),coord(4,1),coord(4,2),1) Color 255,255,255 If collision=0 Then Text 0,0,"No Collision" Color 255,0,0 If collision=1 Then Text 0,0,"Wow! That worked!! A Collision!" Color 125,125,0 If collision=1 Then Color 255,255,0 Line coord(1,1),coord(1,2),coord(2,1),coord(2,2) Color 0,125,125 If collision=1 Then Color 0,255,255 Line coord(3,1),coord(3,2),coord(4,1),coord(4,2) Flip Until KeyDown(1) Function LinesCollide(x1s#,y1s#,x1e,y1e#,x2s#,y2s#,x2e#,y2e#,debugme=0) out=0 ;Step 1. Find "triangle of collision" away from Point 1 of Line 2. TempDX#=x2s-x1s TempDY#=y2s-y1s TOCAng1#=(ATan2(0-TempDX,TempDY)+360) Mod 360 If debugme=1 Color 125,0,0 Line x2s,y2s,x2s+Sin(TOCAng1)1000,y2s-Cos(TOCAng1)1000 EndIf TempDX#=x2s-x1e TempDY#=y2s-y1e TOCAng2#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If debugme=1 Color 125,0,0 Line x2s,y2s,x2s+Sin(TOCAng2)1000,y2s-Cos(TOCAng2)1000 EndIf ;Fix angle messups. A1Fix=0 ;This bit took pissing AGES! ;Lots of trial and error stuff! If Abs(TOCAng1-TOCAng2)<=180 And TOCAng1>TOCAng2 Then TOCTemp#=TOCAng2:TOCAng2=TOCAng1:TOCAng1=TOCTemp If Abs(TOCAng1-TOCAng2)>180 And TOCAng1<TOCAng2 Then TOCAng2=TOCAng2-360:A1Fix=1 If Abs(TOCAng1-TOCAng2)>180 And TOCAng1>TOCAng2 Then TOCTemp#=TOCAng2:TOCAng2=TOCAng1-360:TOCAng1=TOCTemp:A1Fix=2 If Abs(TOCAng1-TOCAng2)<=180 And TOCAng1>TOCAng2 Then TOCTemp#=TOCAng2:TOCAng2=TOCAng1:TOCAng1=TOCTemp ;Step 2. Find "triangle of collision" away from Point 2 of Line 2. TempDX#=x2e-x1s TempDY#=y2e-y1s TOCAng3#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If debugme=1 Color 0,0,125 Line x2e,y2e,x2e+Sin(TOCAng3)1000,y2e-Cos(TOCAng3)1000 EndIf TempDX#=x2e-x1e TempDY#=y2e-y1e TOCAng4#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If debugme=1 Color 0,0,125 Line x2e,y2e,x2e+Sin(TOCAng4)1000,y2e-Cos(TOCAng4)1000 EndIf ;Fix angle messups. A2Fix=0 If Abs(TOCAng3-TOCAng4)<=180 And TOCAng3>TOCAng4 Then TOCTemp#=TOCAng4:TOCAng4=TOCAng3:TOCAng3=TOCTemp If Abs(TOCAng3-TOCAng4)>180 And TOCAng3<TOCAng4 Then TOCAng4=TOCAng4-360:A2Fix=1 If Abs(TOCAng3-TOCAng4)>180 And TOCAng3>TOCAng4 Then TOCTemp#=TOCAng4:TOCAng4=TOCAng3-360:TOCAng3=TOCTemp:A2Fix=2 If Abs(TOCAng3-TOCAng4)<=180 And TOCAng3>TOCAng4 Then TOCTemp#=TOCAng4:TOCAng4=TOCAng3:TOCAng3=TOCTemp ;Step 3. Find the angles of Line 2.. That is from point 1 to 2 and then point 2 to 1 TempDX#=x2s-x2e TempDY#=y2s-y2e Angle1to2#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If A1Fix>0 And Angle1to2>180 Then Angle1to2=Angle1to2-360 ;This bit, too, was trial and error! TempDX#=x2e-x2s TempDY#=y2e-y2s Angle2to1#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If A2Fix>0 And Angle2to1>180 Then Angle2to1=Angle2to1-360 ;Step 4. If Angle from Point 1 to 2 is between TOC1+2, and Angle from 2 to 1 is between TOC3+4, then we've collided. (Hopefully!) If Angle1to2=>TOCAng1 And Angle1to2<=TOCAng2 And Angle2to1=>TOCAng3 And Angle2to1<=TOCAng4 Then out=1 Return out End Function --v Today when I came to use it, I realised that it was missing an important feature. The function will check two lines, and if they connect it'll tell you so. (hit 1 to move point one with the mouse, 2 to move point 2, and on up to point 4....) What I'd like it to do, though, is find out WHERE they connect.. So, a puzzle.. What are the co-ords at point #5. You can either have 2 globals "MeetX,MeetY" and get the function to place them in there, or have 2 versions of the function to each get X and Y results.. ... The easier one would be the 2 globals method.. I'm sure there's a really really easy way to do this, but my brains slightly melted, today, so I can't seem to figure it out. -=-=- ''Load, Next List!''
Mon, 21 Apr 2008, 10:52
shroom_monk	The first thing that comes into my head when I think of this is an equation. If you know the equation for the two lines, you could use an equation to figure it out. Well, at least on paper - I'm not sure about how you'd program it! But say you knew that Line 1 was y=2x+5 and Line 2 was y=x+10, you could say: 2x+5=x+10 2x=x+5 x=5 Then, since x=5, y=(2*5)+5, so y=15. Thus, the co-ords of Point 5 are (5,15). -=-=- A mushroom a day keeps the doctor away... Keep It Simple, Shroom!
Mon, 21 Apr 2008, 10:56
Jayenkai	Hmm.. That kinda makes sense. I'm not sure how I can get that to work in Blitz, but.. ... I'll have a think whilst at work! -=-=- ''Load, Next List!''
Mon, 21 Apr 2008, 11:25
Forklift_Fred	I think your answer could be HERE but again, you'd need to translate it to code... I tried but seem to have failed: If collision=1 Then colx=((((coord(1,1)coord(2,2))-(coord(1,2)coord(1,2)))(coord(3,1)-coord(4,1)))-((coord(1,1)coord(2,1))((coord(3,1)coord(4,2))-(coord(3,2)coord(4,1)))))/(((coord(1,1)-coord(2,1))(coord(3,2)-coord(4,2)))-((coord(1,2)-coord(2,2))(coord(3,1)-coord(4,1)))) coly=((((coord(1,1)coord(2,2))-(coord(1,2)coord(1,2)))(coord(3,2)-coord(4,2)))-((coord(1,2)coord(2,2))((coord(3,1)coord(4,2))-(coord(3,2)coord(4,1)))))/(((coord(1,1)-coord(2,1))(coord(3,2)-coord(4,2)))-((coord(1,2)-coord(2,2))(coord(3,1)-coord(4,1)))) Text 0,0,"Wow! That worked!! A Collision! At ("+colx+","+coly+")" End If --v (Replaces the If collision... "Wow! That worked" line) Probably got some brackets in the wrong place or referenced the wrong coordinates... I'll try again later \|edit\| Add this little snippet to show the line coordinates... Text 0,570,"Line 1 ("+coord(1,1)+","+coord(1,2)+") - ("+coord(2,1)+","+coord(2,2)+")" Text 0,585,"Line 2 ("+coord(3,1)+","+coord(3,2)+") - ("+coord(4,1)+","+coord(4,2)+")" --v \|edit\| -=-=- Come rain or shine...
Mon, 21 Apr 2008, 12:20
JL235	I just wrote this which should help to do some of what Shroom describes. Enjoy!
Mon, 21 Apr 2008, 12:32
Forklift_Fred	OK, I copied the X1...X4 as set out in the Wiki page and it works. A little inaccurate due to pixel resolution but it works: Graphics 640,480 x1#=10 y1#=50 x2#=150 y2#=100 x3#=50 y3#=20 x4#=60 y4#=100 Color 255,0,0 Line x1,y1,x2,y2 Color 0,255,0 Line x3,y3,x4,y4 colx#=( ( ( (x1y2) - (y1x2) ) * (x3-x4) ) - ( (x1-x2) * ( (x3y4) - (y3x4) ) ) ) / ( ( (x1-x2) * (y3-y4) ) - ( (y1-y2) * (x3-x4) ) ) coly#=( ( ( (x1y2) - (y1x2) ) * (y3-y4) ) - ( (y1-y2) * ( (x3y4) - (y3x4) ) ) ) / ( ( (x1-x2) * (y3-y4) ) - ( (y1-y2) * (x3-x4) ) ) Color 255,255,255 Oval colx-1,coly-1,3,3 Color 255,0,0 Text 0,435,"Line 1 ("+x1+","+y1+") - ("+x2+","+y2+")" Color 0,255,0 Text 0,450,"Line 2 ("+x3+","+y3+") - ("+x4+","+y4+")" Color 255,255,255 Text 0,465,"Intersect at ("+colx+","+coly+")" Flip WaitKey End --v So, substituting Jay's coord(x,y) array... If collision=1 Then colx#=( ( ( (coord(1,1)coord(2,2)) - (coord(1,2)coord(2,1)) ) * (coord(3,1)-coord(4,1)) ) - ( (coord(1,1)-coord(2,1)) * ( (coord(3,1)coord(4,2)) - (coord(3,2)coord(4,1)) ) ) ) / ( ( (coord(1,1)-coord(2,1)) * (coord(3,2)-coord(4,2)) ) - ( (coord(1,2)-coord(2,2)) * (coord(3,1)-coord(4,1)) ) ) coly#=( ( ( (coord(1,1)coord(2,2)) - (coord(1,2)coord(2,1)) ) * (coord(3,2)-coord(4,2)) ) - ( (coord(1,2)-coord(2,2)) * ( (coord(3,1)coord(4,2)) - (coord(3,2)coord(4,1)) ) ) ) / ( ( (coord(1,1)-coord(2,1)) * (coord(3,2)-coord(4,2)) ) - ( (coord(1,2)-coord(2,2)) * (coord(3,1)-coord(4,1)) ) ) Text 0,0,"Wow! That worked!! A Collision! At ("+colx+","+coly+")" End If --v So the full working example is thus: Graphics 800,600,32,2 SetBuffer BackBuffer() Dim coord(4,2) For n=1 To 4 coord(n,1)=Rand(0,800) coord(n,2)=Rand(0,600) Next Global colx# Global coly# move=0 Repeat Cls For n=2 To 5 If KeyDown(n) Then move=n-1 Next If move>0 Then coord(move,1)=MouseX():coord(move,2)=MouseY() If MouseDown(1) Then move=0 ;"Debug mode" is the 1, right at the end of this line! collision=LinesCollide(coord(1,1),coord(1,2),coord(2,1),coord(2,2),coord(3,1),coord(3,2),coord(4,1),coord(4,2),1) Color 255,255,255 Text 0,570,"Line 1 ("+coord(1,1)+","+coord(1,2)+") - ("+coord(2,1)+","+coord(2,2)+")" Text 0,585,"Line 2 ("+coord(3,1)+","+coord(3,2)+") - ("+coord(4,1)+","+coord(4,2)+")" If collision=0 Then Text 0,0,"No Collision" Color 255,0,0 If collision=1 Then colx#=( ( ( (coord(1,1)coord(2,2)) - (coord(1,2)coord(2,1)) ) * (coord(3,1)-coord(4,1)) ) - ( (coord(1,1)-coord(2,1)) * ( (coord(3,1)coord(4,2)) - (coord(3,2)coord(4,1)) ) ) ) / ( ( (coord(1,1)-coord(2,1)) * (coord(3,2)-coord(4,2)) ) - ( (coord(1,2)-coord(2,2)) * (coord(3,1)-coord(4,1)) ) ) coly#=( ( ( (coord(1,1)coord(2,2)) - (coord(1,2)coord(2,1)) ) * (coord(3,2)-coord(4,2)) ) - ( (coord(1,2)-coord(2,2)) * ( (coord(3,1)coord(4,2)) - (coord(3,2)coord(4,1)) ) ) ) / ( ( (coord(1,1)-coord(2,1)) * (coord(3,2)-coord(4,2)) ) - ( (coord(1,2)-coord(2,2)) * (coord(3,1)-coord(4,1)) ) ) Text 0,0,"Wow! That worked!! A Collision! At ("+colx+","+coly+")" End If Color 125,125,0 If collision=1 Then Color 255,255,0 Line coord(1,1),coord(1,2),coord(2,1),coord(2,2) Color 0,125,125 If collision=1 Then Color 0,255,255 Line coord(3,1),coord(3,2),coord(4,1),coord(4,2) Flip Until KeyDown(1) Function LinesCollide(x1s#,y1s#,x1e,y1e#,x2s#,y2s#,x2e#,y2e#,debugme=0) out=0 ;Step 1. Find "triangle of collision" away from Point 1 of Line 2. TempDX#=x2s-x1s TempDY#=y2s-y1s TOCAng1#=(ATan2(0-TempDX,TempDY)+360) Mod 360 If debugme=1 Color 125,0,0 Line x2s,y2s,x2s+Sin(TOCAng1)1000,y2s-Cos(TOCAng1)1000 EndIf TempDX#=x2s-x1e TempDY#=y2s-y1e TOCAng2#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If debugme=1 Color 125,0,0 Line x2s,y2s,x2s+Sin(TOCAng2)1000,y2s-Cos(TOCAng2)1000 EndIf ;Fix angle messups. A1Fix=0 ;This bit took pissing AGES! ;Lots of trial and error stuff! If Abs(TOCAng1-TOCAng2)<=180 And TOCAng1>TOCAng2 Then TOCTemp#=TOCAng2:TOCAng2=TOCAng1:TOCAng1=TOCTemp If Abs(TOCAng1-TOCAng2)>180 And TOCAng1<TOCAng2 Then TOCAng2=TOCAng2-360:A1Fix=1 If Abs(TOCAng1-TOCAng2)>180 And TOCAng1>TOCAng2 Then TOCTemp#=TOCAng2:TOCAng2=TOCAng1-360:TOCAng1=TOCTemp:A1Fix=2 If Abs(TOCAng1-TOCAng2)<=180 And TOCAng1>TOCAng2 Then TOCTemp#=TOCAng2:TOCAng2=TOCAng1:TOCAng1=TOCTemp ;Step 2. Find "triangle of collision" away from Point 2 of Line 2. TempDX#=x2e-x1s TempDY#=y2e-y1s TOCAng3#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If debugme=1 Color 0,0,125 Line x2e,y2e,x2e+Sin(TOCAng3)1000,y2e-Cos(TOCAng3)1000 EndIf TempDX#=x2e-x1e TempDY#=y2e-y1e TOCAng4#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If debugme=1 Color 0,0,125 Line x2e,y2e,x2e+Sin(TOCAng4)1000,y2e-Cos(TOCAng4)1000 EndIf ;Fix angle messups. A2Fix=0 If Abs(TOCAng3-TOCAng4)<=180 And TOCAng3>TOCAng4 Then TOCTemp#=TOCAng4:TOCAng4=TOCAng3:TOCAng3=TOCTemp If Abs(TOCAng3-TOCAng4)>180 And TOCAng3<TOCAng4 Then TOCAng4=TOCAng4-360:A2Fix=1 If Abs(TOCAng3-TOCAng4)>180 And TOCAng3>TOCAng4 Then TOCTemp#=TOCAng4:TOCAng4=TOCAng3-360:TOCAng3=TOCTemp:A2Fix=2 If Abs(TOCAng3-TOCAng4)<=180 And TOCAng3>TOCAng4 Then TOCTemp#=TOCAng4:TOCAng4=TOCAng3:TOCAng3=TOCTemp ;Step 3. Find the angles of Line 2.. That is from point 1 to 2 and then point 2 to 1 TempDX#=x2s-x2e TempDY#=y2s-y2e Angle1to2#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If A1Fix>0 And Angle1to2>180 Then Angle1to2=Angle1to2-360 ;This bit, too, was trial and error! TempDX#=x2e-x2s TempDY#=y2e-y2s Angle2to1#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If A2Fix>0 And Angle2to1>180 Then Angle2to1=Angle2to1-360 ;Step 4. If Angle from Point 1 to 2 is between TOC1+2, and Angle from 2 to 1 is between TOC3+4, then we've collided. (Hopefully!) If Angle1to2=>TOCAng1 And Angle1to2<=TOCAng2 And Angle2to1=>TOCAng3 And Angle2to1<=TOCAng4 Then out=1 Return out End Function --v (Having compared the code side by side, my original post failed because it was multiplying in one place where it should have been subtracting! - The middle of the top line in the Wiki equation) -=-=- Come rain or shine...
Mon, 21 Apr 2008, 12:43
Jayenkai	Wow! what a lot of maths! I'll assume that's right.. Can't check at work, no Blitz. Thanks guys! (Now to hope it'll keep up to speed!) -=-=- ''Load, Next List!''
Mon, 21 Apr 2008, 14:42
Jayenkai	Woot! Thanks Forklift, and both DD and Shroom, too. Tomorrow, more work on the super secret game that involves lines colliding!! -=-=- ''Load, Next List!''
Mon, 21 Apr 2008, 15:03
Forklift_Fred	It's Ghostbusters isn't it? Don't cross the streams! -=-=- Come rain or shine...
Mon, 21 Apr 2008, 21:12
Orion Pax	Wow!...What a reference Fred! Havent heard that in a long time....
Thu, 24 Apr 2008, 07:18
Andy_A	Here's a fast lines intersect function. AppTitle "Line Intersection Function by Andy_A" Graphics 800,600,32,2 SetBuffer BackBuffer() Global intersectX%, intersectY% While Not(KeyHit(1)) Cls x1 = Rand(0,799) : y1 = Rand(60,599) x2 = Rand(0,799) : y2 = Rand(60,599) Line(x1,y1, x2,y2) Text(250,5,"Line 1: "+x1+","+y1+" - "+x2+","+y2) x3 = Rand(0,799) : y3 = Rand(60,599) x4 = Rand(0,799) : y4 = Rand(60,599) Line(x3,y3, x4,y4) Text(500,5,"Line 2: "+x3+","+y3+" - "+x4+","+y4) result = linesIntersect(x1,y1,x2,y2,x3,y3,x4,y4) Text 0,0,"Result: "+result If result = True Text(10,20,"Intersection Coords") Text(10,40," X="+ Str(intersectX) +" , Y="+Str(intersectY)) Color 255,0,0 Oval intersectX-3, intersectY-3, 5, 5, True Color 255,255,255 Else Text(10,20,"No Intersection") End If Text(400,580,"Press [Space] for new lines - [ESC] to exit",True,False) Flip WaitKey() Wend End Function linesIntersect(x1%,y1%, x2%,y2%, x3%,y3%, x4%,y4%) denominator# = (y4-y3)(x2-x1)-(x4-x3)(y2-y1) numeratorA# = (x4-x3)(y1-y3)-(y4-y3)(x1-x3) numeratorB# = (x2-x1)(y1-y3)-(y2-y1)(x1-x3) If denominator = 0.0 Then Return False Else Ua# = numeratorA/denominator Ub# = numeratorB/denominator range1% = Ua >= 0.0 And Ua <= 1.0 range2% = Ub >= 0.0 And Ub <= 1.0 If range1 And range2 Then intersectX% = Floor(x1 + Ua(x2-x1)+.5) intersectY% = Floor(y1 + Ua(y2-y1)+.5) Return True Else Return False End If End If End Function --v