LinuxQuestions.org
Go Job Hunting at the LQ Job Marketplace
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 11-29-2012, 02:58 AM   #1
mitchell7man
Member
 
Registered: Jan 2007
Location: Provo, UT
Distribution: OSX - Fedora
Posts: 458

Rep: Reputation: 31
C Programming - Continuous Line on LCD


Okay, so I'm working on an "Etch a Sketch Program"
this is my line drawing algorithm at present
Code:
void DrawLine(int xi, int xf,int yi, int yf)
{
	// Line Algorithm, Here we Go!
	// Declare local variables.
	int dx	= 	0;
	int dy	= 	0;
	int i	=	1;
	int steps = 0;
	int xinc = 	0;
	int yinc = 	0;
	int	x	=	0;
	int y	=	0;
	// Set x values.
	// Assign Dx and Dy;
	dx	=	xf-xi;
	dy	=	yf-yi;
	if (abs(dx) > abs(dy))
	{
		steps=abs(dx);
		xinc	=	dx/steps;
		yinc	=	dy/steps;
		x		=	xi;
		y		=	yi;
		lcd_point(x,y,1);
	}
	else
	{
		steps=abs(dy);
		xinc	=	dx/steps;
		yinc	=	dy/steps;
		x		=	xi;
		y		=	yi;
		lcd_point(x,y,1);
	}
	for	(i=steps;0 <= i;i--)
        {
		else
		{
		x=(x+xinc);
		y=(y+yinc);
		lcd_point(x,y,1);
		}
	}
}
The issue is that when my slope is extreme I get really jumpy lines, that is when my inputs (in this case from pretentiometers, using averaging to smooth out.

I understand that I need to change the algorithm so that I either add or subtract 1 from x or y on steps/dy interals, but how exactly do I set up those for statements?

Something along the lines of
Code:
m = dy/dx;
if(m>1 || m<1)
{
if (abs(dx)>abs(dy))
{
y++;
if(?????)
x++;
lcd_point(x,y,1);
}
else
{
x++;
if(?????)
y++
lcd_point(x,y,1);
}
}
so ????? should be finding whether one of steps/dy intervals has been met.

I hope this is making sense to those of you familiar with doing this, any explanation and help is deeply appreciated, this is my first project to this depth in c.
 
Old 11-29-2012, 05:42 AM   #2
millgates
Member
 
Registered: Feb 2009
Location: 192.168.x.x
Distribution: Slackware
Posts: 651

Rep: Reputation: 269Reputation: 269Reputation: 269
I'm not sure I understand completely, but what about something like this?

Code:
void DrawLine(int xi, int xf,int yi, int yf)
{
	int dr[2];
	dr[0] = xf -xi;
	dr[1] = yf-yi;

	int start[2];
	start[0]=xi;
	start[1]=yi;

	int lng = ( abs(dr[1]) > abs(dr[0]) );
	int shrt = 1 - lng;

	float tan=(float)dr[shrt]/dr[lng];

	for (int i = 0; i <= dr[lng]; i++) {
		int pos[2];
		pos[lng] = start[lng] + i;
		pos[shrt] = start[shrt] + (int)(i * tan + 0.5);
		lcd_point(pos[0], pos[1], 1);
	}
}
assuming you use the C99 standard. Could be a bit more compact if you passed the arguments as two vectors.

Last edited by millgates; 11-29-2012 at 05:43 AM.
 
Old 11-29-2012, 07:55 AM   #3
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,107

Rep: Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114Reputation: 1114
There was a very efficient solution to this problem in common use decades ago when computers were slow and primitive enough that you couldn't waste any resources. (I independently invented this in 1971, but I probably wasn't the first and later inventors of it apparently didn't copy me). Lots of methods are possible now that computers are more powerful, but the old way still works well:

(All integers):

You use an accumulator A and constants SR and FR that are the abs of the X and Y rates of change, swapped if necessary so that SR is the slower rate and FR is the faster rate. You also need three binary flags for whether X, Y were increasing/decreasing and which was faster.

Initialize A to FR/2.

At each step, you will unconditionally bump the position of the faster changing of X or Y and you will subtract SR from A.
If the result of that subtraction is negative, you will also bump the position of the slower changing of X or Y and you will add FR to A.

Note, you don't need to special case equal rates. Whichever you accidentally choose as "faster" when the rates are actually equal, the method will still work.

For elegant C code, avoiding many if statements, I suggest having an array of two counters instead of having scalar x and y counters. Also use an array of two directions 1 or -1 instead of bools for direction. So to bump the faster, instead of something like
Code:
if (y_faster)
   if (y_forward)
     y++;
   else
     y--;
else
   if (x_forward)
     x++;
   else
     x--;
you only need
Code:
counter[y_faster] += direction[y_faster];
To bump the slower counter you only need
Code:
counter[1-y_faster] += direction[1-y_faster];
I assume you can figure out the setup code that computes:
FR the larger of the two abs rates
SR the smaller of the two abs rates
counter[0] the initial x position
counter[1] the initial y position
direction[0] 1 if x is increasing, otherwise -1
direction[1] 1 if y is increasing, otherwise -1
y_faster 1 if y is changing faster than x, otherwise 0.

For line segment drawing, the integer "rate" is the total delta for that coordinate: segment end minus segment beginning.

Last edited by johnsfine; 11-29-2012 at 09:03 AM.
 
Old 11-29-2012, 09:10 AM   #4
theNbomr
LQ 5k Club
 
Registered: Aug 2005
Distribution: OpenSuse, Fedora, Redhat, Debian
Posts: 5,395
Blog Entries: 2

Rep: Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903
I'm guessing that johnsfine is referring to Bresenham's Line Algorithm.
--- rod.
 
Old 12-07-2012, 09:30 PM   #5
mitchell7man
Member
 
Registered: Jan 2007
Location: Provo, UT
Distribution: OSX - Fedora
Posts: 458

Original Poster
Rep: Reputation: 31
Thanks for the help guys! I was able to get it done I did end up using a form of Bresenham's Line Algorithm!
 
  


Reply

Tags
algorithm, continous, cprogramming, line, potentiometer


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Comparing Line Per Line In Shell Programming mblames Programming 3 01-18-2007 11:37 PM
Laptop LCD Screen 1 solid vertical red line comprookie2000 Linux - Hardware 1 03-23-2006 12:48 PM


All times are GMT -5. The time now is 09:59 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration