ASCII Diagonal Lines Troubleshoot

[Überdevel]

I need to draw a diagonal line between two points in the screen, with a variable X and Y distance between both points.

For example:

Code: Select all

P1
   *
      *
         *
            *
               P2

P's are the points to trace the diagonal lines.
That is not a problem.

For such easy example, reducing the X and Y coordinates for the next step of the diagonal line is enough:

X = X + 1
Y = Y + 1

But the problem appears when X <> Y.

When X > Y, if using the formulae there up, the Y reaches faster the Point2 'Y' coordinate, so it will not decrease/increase more, meanwhile the 'X' will still be modified until reach the Point2 'X' coordinate. This results in something like this:

Code: Select all

P1
   *
      *
         *
            ************P2

In this example, the horizontal distance between P1 and P2 is larger than the Vertical Distance, so the line traced is diagonal until the Vertical Distance reaches P2 'Y' coordinate.

I think the example is quite visual on what I want to mean.

So, I need an algorithm to allow me to trace such diagonal lines without the side effect described before. I don't mind the ASCII line to look perfect diagonal, just to have an algorithm that results on the most perfect numeric approximation.

I was trying to apply the Pythagorean Theorem, but I couldn't reach a real functionality by using the Theorem, other than acquiring the real distance between P1 and P2.

Thanks in advance.

[vdecampo]

The best way I know to do this is to either do an integer count of x coords from x1 to x2 and increment y1 (single) by (y2-y1)/(x2-x1), or the reverse using the y coords. I am not at a computer where I can code an example but I will when I get a chance.

-Vince

[rolliebollocks]

The distance formula is what you are looking for, a variation on the Pythagorean Theorem...

d = SQR( (x2-x1)^2 + (y2-y1)^2 )

Set either the x's or the y's to be incremented at 1... and then the other variable will be incremented at the ratio... as in the slope formula... As Vince said... The problem is that if you happen to run into a slope which is 0 or there is NO SLOPE... It isn't going to draw squat.

Code: Select all

sub Projectile.Fire ( shooter as observer ptr, angle as coord_type )
    
    this.switch.counter = 0
    this.switch.isOn = TRUE
    
    this.p.x = shooter->p.x 'Set proj's pos = to the shooter
    this.p.y = shooter->p.y
    
    this.d.x = angle.x - this.p.x 'set the distances/direction
    this.d.y = angle.y - this.p.y
    
    if this.d.x + this.d.y = 0 then this.d.x = velocity
    
    m = 1 / sqr( this.d.x^2 + this.d.y^2)
    
    this.d.x *= m
    this.d.y *= m
    
    this.v.x = this.d.x * velocity
    this.v.y = this.d.y * velocity
    
end sub

That code snip will fire at mouse coordinates p.x, p.y from coordinates angle.x, angle.y making a straight line between them... This will work in the event that there is NO SLOPE or the slope = 0...

Peace,

rb

*EDIT*

In ASCII you'll need to use perfect right triangles of the (3/4/5) variety or else it won't (necessarily) incremement properly.

Let's say you have (0,0), (3,5) ... You will increment at 3 steps over/5 Down or 1: .6 ... Ascii coordinates can only be integers ... So you can use DRAW STRING instead of PRINT ...

Since you can't increment a character .6, none of this will work...

[rolliebollocks]

This draws the diagonal properly for 3:4:5's ...

Code: Select all

Dim As Integer x1,y1,x2,y2

x2=30:y2=50

dim as integer loop1 = Abs(x1-y1)
Dim As Integer loop2 = Abs(y1-y2)

for i as integer = x1 to loop1 step 3
For ii As Integer = y1 To loop2 step 4
    Locate i, ii: ?"X"
Next
next
Sleep

[counting_pine]

The Pythagorean algorithm isn't really any help when drawing lines because there's no use in knowing the diagonal length of the line. You just iterate along the x or y axis - whichever's longer - and work out the corresponding coordinate of the other value.

Here's a basic algorithm for line drawing. It isn't tested, and I haven't bothered with the code for y longer than x, but it's easy to write based on what's there:

Code: Select all

sub drawline(byval x1 as integer, byval y1 as integer, byval x2 as integer, byval y2 as integer)

 dim as integer swapxy = 0
 if abs(y2-y1) > abs(x2-x1) then '' make sure the x length is longest
     swap x1, y1
     swap x2, y2
     swapxy = not 0
 end if

 if x2 < x1 then swap x1, x2: swap y1, y2 '' make sure x increases horizontally

 dim as integer x
 dim as single y = y1
 dim as single dy = (y2-y1) / (x2-x1+1)

 for x = x1 to x2
  if swapxy then locate x, cint(y), 0 else locate cint(y), x, 0
  print "X";
  y += dy
 next x

end sub

do
    dim as integer x, y: do: sleep 100: loop while getmouse(x,y)
    cls
    drawline(40, 12, x, y)
loop until len(inkey)

You should know that from an efficiency point of view the definitive algorithm, which is entirely done in integer math, is Bresenham's line algorithm:
http://en.wikipedia.org/wiki/Bresenham_algorithm

EDIT: Code tested, stupidities fixed, plus steep line support (longer in y than x), plus a running example.

But anyway, see Voltage's code below for a Bresenham example.

[Voltage]

This is a Bresenham line drawing routine.

Code: Select all

ScreenRes 800,600,32

Declare Sub dline(x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer,c As UInteger)

Dim As Integer x1,y1,x2,y2

Randomize Timer

Do
	x1=Rnd*800
	x2=Rnd*800
	y1=Rnd*600
	y2=Rnd*600
	dline x1,y1,x2,y2,RGB(255,255,255)

	circle (x1,y1),3,RGB(255,0,0)
	circle (x2,y2),3,RGB(0,255,0)
	'sleep
	dline x2,y2,x1,y1,RGB(255,0,255)
Loop Until InKey=Chr(27)

Sub dline(x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer, c As UInteger)
	Dim As Integer dx,dy,ys,x,y,a
	
	dx=x2-x1

	'always left to right
	If dx<0 Then
		swap x1,x2
		swap y1,y2
		dx=-dx
	EndIf
	
	dy=y2-y1
	ys=1
	If dy<0 Then
		ys=-1
	EndIf

	dy=Abs(dy)
	
	If dy>dx Then
		a=dy/2
		For y1=y1 To y2 Step ys
			PSet (x1,y1),c
			a=a+dx
			If a>dy Then
				a=a-dy
				x1=x1+1
			EndIf
		Next y1
	Else
		a=dx/2
		For x1=x1 To x2 
			PSet (x1,y1),c
			a=a+dy
			If a>dx Then
				a=a-dx
				y1=y1+ys
			EndIf
		Next y1
	EndIf
End Sub

[dodicat]

Hi
Would this do the job?

Code: Select all

sub drawpoints(x1 as integer,y1 as integer,x2 as integer,y2 as integer,N as integer)
    N=N-1
    if x2=x1 then x2=x1+1
    if x2<x1 then swap x2,x1:swap y2,y1
    dim steps as single
    dim as single yval=y1,diffx
     diffx=abs(x2-x1)/(N)
    dim as single main_ratio=abs(y2-y1)/abs(x2-x1)
    steps=sgn(x2-x1)*diffx
    dim as integer count
    for s as single=x1 to x2 step steps
        count=count+1
        draw string(s,yval),"x"
        yval=y1+sgn(y2-y1)*count*steps*(main_ratio)
        next s
    end sub
    '********  EXAMPLE *************
    'PLEASE NOTE the fifth parameter (N) is the required number of points
    screenres 700,700,32
    'Draw a check grid
for n as integer=0 to 700 step 100
    line(0,n)-(700,n),rgb(50,50,50)
    line(n,0)-(n,700),rgb(50,50,50)
next
'checkgrid done
    drawpoints(100,100,450,650,15)
    sleep

[Überdevel]

Thanks you all for your tips.

I will try when arrive home :-)

[dodicat]

@ Counting Pine
I thought a single character only was required. Voltages code shows a mass of lines, yours, multiple X's. I thought Uberdevel just wants a single line of characters.
Do you Uberdevel?

Code: Select all

Sub drawpoints(x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer,N As Integer)
    N=N-1
    If x2=x1 Then x2=x1+1
    If x2<x1 Then Swap x2,x1:Swap y2,y1
    Dim steps As Single
    Dim As Single yval=y1,diffx
     diffx=Abs(x2-x1)/(N)
    Dim As Single main_ratio=Abs(y2-y1)/Abs(x2-x1)
    steps=Sgn(x2-x1)*diffx
    Dim As Integer count
    For s As Single=x1 To x2 Step steps
        count=count+1
        Draw String(s,yval),"x"
        yval=y1+Sgn(y2-y1)*count*steps*(main_ratio)
        Next s
    End Sub
    '********  EXAMPLE *************
    'PLEASE NOTE the fifth parameter (N) is the required number of points
    screenres 700,700,32
Do
    screenlock
    Dim As Integer x, y
    getmouse(x,y)
    Cls
    For n As Integer=0 To 700 Step 100  'The grid
    Line(0,n)-(700,n),rgb(50,50,50)
    Line(n,0)-(n,700),rgb(50,50,50)
Next
draw string(250,20),"Mouse":draw string(310,20),str(x)+",":draw string(350,20),str(y)
    drawpoints(100,100,x,y,15)
    screenunlock
Loop Until Len(Inkey)
    'drawpoints(100,100,450,650,15)
    'Sleep