Interesting math problem

[Ivan Illarionov]

On Mar 19, 2:17 pm, "BJörn Lindqvist" <bjou... at gmail.com> wrote:
> On Mon, Mar 17, 2008 at 11:57 PM, Arnaud Delobelle
>
>
>
> <arno... at googlemail.com> wrote:
> >  > def make_slope(distance, parts):
> >  >     step = distance / float(parts)
> >  >     intstep = int(step)
> >  >     floatstep = step - intstep
>
> >  >     steps = []
> >  >     acc = 0.0
> >  >     for i in range(parts):
> >  >         acc += floatstep
> >  >         step = intstep
> >  >         if acc > 0.999:
> >  >             step += 1
> >  >             acc -= 1.0
> >  >         steps.append(step)
> >  >     return steps
>
> >  OK then, using list comprehensions.  It is more succint, is it easier
> >  to read?
>
> >  def slope(dist, parts):
> >     return [(i+1)*dist/parts - i*dist/parts for i in xrange(parts)]
>
> Congratulations! You Won! Jeff Schwab's recursive approach is also
> cool but this is the most interesting abuse of integer division I have
> seen. I don't think any of the variants are readable at a first
> glance, but with a comment it should be ok.
>
> --
> mvh Björn

I really want to revive this discussion. Arnaud's approach is
definetly cool, but it turns out that in real-world situations it
doesn't work as succint as here.

Try to use it to draw a simple non-anitaliased line in a standrad
python array or buffer object. Suppose we have an array of unsigned
bytes called `buf` where each line takes `pitch` bytes. That's what I
got while trying to take advantage of this approach. No advantage at
all. And what about ability to port the code to C for speed?

def draw_line(buf, pitch, x, y, dx, dy):
    if dx == dy == 0:
        buf[y * pitch + x] = 0
        return
    xdir, ydir = 1, 1

    if dx < 0:
        xdir = -1
        dx = abs(dx)
    if dy < 0:
        ydir = -1
        dy = abs(dy)

    if dy < dx:
        steps = ((i+1) * dx / dy - i * dx / dy for i in xrange(dy))
        for step in steps:
            start = y * pitch + x
            if xdir > 0:
                buf[start : start + step] = array('B', [0] * step)
            else:
                buf[start - step : start] = array('B', [0] * step)
            x += step * xdir
            y += ydir
    else:
        steps = ((i+1) * dy / dx - i * dy / dx for i in xrange(dx))
        for step in steps:
            start = y * pitch + x
            if ydir > 0:
                for i in range(start, start + pitch * step, pitch):
                    buf[i] = 0
            else:
                for i in range(start, start - pitch * step, -pitch):
                    buf[i] = 0
            x += xdir
            y += step * ydir

Please, tell me that I'm wrong and it's really possible to draw lines,
do scan-conversion and so on with such a cool succint constructs!

--
Ivan