[plt-scheme] 2htdp/image

On Wed, Nov 18, 2009 at 3:29 PM, Stephen Bloch <sbloch at adelphi.edu> wrote:
>
> On Nov 18, 2009, at 4:07 PM, Robby Findler wrote:
>
>> What you describe in the first paragraph (below) is what htdp/image
>> did, except that it didn't provide the second equality operator, only
>> the bitmap-based one. One of the things we found is that doing a full
>> bitmap comparison for equality was too expensive for systems and that
>> was part of the impetus for 2htdp/image.
>
> Gee, and I thought it was getting arbitrary rotations to work :-)

Rotations was also part of the impetus for 2htdp/image. There were a
few other things too.

> Yes, full bitmap comparisons will be expensive: you have to (a) flatten the
> image to a bitmap, and (b) compare it bit by bit.  But if you cache the
> flattened bitmap, at least you can amortize the time for (a) over multiple
> comparisons and displays.

Yes, and the current htdp/image library does this (and so your
libraries inherit this behavior, I believe).

>> Finally, what you say about matrices (in a followup message) doesn't
>> really work for rotation because you need to compute the bounding box
>> of the shape (to be prepared for future overlays and stuff) and thus
>> you actually need to do a linear time computation to find that bound
>> box (ie, apply the matrix to all of the points in the shape)-- it
>> isn't just (constant time) matrix multiply. But yes, thinking thru all
>> of these issues is what we've been doing recently.
>
> Hmm.  We should be able to do better than "apply the matrix to all of the
> points in the shape."
>
> Do you really need a bounding box precomputed (as opposed to computing it
> only when you actually need it)?

No, but most operations need it, so it will be computed. Repeated
rotations (without intervening overlays) won't need it, but it didn't
seem worth going the lazy route for that, since it seems uncommon.

> How about replacing the bounding box with a convex hull?  To compute the
> convex hull after a rotation (or reflection or scaling or translation or
> skewing or whatever) you would simply apply the matrix to each of the
> vertices of the convex hull.  In fact, like the "cached bitmap" I mentioned
> in a previous message, you don't need to store a convex hull at each node of
> the tree.  When you apply any of the matrix-multiply operations (rotate,
> reflect, scale, translate, skew) to an image that has a known convex hull,
> just compose the new matrix with the existing one.  The only times you need
> to actually COMPUTE a convex hull (by multiplying a matrix by all the
> vertices of the previous one) are when you're about to do a crop, an
> overlay, or a display.

I thought about that too, but it didn't seem worth the effort because
it won't give an asymptotic speed up.

That possibility is still open, of course, if we do run into
performance problems (but it seems like premature optimization at this
point).

> And since you don't actually need a precise convex hull, you can do a sort
> of "conservative convex hull" that merges any two vertices that are closer
> than a certain distance apart, so the hulls don't get enormous themselves.

But then the bounding boxes will start getting less precise, no? You
don't want a situation where repeating a series of operations and
(what seem like) inverses grows the bounding box. Can you avoid that
here?

Robby