使用 Bresenham画线算法绘制线时，该行可能不在要写入的位图的范围内-剪切结果将很有用，以便它们适合要写入的图像的轴对齐范围内.
When drawing a line with Bresenham line drawing algorithm, where the line may not be within the bounds of the bitmap being written to - it would be useful to clip the results so they fit within the axis aligned bounds of the image being written to.
虽然可以先将线剪裁到矩形，然后再画线.这是不理想的，因为它常常使(假设使用int坐标)线的倾斜度稍有不同.
While its possible to first clip the line to the rectangle, then draw the line. This isn't ideal since it often gives a slightly different slant to the line (assuming int coords are being used).
由于这是原始操作，是否存在在保持相同形状的同时剪切线的方法?
Since this is such a primitive operation, are there established methods for clipping the line while maintaining the same shape?
如果有帮助，请这是该算法的参考实现-它使用int坐标，这样可以避免在绘制直线时进行int/float转换.
In case it helps, here is a reference implementation of the algorithm - it uses int coords, which avoids int/float conversion while drawing the line.
我花了一些时间研究这个问题:
I spent some time looking into this:
- virtual-dub的网页上详细描述了问题a>.
- 艾伦·蒂德曼(Alan Tiedemann)可能的解决方案 ...尽管我需要基于文本实现代码-才能查看其效果.
- 具有内置剪切功能的布雷森汉姆线生成算法 (论文来自1995年，找不到整个文档吗?-PDF是没有参考的C代码的单个页面，看起来像是付费的墙.
让我们重新构造问题，以便我们了解布雷森汉姆算法的真正工作原理...
Let's reframe the problem so we can see how Bresenham's algorithm really works...
让我们说您正在画一条从(x0，y0)到(x1，y1)的基本上是水平的线(该方法对于大多数是垂直的，但是轴已切换):
Lets say you are drawing a mostly horizontal line (the method is the same for mostly vertical, but with the axes switched) from (x0,y0) to (x1,y1):
整行可以用 x (所有整数)描述为 y 的函数:
The full line can be described as a function of y in terms of x (all integers):
y = y0 + round( (x-x0) * (y1-y0) / (x1-x0) )这精确地描述了绘制整条线时要绘制的每个像素，并且当连续裁剪线时，它 still 精确地描述了要绘制的每个像素-您只需将其应用于较小的 x 值的范围.
This describes precisely each pixel you will paint when drawing the full line, and when you clip the line consistently, it still describes precisely each pixel you will paint -- you just apply it to a smaller range of x values.
我们可以使用所有整数数学，通过分别计算除数和余数来评估此函数.对于 x1> = x0 和 y1> = y0 (否则请进行常规转换):
We can evaluate this function using all integer math, by calculating the divisor and remainder separately. For x1 >= x0 and y1 >= y0 (do the normal transformations otherwise):
let dx = (x1-x0); let dy = (y1-y0); let remlimit = (dx+1)/2; //round up rem = (x-x0) * dy % dx; y = y0 + (x-x0) * dy / dx; if (rem >= remlimit) { rem-=dx; y+=1; }布雷森纳姆(Bresenham)算法是在更新 x 时递增地更新此公式结果的一种快速方法.
Bresenham's algorithm is a just a fast way to update the result of this formula incrementally as you update x.
在这里，我们可以利用增量更新来绘制从x = xs到x = xe的同一行的一部分:
Here's how we can make use of incremental updates to draw the portion of the very same line from x=xs to x=xe:
let dx = (x1-x0); let dy = (y1-y0); let remlimit = (dx+1)/2; //round up x=xs; rem = (x-x0) * dy % dx; y = y0 + (x-x0) * dy / dx; if (rem >= remlimit) { rem-=dx; y+=1; } paint(x,y); while(x < xe) { x+=1; rem+=dy; if (rem >= remlimit) { rem-=dx; y+=1; } paint(x,y); }如果要对0进行余数比较，则可以在开始时将其偏移:
If you want do to your remainder comparisons against 0, you can just offset it at the beginning:
let dx = (x1-x0); let dy = (y1-y0); let remlimit = (dx+1)/2; //round up x=xs; rem = ( (x-x0) * dy % dx ) - remlimit; y = y0 + (x-x0) * dy / dx; if (rem >= 0) { rem-=dx; y+=1; } paint(x,y); while(x < xe) { x+=1; rem+=dy; if (rem >= 0) { rem-=dx; y+=1; } paint(x,y); }更多推荐
如何将Bresenham的画线算法与裁剪一起使用?
发布评论