February 1996 Programmer's Challenge

Intersecting Rectangles

Mail solutions to: progchallenge@mactech.com

Due Date: 10 February 1996

The Challenge this month is to write a routine that will accept a list of rectangles and calculate a result based on the intersections of those rectangles. Specifically, your code will return a list of non-overlapping rectangles that contain all points enclosed by an odd (or even) number of the input rectangles. The prototype for the code you should write is:

void RectangleIntersections(
  const Rect inputRects[],  /* list if input rectangles */
  const long numRectsIn,    /* number of inputRects */
  Rect outputRects[],       /* preallocated storage for output */
  long *numRectsOut,        /* number of outputRects returned */
  const Boolean oddParity   /* see text for explanation */
);

The parameter oddParity indicates whether you are to return rectangles containing points enclosed by an odd number of the numRectsIn inputRects rectangles (oddParity==true) or by an even (nonzero) number of rectangles (oddParity==false). (Think of odd parity as the exclusive OR of the input rectangles.) Sufficient storage for the output will be preallocated for you and pointed to by outputRects.

As an example, if you were given these inputRects:

        {0,10,20,30}, {5,15,20,30}
 

... and oddParity were true, you might return one the following list of outputRects:

        {0,10,5,15}, {0,15,5,30}, {5,10,20,15}
 

(Note that the last two coordinates of the third rectangle were inadvertently transposed in the published problem statement.)

It would also be correct to return a result that combined the first of these rectangles with either of the other two. If oddParity were false, you would return the following list for the example input:

        {5,15,20,30}
 

The outputRects must be non-empty and non-overlapping. In the example, it would be incorrect to return the following for the odd parity case:

        {0,10,5,30} {0,10,20,15}
 

The outputRects you generate must also be maximal, in the sense that every x-coordinate in the output rectangle list must occur as an x-coordinate in the input rectangle list, and the likewise for y-coordinates. That is, no manufactered coordinates: I don't want you to return a 1x1 rectangle representing each point enclosed in the desired number of inputRects. Before returning, set *numRectsOut to indicate the number of outputRects you generated.

If you need auxiliary storage, you may allocate any reasonable amount within your code using toolbox routines or malloc, but you must deallocate that storage before returning. (No memory leaks! - I'll be calling your code many times.)

This native PowerPC Challenge will be scored using the latest Metrowerks compiler, with the winner determined by execution time. If you have any questions, or would like some test data for your code, please send me e-mail at one of the Programmer's Challenge addresses, or directly to bob_boonstra@mactech.com. Test data will also be sent to the Programmer's Challenge mailing list, which you can join by sending a message to autoshare@mactech.com with the SUBJECT line "sub challenge YourName", substituting your real name for YourName.

If you have any questions, please send me e-mail at one of the Programmer's Challenge addresses, or directly to boonstra@ultranet.com.

Back to the Programmer's Challenge Page