[plt-scheme] 2htdp/image

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 :-)

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.

> 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)?

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.

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.


Stephen Bloch
sbloch at adelphi.edu