2
$\begingroup$

I am using the Bresenham algorithm from wikipedia:

 plotLine(x0,y0, x1,y1)
      dx = x1 - x0
      dy = y1 - y0
      D = 2*dy - dx
      y = y0

     for x from x0 to x1
        plot(x,y)
        if D > 0
           y = y + 1
           D = D - 2*dx
        end if
        D = D + 2*dy

I have the following two points:

P1 = (10, 120) and P2 = (18, 117)

I wrote a C program to run the algorithm and I got as output:

ePlot the following points: 
10, 120
11, 120
12, 120
13, 120
14, 120
15, 120
16, 120
17, 120

Which is totally wrong, is there any other version of this algorithm which works for this scenario or it does not exist?

$\endgroup$
  • 2
    $\begingroup$ The algorithm as written is only for the case $\Delta x > \Delta y > 0$. In your case you have $\Delta y < 0$, which is why it does not work. See the complete algorithm under "All cases" instead. $\endgroup$ – user106 May 26 '19 at 20:30
2
$\begingroup$

Like Rahul said that algorithm is only in the case where $0 \lt \Delta y \lt \Delta x$.

So you need to adjust the coordinates to fit within that.

There are 8 cases:

  1. $0 \lt \Delta y \lt \Delta x$ the normal base case
  2. $0 \lt \Delta x \lt \Delta y$ swap x and y except for the drawPixel call.
  3. $\Delta x \lt 0 \lt \Delta y$ and $|\Delta y < \Delta x|$ use case 1 but negate $\Delta x$ and instead of counting from x0 to x1 you count from x1 to x0
  4. $\Delta x \lt 0 \lt \Delta y$ and $|\Delta x \lt \Delta y|$ use case 2 but negate $\Delta x$ and instead of counting from x0 to x1 you count from x1 to x0

The remaining cases have $\Delta y \lt 0$ so swap the 2 points and it will fall within the previous 4 cases.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.