Tuesday 17 June 2008
Advanced Topics In Computer Science #2: Rectangles
A while ago I wrote about the deep computer science problems of strings. Now I need to talk about another poorly understood data structure: rectangles. There are a couple of issues.
x1,y1,x2,y2 vs x,y,width,height Windows uses the former, most other libraries that I know of use the latter. If you mostly work with coordinates relative to the rectangle origin, then you'll probably prefer width+height, but otherwise I actually think Windows got this right! A lot of rectangle operations, such as union, intersection, and point containment are simpler in the x2+y2 format.
Union of empty rectangles Should the 'union' operation ignore empty rectangles or include them in the calculations? For example, what is the union of (100,100)-(100,200) with (100,100)-(200,100)? It depends on the use-case and is quite subtle. When the rectangle represents a set of pixels, for example a damage area that needs to be repainted, then you want 'union' to ignore empty rectangles, so the result in my example could be any empty rectangle. But when the rectangle represents the bounds of a set of points, then you want to return a non-empty rectangle in this case --- (100,100)-(200,200). (The difference between a pixel and a point is that a pixel has area, usually a 1x1 square, but a point is a mathematical point of zero size.) An example of this latter usage is when you're computing the bounds of a set of CSS boxes in order to determine how big a container must be to include them all.
So we want two forms of 'union' operator, or perhaps better still we should have two entirely different data structures for these two tasks. For pixel-set rectangles, there is only one logical "empty rectangle" --- all rectangles with zero width or height should be considered equal. For point-set rectangles, even if the width is zero the height and top-left can still be significant, and vice versa for height. This suggests we should separate the concepts.
The problem with having two data structures is that very often we need to convert one to the other --- to find the set of pixels that cover a point-set rectangle. (Off the top of my head, I can't think of situations where we need to convert pixel-sets to point-sets.) It would also be rather confusing for developers since I'm not aware of any libraries that make this distinction. Also, in Gecko, rectangles like the "overflow areas" are used to mean both pixel-sets and point-sets. For now, we'll just stick with different 'union' operators.
Comments
You could have getters for information like topY, rightX, bottomY, leftX, centerY, centerX, width, and height all on the same type. You just take whatever you want and don't worry about how it's implemented. Built-in support for getters, like in JavaScript or C#, would make this much nicer.
You could then measure which properties are accessed the most, and choose an implementation that provides the best average performance.
Of course, you'd also then want multiple constructors that each take four numbers. Since most languages don't support named constructors, you'd probably end up using something really messy and/or slow, like factory methods or a RectangleArgumentsFormat enum. Yuck.
Even if the rectangle describes bounds on a set of points, a zero-size rectangle can be ignored since no points can fall within it, whether "mathematical" or 1x1 pixels. The distribution of zero-size points should (ideally?) then too be described by a non-zero size rectangle, even if you're only interested in the bound on one dimension.
It sounds like the bounds of the "mathematical" point cloud in question aren't really rectangular but one-dimensional (i.e. the bounds apply to each dimension individually rather than to the point-cloud as a whole), in which case the "union" model probably isn't the best anyhow - then you'd probably want the rectangle whose bounds in each dimension are the union of the bounds in that dimension - which in turn is exactly the "union" operator you describe...
x1,
y1,
x2,
y2,
bool x1_inclusive,
bool y1_inclusive,
bool x2_inclusive,
bool y2_inclusive
Then you don't have to worry about which sides are inclusive, and you can choose to ignore the inclusivity on a function-level basis for when you do or don't care.
It'd be interesting to think of a case where you'd only want some of them inclusive, though, so this might not make sense...
Maybe just have a bool in the structure indicating it's a pixel-set: you only ever treat it all as inclusive or not (unless you'd want some advanced filter situation?).
At this point I'm struggling with problems akin to those you have described in the post.
How to represent rectangles? Which useful operations on rectangles are there?
I suppose one can use just one representation, say (x,y,w,h) and make width and height inclusive. Then you'd define a few constructors and selectors ("getters", but we are talking in terms of CS here, right?) and be done with it! :)
The answer to the question posed would be something like "do empty rectangles count?" (sometimes they do, sometimes not)
How about this solution? Please tell me how you solved your problem.