Math problem with lines, offset
Community Forums/General Help/Math problem with lines, offset
| ||
 Today, let's play "Help Ian with math!" :) See the attached picture? I am trying to figure this out. If I have points X1,Y1 and X2,Y2, I know how to find midpoint X3,X4. What I'm trying to figure out is how to find a point a certain number of pixels away from the center at a right angle. For instance, the point at X4,Y4? I'm not sure what you would even call such an equation to look it up. Anybody know how to do this or what this is called? I know this may seem simple, but I have looked and looked at equations and I'm not seeing it. Please help if you can! |
| ||
| This would be screen pixel locations, from 0,0 in the upper left to 1919,1079 or whatever in the bottom right. |
| ||
| The gradient of the 90 degree line would be the negative inverse of the line between points 1 and 2. So, if y = mx + c then your new line's gradient would be -1/m. Writing this on phone so difficult to type but that should get you started. |
| ||
| I'll give it a shot with my kindergarten math. EDIT: Corrected. If you know [X1,Y1], [X2,Y2] and [X3,Y3], do this: ANGLE% = 90 ;Degrees. LENGTH% = 50 ;Pixels. LineAngle# = Atan2( Y2 - Y1, X2 - X1) X4# = X3 + Cos(ANGLE + LineAngle)*LENGTH Y4# = Y3 + Sin(ANGLE + LineAngle)*LENGTHX3 and Y3 represent the origin from where you're trying to advance towards some point that is 'LENGTH' away and 'ANGLE' around line [x1,y1,x2,y2]. Last edited 2011 |
| ||
| It's not the best way to do this but, it works. |
| ||
| Thanks everybody! That's exactly what I was trying to figure out. I took the code example and played around with it a bit. I think it could be a bit faster with look-up tables for the math maybe? Anyway, here's what I've got now, thanks for the code above :) Graphics 800,600,32,2 SetBuffer BackBuffer() SeedRnd MilliSecs() Repeat ProfTimeA=MilliSecs() Cls ;arbitrarily chosen points x1 = Rand (0,799) y1 = Rand (0,599) x2 = Rand (0, 799) y2 = Rand (0, 599) ;draw the original line Line x1,y1, x2,y2 ;find the midpoint x3 = (x1+x2) Shr 1 y3 = (y1+y2) Shr 1 ;find the angle of the line from x1,y1 to x2,y2 and subtract 90 degrees or 270 If Rand (0,1)=1 Then angle# = ATan2( Float(y2-y1), Float(x2-x1) ) - 270.0 Else angle# = ATan2( Float(y2-y1), Float(x2-x1) ) - 90.0 EndIf ;use random pixeldist in this example pixelDist = Rand (10,250) ;was 100 ;calc the new point pixels distance at 90 degrees from mid-point x4 = Cos(angle) * pixelDist + x3 y4 = Sin(angle) * pixelDist + y3 ;show the mid-point Color 255,0,0 Oval x3-2, y3-2, 5, 5, True ;draw a line from mid-point x3,y3 to x4,y4 Color 255,255,0 Line x3,y3, x4,y4 ;show the point 100 pixels away from mid-point x3,y3 Color 255,0,0 Oval x4-2, y4-2, 5, 5, True ProfTimeB=MilliSecs()-ProfTimeA Text 20,20, "Time to execute=" + ProfTimeB Flip WaitMouse() Until KeyHit(1) ;ESC exit End Comment out this line to see it at speed: WaitMouse() |
| ||
| I will have to do this a bunch of times each frame, as I need to take the new point and make lines to it, cut those lines in half and repeat. Eventually, this will be a lightning effect in the game. Thanks again for the help! |
| ||
You can do it with just a single Sqrt call, avoiding the trig functions.Graphics 800,600,0 dist#=50 While Not (KeyHit(KEY_ESCAPE) Or AppTerminate()) 'use scroll wheel or arrow keys to change length of secondary line dist:+(MouseZ()-omz+KeyDown(KEY_UP)-KeyDown(KEY_DOWN))*2 omz=MouseZ() 'get mouse co-ordinates mx = MouseX() my = MouseY() 'click to change position of start of line If MouseHit(1) x1#=mx y1#=my EndIf 'end of line is at mouse cursor x2#=mx y2#=my 'get the difference between the start and end points dx# = x2-x1 dy# = y2-y1 '(x3,y3) is at the midpoint of the line x3#=x1+dx/2 y3#=y1+dy/2 'we want to find a vector of length 1 which is at right angles to the first line If dy=0 'then perpendicular line must be vertical dy=-Sgn(dx) 'whether the perpendicular goes up or down depends on the horizontal direction of the first line dx=0 Else 'gradient of perpendicular is -1/gradient of line 'gradient of line is dy/dx, so perpendicular is -dx/dy m# = -dx/dy*Sgn(dy) '*Sgn(dy) is to make sure perpendicular is always on the same side of the line 'the vector (1,m) is at right angles to the first line, but doesn't have length 1 'find the length of the vector d#=Sqr(1*1+m*m) 'divide by the vector's length to get a vector in the right direction and with length 1 dx=1/d*Sgn(dy) dy=m/d EndIf 'find (x4,y4) by moving <dist> units away from (x3,y3) in the direction of the perpendicular vector we just worked out x4#=x3+dist*dx y4#=y3+dist*dy 'draw both lines DrawLine x1,y1,x2,y2 DrawLine x3,y3,x4,y4 Flip Cls Wend |
| ||
| Everybody is making too much of this, at least the perpendicular vector part. We know (dx,dy) = (x2-x1,y2-y1) is a vector in the direction from point1 to point2. How do we get a vector perpendicular to this? Just use (-dy,dx) or (dy,-dx). Either of these is perpendicular to (dx,dy) because the dot product is 0. Then proceed as before. Divide by Sqr( dx*dx + dy*dy ) to get a vector of length one. Multiply by the desired distance from the original line and add this to the midpoint. Last edited 2011 |
| ||
| *ahem* |
| ||
| I was referring only to the calculation of a normal vector (nx,ny). Here's Warpy's example with a simplified normal calculation, and drawing both perpendicular lines. Graphics 800,600,0 dist#=50 While Not (KeyHit(KEY_ESCAPE) Or AppTerminate()) 'use scroll wheel or arrow keys to change length of secondary line dist:+(MouseZ()-omz+KeyDown(KEY_UP)-KeyDown(KEY_DOWN))*2 omz=MouseZ() 'get mouse co-ordinates mx = MouseX() my = MouseY() 'click to change position of start of line If MouseHit(1) x1#=mx y1#=my EndIf 'end of line is at mouse cursor x2#=mx y2#=my 'get the difference between the start and end points dx# = x2-x1 dy# = y2-y1 '(x3,y3) is at the midpoint of the line x3#=x1+dx/2 y3#=y1+dy/2 'we want to find a vector of length dist which is at right angles to the first line d# = dist / Sqr( dx*dx + dy*dy ) nx# = -dy * d ny# = dx * d SetColor 255,255,255 ; DrawLine x1,y1,x2,y2 ' original line drawn in White ' now add or subtract this from the midpoint SetColor 255,0,0 ; DrawLine x3,y3,x3+nx,y3+ny ' use (-dy, dx) and draw in Red SetColor 0,0,255 ; DrawLine x3,y3,x3-nx,y3-ny ' use ( dy,-dx) and draw in Blue Flip Cls Wend Last edited 2011 |
| ||
| Had to download the Blitzmax demo to try that real quick. I'm using Blitz3D :) This is essentially what I am trying to do. I will then take the resulting offset line endpoint and the original line endpoints and subdivide them again. And then take those points/lines and subdivide and so forth. This will happen a bunch of times (32 or less) in each frame to achieve the desired effect. So at this point I am wondering what method is the fastest to do these calculations. In my post above, the first trip through the loop is slower than the subsequent ones (4 milliseconds). Why is that? I have a very fast computer, which gets 1 millisecond for subsequent frames. Are slower computers going to have trouble doing this real time? The last post before this seems quite fast too. Is it faster than the Sin/Cos version? |
| ||
| I would have thought the trig version would be acceptably fast. But the point is that we don't need it in this case. We are rotating by +90 or -90 degrees. So the only possible values for Cos and Sin are 0, +1 and -1. For example, the expression dx*Cos(90) - dy*Sin(90) simplifies to dx*0 - dy*1, which is just -dy. Last edited 2011 |
| ||
| Here's the fastest solution that I can come up with. Notice that the square root has been eliminated. The funny thing is that on Win7 64 bit Home Premium with 2.9 GHz AMD dual processors it runs about 70% of what it runs on an old Dell laptop with a 2.6GHz single core. |
| ||
| The funny thing is that on Win7 64 bit Home Premium with 2.9 GHz AMD dual processors it runs about 70% of what it runs on an old Dell laptop with a 2.6GHz single core. Is it funny? I'd have expected 64 bit registers to be slower when doing 32 bit calculations. |
| ||
| It gets even funnier. I did those timings in debug mode :\ They're now about twice as fast as the laptop. Last edited 2011 |
| ||
| ...Notice that the square root has been eliminated. Notice also that it doesn't work. Try an easily checked example, a horizontal line. The two new points should then be (midX, +distance) and (midX, -distance). I was still curious about the speed of the test. It ran in 90 ms on my Window7 Intel i7 PC. Eliminating all calculations except the calls to Rand() left this: ;Time only the math used to determine mid-point and new point For i = 1 To iterations x1 = Rand (0,799) y1 = Rand (0,599) x2 = Rand (0, 799) y2 = Rand (0, 599) distance% = Rand(10,250) side% = Rand(0,1) NextThat still gave a time of 66 ms, which means nearly three fourths of all the time used originally was simply generating random numbers. That's a common failing with speed tests posted on these forums. Last edited 2011 |
| ||
| What I'm trying to figure out is how to find a point a certain number of pixels away from the center at a right angle. For instance, the point at X4,Y4? It works for what was described. |
| ||
| It gets the distance wrong because length should be Sqr(length). |
| ||
| That's a common failing with speed tests posted on these forums. You want a bit of silliness that will really blow your minds? This: distSqrd% = distance*distance ...will unpredictably either slow down or speed up the following code, depending on the complexity of the function and several specifics of the user's hardware (i.e. redoing the multiplication will on most machines be faster than accessing the local variable from RAM). The first rule of optimisation has always been: Don't. The second rule of optimisation is definitely: Don't attempt to do it in Blitz3D, because you'll probably make things worse (and if you're even trying, you probably have no idea what you're doing). Write time-critical code in C, after profiling to find out where the problems are. [/wild tangent] Last edited 2011 |
| ||
Andy's code works fine for what I am trying to do. It also seems to be more than fast enough. Here's doing 1000 iterations:Graphics 800,600,32,2 SetBuffer BackBuffer() SeedRnd MilliSecs() iterations% = 1000 ;iterations ;iterations% = 1 ;check to make sure it's doing what's intended Global floaty1# Global floaty2# Global floaty3# Repeat ;time the whole process Cls ProfTimeA=MilliSecs() For i = 1 To iterations ;arbitrarily chosen points x1 = Rand (0,799) y1 = Rand (0,599) x2 = Rand (0, 799) y2 = Rand (0, 599) ;points will be known before routine so we can discount the random generating time Color 255,0,0 Line x1,y1, x2,y2 distance% = Rand(10,250) distSqrd% = distance*distance side% = Rand(0,1) dx# = (x2-x1) dy# = (y2-y1) length# = 1.0/((dx*dx+dy*dy)/distSqrd) ;left side = 0 --- right side <> 0 If side = 0 Then dy = -dy Else dx = -dx ;find the mid-point of x1,y1 - x2,y2 midX = (x1+x2) Shr 1 midY = (y1+y2) Shr 1 ;find the perpendicular and make it 'distance' pixels from mid-point newX = dy * length + midX newY = dx * length + midY Color 255,255,0 Line midX, midY, newX, newY Next ProfTimeB=MilliSecs()-ProfTimeA Color 255,255,255 Text 20,20, "Time to execute: " + ProfTimeB floaty2#=ProfTimeB floaty3#=iterations floaty1#=floaty2#/floaty3# Text 20,40,"Time per iteration= "+(floaty1#) Flip WaitMouse() Until KeyHit(1) End This includes using random numbers which I won't need as the numbers are known ahead of time (ship location, target location). It's also doing all the drawing and still very fast. Thanks for helping everybody! I come from the Atari 8bit days and sometimes I think I need to get things more optimized than they need to be :) |
| ||
| As Floyd pointed out, the distance from the midpoint is not the correct value. And as Yasha noted, I got a little carried away in trying to optimize the code. This is slightly slower, but gets the distance right. |
| ||
| Ah, I see now! That works more than fast enough for what I need it for :) |
   |