[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