Wednesday, 18 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.



8 comments:

  1. Ideally, you shouldn't have to know how the rectangle is implemented.
    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.

    ReplyDelete
  2. Robert O'Callahan18 June 2008 04:46

    Yeah, you can hide the implementation choice, but you still have to choose an implementation. That's what I'm interested in.

    ReplyDelete
  3. assuming the rectangle properties are read a whole lot more then they are written you could store both.

    ReplyDelete
  4. Robert O'Callahan18 June 2008 05:35

    No, space is important, not just for memory usage but also cache footprint.

    ReplyDelete
  5. I think the important question is rather which bounds are inclusive and which exclusive. As most people quickly note writing for-loops, it's very handy to have an upper bound which is exclusive. I'd lean toward the x1,y1,x2,y2 representation with x2 and y2 exclusive upper bounds. As long as that's a firm requirement, the union distinction you describe doesn't apply:
    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...

    ReplyDelete
  6. Perhaps have a data structure:
    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?).

    ReplyDelete
  7. i want to knwo more about computer science

    ReplyDelete
  8. Artyom Shalkhakov19 August 2009 07:02

    Hey, an interesting blog you have here. :)
    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.

    ReplyDelete