Solved

A small problem with a line algorithm

Posted on 2004-08-31
4
212 Views
Last Modified: 2010-04-16
Hi. Im sure this is a simple mathematical error, since I just jiggled around with a formula which worked for one type of line direction to get it to work with all line directions.

I know that this could be optimised with assembler code, but that is not my objective. Although some other optimisations for that pascal coding would be extremely welcome.

Anyway, enouth waffle...onto the problem :)

When I draw lines in the following ways this is what happens:

What is meant to happen                                        What acctually happens
===================================================
       :                                                                       :
       :                                                                       :                                                          
         :                                                                     :                                     (same for mirror images of these)
         :                                                                       :
           :                                                                     :
           :                                                                       :

===================================================

                :                                                                    :
                :                                                                    :                                                          
              :                                                                    :                               (same for mirror images of these)
              :                                                                    :
            :                                                                      :
            :                                                                    :

====================================================

   
Here is the code:


procedure drawline (x1,y1,x2,y2 : word);
var
   Count                    : word;
   Error                    : integer;
   dytimes2,dxtimes2        : Integer;
Begin
     if (x1 > x2) and (y1 < y2) then
     Begin
          dxtimes2 := (x1-x2) SHL 1;
          dytimes2 := (y2-y1) SHL 1;
          Error := x2-x1;
          if dxtimes2 > dytimes2 then
          Begin
               for count := x1 downto x2 do
               Begin
                    putpixel(count,y1,15);
                    Error := Error + dytimes2;
                    if Error > 0 then
                    Begin
                         Error := Error - dxtimes2;
                         y1 := y1 + 1;
                    End
               End;
           End
           Else
           Begin
                for count := y1 to y2 do                         {ONE PROBLEM IS IN THIS LOOP***********************************}
                Begin                                                   {***********************************************************}
                     putpixel(x1,count,15);                      {***********************************************************}
                     Error := Error + dxtimes2;              {***********************************************************}
                     if Error > 0 then                            {***********************************************************}
                     Begin                                           {***********************************************************}
                          Error := Error - dytimes2;        {***********************************************************}
                          x1 := x1 - 1;                           {***********************************************************}
                     End                                             {***********************************************************}
                End;                                                {***********************************************************}

           End;
     End
     Else
     Begin
     if (x1 > x2) and (y1 > y2) then
     Begin
          dxtimes2 := (x1-x2) SHL 1;
          dytimes2 := (y1-y2) SHL 1;
          Error := x2-x1;
          if dxtimes2 > dytimes2 then
          Begin
               for count := x1 downto x2 do
               Begin
                    putpixel(count,y1,15);
                    Error := Error + dytimes2;
                    if Error > 0 then
                    Begin
                         Error := Error - dxtimes2;
                         y1 := y1 - 1;
                    End
               End;
           End
           Else
           Begin
                for count := y1 downto y2 do                {ONE PROBLEM IS IN THIS LOOP***********************************}
                Begin                                                   {*********************************************************}
                     putpixel(x1,count,15);                      {*********************************************************}
                     Error := Error + dxtimes2;               {*********************************************************}
                     if Error > 0 then                               {*********************************************************}
                     Begin                                               {*********************************************************}
                          Error := Error - dytimes2;             {*********************************************************}
                          x1 := x1 - 1;                                 {*********************************************************}
                     End                                                {*********************************************************}
                End;                                                    {*********************************************************}

           End;
     End
     Else
     Begin
     if (x1 < x2) and (y1 < y2) then
     Begin
          dxtimes2 := (x2-x1) SHL 1;
          dytimes2 := (y2-y1) SHL 1;
          Error := x1-x2;
          if dxtimes2 > dytimes2 then
          Begin
               for count := x1 to x2 do
               Begin
                    putpixel(count,y1,15);
                    Error := Error + dytimes2;
                    if Error > 0 then
                    Begin
                         Error := Error - dxtimes2;
                         y1 := y1 + 1;
                    End
               End;
           End
           Else
           Begin
                for count := y1 to y2 do                      {ONE PROBLEM IS IN THIS LOOP***********************************}
                Begin                                                {*********************************************************}
                     putpixel(x1,count,15);                     {*********************************************************}
                     Error := Error + dxtimes2;             {*********************************************************}
                     if Error > 0 then                          {*********************************************************}
                     Begin                                         {*********************************************************}
                          Error := Error - dytimes2;        {*********************************************************}
                          x1 := x1 + 1;                         {*********************************************************}
                     End                                            {*********************************************************}
                End;                                                {*********************************************************}

           End;
     End
     Else
     Begin
     if (x1 < x2) and (y1 > y2) then
     Begin
          dxtimes2 := (x2-x1) SHL 1;
          dytimes2 := (y1-y2) SHL 1;
          Error := x1-x2;
          if dxtimes2 > dytimes2 then
          Begin
               for count := x1 to x2 do
               Begin
                    putpixel(count,y1,15);
                    Error := Error + dytimes2;
                    if Error > 0 then
                    Begin
                         Error := Error - dxtimes2;
                         y1 := y1 - 1;
                    End
               End;
           End
           Else
           Begin
                for count := y1 downto y2 do                       {ONE PROBLEM IS IN THIS LOOP***********************************}
                Begin                                                         {*********************************************************}
                     putpixel(x1,count,15);                             {*********************************************************}
                     Error := Error + dxtimes2;                        {*********************************************************}
                     if Error > 0 then                                     {*********************************************************}
                     Begin                                                     {*********************************************************}
                          Error := Error - dytimes2;                   {*********************************************************}
                          x1 := x1 + 1;                                      {*********************************************************}
                     End                                                        {*********************************************************}
                End;                                                           {*********************************************************}

           End;
     End;

     End;
     End;
     End;

End;


I know it is long :) But after a few if statments are executed there are just plotting to get on with. I have marked the problem parts.

Thanks for any help
0
Comment
Question by:GaryStanton414
  • 2
  • 2
4 Comments
 
LVL 10

Expert Comment

by:For-Soft
ID: 11947580
I believe, your program is more complicated than it schould be.

Instead of using the Error variable, you can calculate the point position using Real type. Then you can round the result. So there is no need for additional Error variable.
dx and dy could be calculated more precisely if declared as Real.
This will give you far more powerful control over point positions.
0
 

Author Comment

by:GaryStanton414
ID: 11950792
No. This is an efficient algorithm. Using real numbers for calcualtions is slow and inefficient. Then add rounding on top of that and it becomes more inefficient. This algorithm is designed for speed. Notice it also only uses addition and subtraction and a bit shift which are fast. There is no slow division or multiplicatio involved.

So I am looking for why this algorithm has the slight problem. Any optimisations which use the same technique are welcome but I am not looking for another method. Using the same method with for example less code but no loss in efficientcy is very welcome indeed.

Thanks
0
 
LVL 10

Accepted Solution

by:
For-Soft earned 50 total points
ID: 11951784
You are calculating Error variable only with X axis values.

You shold calculate Error depending on loop axis:


          dxtimes2 := (x1-x2) SHL 1;
          dytimes2 := (y2-y1) SHL 1;
          Error := x2-x1; {not proper place to calculate Error}
          if dxtimes2 > dytimes2 then
          Begin
               {Calculate Error here with X axis}
               for count := x1 downto x2 do
               Begin
                    putpixel(count,y1,15);
                    Error := Error + dytimes2;
                    if Error > 0 then
                    Begin
                         Error := Error - dxtimes2;
                         y1 := y1 + 1;
                    End
               End;
           End
           Else
           Begin
               {Calculate Error here with Y axis}
                for count := y1 to y2 do        
                Begin                                      
                     putpixel(x1,count,15);        
                     Error := Error + dxtimes2;    
                     if Error > 0 then            
                     Begin                        
                          Error := Error - dytimes2;
                          x1 := x1 - 1;
                     End  
                End;

           End;
     End


0
 

Author Comment

by:GaryStanton414
ID: 11953000
Brilliant Thanks
0

Featured Post

ScreenConnect 6.0 Free Trial

At ScreenConnect, partner feedback doesn't fall on deaf ears. We collected partner suggestions off of their virtual wish list and transformed them into one game-changing release: ScreenConnect 6.0. Explore all of the extras and enhancements for yourself!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Delphi & Indy 10 Whois over Web Proxy 3 1,198
Delphi - What Does "F" Symbolize? 2 475
USB Flash Drive Serial Numbers 9 3,975
access tor through embbed delphi browser 4 392
Adding Computers to AD groups through an SCCM Task Sequence
When you have clients or friends from around the world, it becomes a challenge to arrange a meeting or effectively manage your time. This is where Outlook's capability to show 2 time zones in one calendar comes in handy.
In a recent question (https://www.experts-exchange.com/questions/28997919/Pagination-in-Adobe-Acrobat.html) here at Experts Exchange, a member asked how to add page numbers to a PDF file using Adobe Acrobat XI Pro. This short video Micro Tutorial sh…
The Email Laundry PDF encryption service allows companies to send confidential encrypted  emails to anybody. The PDF document can also contain attachments that are embedded in the encrypted PDF. The password is randomly generated by The Email Laundr…

809 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question