Interesting math problem

Arnaud Delobelle arnodel at googlemail.com
Sun Apr 13 22:06:48 CEST 2008


On Apr 13, 5:35 pm, Ivan Illarionov <ivan.illario... at gmail.com> wrote:
> 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

I don't think my answer is suitable for drawing a line the way you are
doing it.  FWIW, this is how I would go about it (not tested):

def draw_rectangle(buf, pitch, x, y, w, h):
    # Make a mask for w and apply it across h lines

def draw_line(buf, pitch, x, y, w, h):
    # w and h can't be < 0
    if w < h:
        limits = ((i, i*h/w) for i in xrange(1, w+1))
    else:
        limits = ((i*w/h, i) for i in xrange(1, h+1))
    dx0, dy0 = 0, 0
    for dx, dy in limits:
        draw_rectangle(x+dx0, y+dy0, dx-dx0, dy-dy0)
        dx0, dy0 = dx, dy

The positive thing is that it is trivial to extend draw_line so that
it accepts a thickness parameter as well.

--
Arnaud




More information about the Python-list mailing list