Edit: If you're searching for a good explination of a Dirty Rectangle System, read axilmar's posts below, they go through in detail and include many ASCII drawings as aids.
Aeiii! Headache city. I've dedicated about the last week or so to getting my DR system to work correctly, starting over about 5 times so far. The basic components I understand, draw to a buffer, store those corrodinates in a vector of some sort, check for overlapping rectangles, divide and conqueror. Keep a current list and and old list, combine the two into one list (check for overlapping again) and draw the final list buffer -> screen, background -> buffer.
All of it is simple enough except for one part.. Overlapping. I just can't seem to get it right.
I did some research, to try and see if there was an example I could understand, and these are what I found:
DRS: the 'Dirty Rectangle System' seemed like a nice enough system, except that it was missing the one part I wanted to mimic, overlapping. It simply just stored all the rectangles and never checked for overlapping.
Allegro Demo: Again same thing, the dirty rectangle system didnt check for overlapping
Steve Terry's NAS GUI: Here I found a working DRS with overlapping 
. Now my problem is I barely can understand the code, let alone copy it. The guts of the overlapping is in one function some 100 lines long with int flags and bit moves. Needless to say I got lost in seconds.
So, this brings me to my main issue, getting this thing to work 
.
Heres some relevant code:
| 1 | void tile_blit(BITMAP *src, BITMAP *des) { |
| 2 | for(int x = 0; x < des->w; x += src->w) |
| 3 | for(int y = 0; y < des->h; y += src->h) |
| 4 | blit(src, des, 0, 0, x, y, src->w, src->h); |
| 5 | } |
| 6 | |
| 7 | std::list<dirty_zone*> dirty_zones; |
| 8 | std::list<dirty_zone*> cleanup_zones; |
| 9 | std::list<dirty_zone*> current_job; |
| 10 | bool buf_store_moded = false; |
| 11 | |
| 12 | void stuoop_buf_blit() { |
| 13 | |
| 14 | // ... |
| 15 | |
| 16 | std::list<dirty_zone*>::iterator citr = cleanup_zones.begin(); |
| 17 | |
| 18 | for(int i = 0; citr != cleanup_zones.end(); citr++, i++) { |
| 19 | mark((*citr)->x1, (*citr)->y1, (*citr)->x2, (*citr)->y2, current_job); |
| 20 | |
| 21 | delete *citr; |
| 22 | } |
| 23 | |
| 24 | cleanup_zones.clear(); |
| 25 | |
| 26 | std::list<dirty_zone*>::iterator itr = dirty_zones.begin(); |
| 27 | |
| 28 | for(; itr != dirty_zones.end(); itr++) { |
| 29 | mark((*itr)->x1, (*itr)->y1, (*itr)->x2, (*itr)->y2, current_job); |
| 30 | |
| 31 | cleanup_zones.push_back(*itr); |
| 32 | } |
| 33 | |
| 34 | |
| 35 | dirty_zones.clear(); |
| 36 | |
| 37 | std::list<dirty_zone*>::iterator jitr = current_job.begin(); |
| 38 | |
| 39 | for(; jitr != current_job.end(); jitr++) { |
| 40 | blit( buf, screen_dest, (*jitr)->x1, (*jitr)->y1, (*jitr)->x1 + x, (*jitr)->y1, (*jitr)->x2 - (*jitr)->x1, (*jitr)->y2 - (*jitr)->y1); |
| 41 | // notice the + x used above is for hardware scrolling optimization |
| 42 | blit(background, buf, (*jitr)->x1, (*jitr)->y1, (*jitr)->x1, (*jitr)->y1, (*jitr)->x2 - (*jitr)->x1, (*jitr)->y2 - (*jitr)->y1); |
| 43 | |
| 44 | delete *jitr; |
| 45 | } |
| 46 | |
| 47 | current_job.clear(); |
| 48 | |
| 49 | // ... |
| 50 | |
| 51 | } |
| 52 | |
| 53 | void _mark(list<dirty_zone*>&,list<dirty_zone*>&,dirty_zone*,int,int,int,int); |
| 54 | |
| 55 | inline void mark(int x1, int y1, int x2, int y2, list<dirty_zone*> &dest) { |
| 56 | dirty_zone *current_new = new dirty_zone(x1, y1, x2, y1); |
| 57 | |
| 58 | list<dirty_zone*> mark_list; |
| 59 | |
| 60 | _mark(dest, mark_list, current_new, x1, y1, x2, y2); |
| 61 | |
| 62 | list<dirty_zone*>::iterator itr = mark_list.begin(); |
| 63 | |
| 64 | for(; itr != mark_list.end(); itr++) { |
| 65 | dest.push_back(*itr); |
| 66 | } |
| 67 | |
| 68 | delete current_new; |
| 69 | } |
| 70 | |
| 71 | inline int _get_quad(int x1, int y1, int x2, int y2, int x, int y) { |
| 72 | int ret = 0; |
| 73 | |
| 74 | if(x < x1) { |
| 75 | if(y < y1) |
| 76 | ret = 1; |
| 77 | else if(y < y2) |
| 78 | ret = 4; |
| 79 | else |
| 80 | ret = 7; |
| 81 | } else if(x < x2) { |
| 82 | if(y < y1) |
| 83 | ret = 2; |
| 84 | else if(y < y2) |
| 85 | ret = 5; |
| 86 | else |
| 87 | ret = 8; |
| 88 | } else { |
| 89 | if(y < y1) |
| 90 | ret = 3; |
| 91 | else if(y < y2) |
| 92 | ret = 6; |
| 93 | else |
| 94 | ret = 9; |
| 95 | } |
| 96 | |
| 97 | return ret; |
| 98 | } |
| 99 | |
| 100 | /* return values: |
| 101 | * 1 | 2 | 3 |
| 102 | * ----------------- |
| 103 | * 4 | 5 | 6 |
| 104 | * ----------------- |
| 105 | * 7 | 8 | 9 |
| 106 | * |
| 107 | * 5 represents dirty_zone *o |
| 108 | * _get_quad returns which quad x,y are in in relation to box o |
| 109 | */ |
| 110 | inline int _get_quad(dirty_zone *o, int x, int y) { |
| 111 | return _get_quad(o->x1, o->y1, o->x2, o->y2, x, y); |
| 112 | } |
| 113 | |
| 114 | inline int _mark_logic(list<dirty_zone*> &dirty_zones, list<dirty_zone*> &mark_list, dirty_zone *current_new, dirty_zone *o, int x1, int y1, int x2, int y2) { |
| 115 | if(x1 > x2) |
| 116 | std::swap(x1, x2); |
| 117 | if(y1 > y2) |
| 118 | std::swap(y1, y2); |
| 119 | |
| 120 | int o_upper_left = _get_quad(o, x1, y1); |
| 121 | int o_upper_right = _get_quad(o, x2, y1); |
| 122 | int o_lower_right = _get_quad(o, x2, y2); |
| 123 | int o_lower_left = _get_quad(o, x1, y2); |
| 124 | |
| 125 | int cn_upper_left = _get_quad(current_new, x1, y1); |
| 126 | int cn_upper_right = _get_quad(current_new, x2, y1); |
| 127 | int cn_lower_right = _get_quad(current_new, x2, y2); |
| 128 | int cn_lower_left = _get_quad(current_new, x1, y2); |
| 129 | |
| 130 | // Must have all corners inside current_new to continue, if we dont return fail |
| 131 | if(cn_upper_left != 5 || cn_upper_right != 5 || cn_lower_right != 5 || cn_lower_left != 5) |
| 132 | return false; |
| 133 | |
| 134 | // Cant have all corners inside original (o), if we do return fail |
| 135 | if(o_upper_left == 5 && o_lower_right == 5) |
| 136 | return false; |
| 137 | |
| 138 | // Must have one corner inside original (o) to continue, if we dont, then this is a finished square, return success |
| 139 | if(o_upper_left != 5 && o_upper_right != 5 && o_lower_right != 5 && o_lower_left != 5) |
| 140 | return true; |
| 141 | |
| 142 | // horizontal overlapping |
| 143 | _mark(dirty_zones, mark_list, current_new, x1, y1, o->x1, y2); |
| 144 | _mark(dirty_zones, mark_list, current_new, o->x2, y1, x2, y2); |
| 145 | |
| 146 | // verticle overlapping (this crops corners) |
| 147 | _mark(dirty_zones, mark_list, current_new, MAX(x1, o->x2), y1, MIN(x2, o->x2), o->y1); |
| 148 | _mark(dirty_zones, mark_list, current_new, MAX(x1, o->x2), o->y2, MIN(x2, o->x2), y2); |
| 149 | |
| 150 | return false; |
| 151 | } |
| 152 | |
| 153 | void _mark(list<dirty_zone*> &dirty_zones, list<dirty_zone*> &mark_list, dirty_zone *current_new, int x1, int y1, int x2, int y2) { |
| 154 | if(x1 > x2) |
| 155 | std::swap(x1, x2); |
| 156 | if(y1 > y2) |
| 157 | std::swap(y1, y2); |
| 158 | |
| 159 | if(!(x2 - x1) || !(y2 - y1)) |
| 160 | return; |
| 161 | |
| 162 | bool mark_now = true; |
| 163 | |
| 164 | std::list<dirty_zone*>::iterator itr = dirty_zones.begin(); |
| 165 | |
| 166 | for(int id = 0; itr != dirty_zones.end(); itr++, id++) { |
| 167 | mark_now = _mark_logic(dirty_zones, mark_list, current_new, *itr, x1, y1, x2, y2); |
| 168 | } |
| 169 | |
| 170 | if(mark_now) |
| 171 | mark_list.push_back(new dirty_zone(x1, y1, x2, y2)); |
| 172 | } |
I've uploaded my project at its current status so its possible to see the issues in this system in real time.
tar format
zip format
Both formats should work on any unix with gcc, windows with mingw32, or DOS with djgpp.
Is there anyone who understands this stuff? I sure dont .
edit: the controls for the linked project:
Left shift : call mark(0, 0, SCREEN_W, SCREEN_H) i.e. try to redraw the whole screen
Right shift : animate boxes on screen (theres 2 of them)
Enter : set second_countdown to 10 (fairly useless in this example)
Up Arrow : make the rectangles bounce faster (you'll only notice a differnce if you're also holding the right shift key)
Down Arrow : make the rectangles bounce slower (or backwards) (you'll only notice a differnce if you're also holding the right shift key)
Steve Terry's NAS GUI: Here I found a working DRS with overlapping . Now my problem is I barely can understand the code, let alone copy it. The guts of the overlapping is in one function some 100 lines long with int flags and bit moves. Needless to say I got lost in seconds.
Heh thanks 
I stole it and modified it from COUGH*Mirans*COUGH version What's wrong with it, it's just a bit of recursion.... oooh and I found a way to optimize recursion too with some tricky assembly and stack winding I may have to use one day 
It's a pretty slick concept, you simply modify the stack so that when the end condition is met instead of unwinding the stack you simply pop right out of the sucker. I think we found though through bitter discussion is that overlapping can be a bottleneck and it's generally best to just not do it, there were a variet of other DRS methods discussed too, I still like optimized blits though, at least it makes you feel good knowing you did something cool.
Solving rectangle overlapping is a difficult thing to grasp at the beginning, but once you understand the basic concepts, it suddently becomes very easy.
The problem is about how to combine two collections of rectangles into a third one without having overlapping parts. A solution is to 'subtract' the overlapping parts from one of the lists, then combine the other list with the new list:
//first list LIST A //second list LIST B //list that contains all rectangles of B except the rectangles of A TEMP LIST = LIST B - LIST A //optimal list that contains all rectangles of A plus all rectangles of B not overlapping with A OPTIMAL LIST = LIST A + TEMP LIST
In order to subtract one list from another, you have to understand all the possible ways two rectangles can overlap. Put one rectangle in the center, then move the other around it. You may use two pieces of paper to understand the concept better.
The obvious cases are that 1) a rectangle completely overlaps another rectangle, 2) the rectangles don't overlap at all, 3) rectangles overlap partially. Let's see all the possible cases:
total overlapping
-------------------- |A | | | | ------------ | | |B | | | | | | | | | | | |----------- | | | | | --------------------
no overlapping
case a): rect A at left of B
-------------------- |A | | | | | ------------ | | |B | | | | | | | | | | | ------------ | | | | --------------------
case b): rect A at right of B
-------------------- |A | | | ------------ | | |B | | | | | | | | | | | ------------ | | | | | | --------------------
case c): rect A above B
case d): rect A below B
There are also 4 more cases: A at left-above B, A at left-below B, A at right-above B, A at right-below B.
partial overlapping
Partial overlapping is the trickiest part to understand, as there are many cases. A rectangle A may overlap a rectangle B in such a way that:
1) only one part of B is visible.
2) only two parts of B are visible: a) one part from the left side and one part from the right side or b) one part from the top side and one part of the bottom side.
3) rectangle A overlaps a corner of B.
4) rectangle A overlaps a middle portion of one side of B.
5) rectangle A is in the middle of B.
Let's see some examples.
case (1): only one part of B is visible
Horizontally:
-------------------- |A | | | | |------ | |B | | | | | | | | |------ | | | | --------------------
or
-------------------- |A | | | -----| | |B | | | | | | | | -----| | | | | | --------------------
Vertically:
------------ |B | | | -------------------- |A | | | | | | | | | | | | | | | | | --------------------
Or
-------------------- |A | | | | | | | | | | | | | | | | | -------------------- |B | | | ------------
case (2): only two parts of B are visible
----------------- |B | | | ------------------------- |A | | | | | ------------------------- | | | | -----------------
or
|-------------| |A | -----| |----- |B | | | | | | | | | | | | | | | -----| |----- | | ---------------
case (3): rectangle A overlaps a corner of B
-------------------- |A | | | | | | | | | | | | |------- | | | | | | -------------------- | |B | | | -------------
or
------------- |B | | | -------------------- | |A | | | | | | |------- | | | | | | | | | | | | --------------------
or
------------- |B | | | | -------------------- | |A | | | | --------| | | | | | | | | | | | | | --------------------
or
-------------------- |A | | | | | | | | | | | --------| | |B | | | | | | -------------------- | | | | -------------
case (4) rectangle A overlaps a middle portion of one side of B.
------------- |B | | | -------------- | |A | | | | | | | | | | | -------------- | | | | | -------------
Or
------------- |B | | | | -------------- | |A | | | | | | | | | | | -------------- | | | | -------------
Or
----------- |A | -----| |----- |B | | | | | | | | ----------- | | | | | ---------------------
Or
--------------------- |B | | | | ----------- | | |A | | | | | | -----| |----- | | -----------
case (5) rectangle A is in the middle of B.
-------------------- |B | | | | ------------ | | |A | | | | | | | | | | | |----------- | | | | | --------------------
The above is the first part. Somebody please post a little message so I can post the 2nd part.
Somebody please post a little message so I can post the 2nd part.
hey i will!
now whose the kind person who gave the long post about rectangles on this
thread ?
good on ya
Here is the 2nd part:
Analysis
What we see from the above is that rectangle A splits rectangle B into one or more rectangles. Let's see how rectangle B is splitted.
Total overlap:
In total overlap, there is no left overs from rectangle B.
No overlap:
When two rectangles don't overlap, B remains as is.
Partial overlap:
(Area covered with '////' is the remaining rectangle)
Rectangle A splits rectangle B in one rectangle:
-------------------- |A | | | | |------ | |B1///| | |/////| | |/////| | |------ | | | | --------------------
-------------------- |A | | | -----| | |B1//| | |////| | |////| | -----| | | | | | --------------------
------------ |B1////////| |//////////| -------------------- |A | | | | | | | | | | | | | | | | | --------------------
-------------------- |A | | | | | | | | | | | | | | | | | -------------------- |B1////////| |//////////| ------------
Rectangle A splits rectangle B in two rectangles:
----------------- |B1/////////////| |///////////////| ------------------------- |A | | | | | ------------------------- |B2/////////////| |///////////////| -----------------
|-------------| |A | -----| |----- |B1//| |B2//| |////| |////| |////| |////| |////| |////| -----| |----- | | ---------------
-------------------- |A | | | | | | | | | | | | |------- | |B2////| | |//////| -------------------|------| |B1/////////| |///////////| -------------
------------- |B1/////////| |///////////| -------------------|------| |A |B2////| | |//////| | |------- | | | | | | | | | | | | --------------------
------------- |B1/////////| |///////////| |-------|------------------- |B2/////|A | |///////| | --------| | | | | | | | | | | | | | --------------------
-------------------- |A | | | | | | | | | | | --------| | |B1/////| | |///////| | |-------|------------------- |B2/////////| |///////////| -------------
Rectangle A splits rectangle B in three rectangles:
------------- |B1/////////| |///////////| ------------------ |A |B2/| | |///| | |///| | |///| ------------------ |B3/////////| |///////////| -------------
Or
------------- |B1/////////| |///////////| ------------------- |B2//|A | |////| | |////| | |////| | ------------------- |B3/////////| |///////////| -------------
Or
----------- |A | -----| |----- |B1//| |B3//| |////| |////| |////-----------////| |////|B2///////|////| |////|/////////|////| ---------------------
Or
--------------------- |B1//|B2///////|B3//| |////|/////////|////| |////-----------////| |////|A |////| |////| |////| -----| |----- | | -----------
case (5) Rectangle A splits rectangle B in four rectangles:
-------------------- |B1////////////////| |//////////////////| |------------------| |B2/|A |B3/| |///| |///| |///| |///| |------------------| |B4////////////////| |//////////////////| --------------------
As we can see, the splitting of rectangle B from rectangle A results to 0, 1, 2, 3 or 4 new rectangles. We see that splitting is done per side, i.e. the left side of rect A splits the left side of rect B, the top side of rect A splits the top side of rect B etc. Let's see how we can implement it.
Implementation
The following is only an example, of course. You may optimize it the way it suits you. I am going to use C++, as STL gives me a ground to talk on.
We need a routine that takes two rectangles as an input, and produces a list of rectangles that is the remains of the splitting, as it was described above. The routine supposes that the two rectangles overlap. Let's see the routine:
The above routine splits rectangle B into one or more rectangles by subtracting rectangle A from B. After the splitting, the rectangle B is no longer useful. The routine should be used in another routine that subtracts a rectangle from a rectangle list:
The above routine is useful in subtracting one list from the other:
//subtracts rectangle list 'a' from rectangle list 'b' void subtractList(RectList &b, const RectList &a) { for(RectIterator it = a.begin(); it != a.end(); ++it) { subtractRect(b, *it); } }
So the algorithm of optimally combine two rectangle lists becomes:
void combineLists(RectList &result, const RectList &a, const RectList &b) { //subtract list A from list B result = b; subtractList(result, a); //unite B-A with list A result.insert(result.end(), a.begin(), a.end()); }
Conclusions
The above algorithms may be optimized in numerous ways: rectangles can be kept in pre-allocated lists ordered by scanlines; arrays can be used instead double-linked lists; horizontal strips may be combined; rectangles can be ordered vertically from top to bottom in order to be nice to the screen refresh etc.
Other DRS algorithms
Another DRS algorithm, which is much simpler, is to divide the playing area into blocks, and mark each block that is dirty. When it is time to update the screen, blit all dirty blocks. By carefully chosing the size of blocks, an optimal speed may be achieved.
Dirty blocks can be placed in a list if their dirty flag is not set. Then the list of dirty blocks is traversed, each block's dirty flag is reset and the relevant area of the game buffer is blitted to the screen.
You can find an example of the above [url http://www.allegro.cc/forums/view_thread.php?_id=395646]here[/url].
The most glaring optimization to me would be that if subtracting A from B yields 3 or 4 rectangles, instead subtract B from A, which will result in 1 or 0 rectangles, respectively.
B-A != A-B.
The goal of overlap handling is to effectively OR the two buffers together (were they stored as a mask). In order to do this, you remove the intersection of A from B, then merge the two lists together. This is functionally the same as removing B from A and merging the two lists together. By doing this, you have fewer rectangles in the end product.
This is functionally the same as removing B from A
Nothing guarrantees that A-B is more optimizable than B-A and vice versa.
and merging the two lists together.
You have to unite the result with the other list though.
In a situation similar to the one below in figure 1, wouldn´t it be more effective to just blit the combined borders as in figure 2? (in that specific case) So that you get only one blit, and the rectangles are within a quite close range and aligned horizontally.
---------- ------- | | -------- | | | a | | b | | c | ---------- | | |-----| --------
Above -- Figure 1
---------------------------- | a:s left upper corner & | | a.left,b.bottom low left | | corner and c upper right | ----------------------------
Above -- Figure 2
Do anyone know of any good books/articles about different DRS algorithms? I would like to get a feeling for which solutions are commonly used.
aximilar: Look A splits B into 3 parts:</code> -------------
|B1/////////|
|///////////|
------------------
|A |B2/|
| |///|
| |///|
| |///|
------------------
|B3/////////|
|///////////|
-------------</code>BUT! What if we reversed it. B splits A! into 1 part! -------------
|B |
| |
-----| |
|A1//| |
|////| |
|////| |
|////| |
-----| |
| |
| |
-------------</code>The net result of this is that when you merge A and B you have fewer rectangles and thus fewer blits. I don't know how much of an actual speed optimization this is, but it's there, nonetheless.
In a situation similar to the one below in figure 1, wouldn´t it be more effective to just blit the combined borders as in figure 2? (in that specific case) So that you get only one blit, and the rectangles are within a quite close range and aligned horizontally.
It certainly would be more effective, but in order to do so you have to calculate distances between each pair of rectangles, either horizontally or vertically, which means that each rectangle should be compared with every other rectangle at least twice.
And then, how do you combine more than two rectangles in one blit?
There have to be some compromizes for such an optimization to work.
aximilar: Look A splits B into 3 parts:
BUT! What if we reversed it. B splits A! into 1 part!
The net result of this is that when you merge A and B you have fewer rectangles and thus fewer blits. I don't know how much of an actual speed optimization this is, but it's there, nonetheless.
I understood what you say in the first post. But you have to be aware that if you reverse the subtraction (do A-B instead of B-A), you have to subtract the result from the other list. In other words, you either do:
//list that contains all rectangles of B except the rectangles of A TEMP LIST = LIST B - LIST A //optimal list that contains all rectangles of A plus all rectangles of B not overlapping with A OPTIMAL LIST = LIST A + TEMP LIST
or you do:
//list that contains all rectangles of B except the rectangles of A TEMP LIST = LIST A - LIST B <---- your optimization here //optimal list that contains all rectangles of B plus all rectangles of A not overlapping with B OPTIMAL LIST = LIST B + TEMP LIST <---- needed change
There is no guarrantee that by doing the latter the subtraction will be more optimized. It may be so for one rectangle, but it may not be so for the other ones.
How would it not be an optimization for other ones? You have fewer rectangles, meaning fewer blits...
I just melt both rectangles in one, using the bounds to create it. Some parts that don't need to be blitted will be blitted, but still it is much faster than blitting a lot of small pieces in a near place.
How would it not be an optimization for other ones? You have fewer rectangles, meaning fewer blits...
Because it is not guarranteed that the rest of the rectangles will have a configuration similar to the one you showed.
But I covered all possible configurations. If A-B would result in 3 or 4 resultant rectangles (which we can check for), than instead do B-A, which results in 1 or 2 resultants, respectively. If A-B results in 0, 1, or 2 resulatants, than stick with A-B.
But I covered all possible configurations. If A-B would result in 3 or 4 resultant rectangles (which we can check for), than instead do B-A, which results in 1 or 2 resultants, respectively. If A-B results in 0, 1, or 2 resulatants, than stick with A-B.
The way the formula I posted works, if A and B are swapped in the rectangle subtraction, they have to be swapped in all the formulas.
And I am not sure if checking of how many rectangles the subtraction will result in is any different from the actual subtraction.
Consider the case with the largest difference. Case 5 in your above example. The way it is now, B-A, there are five rectangles in the end. Subtract A from B instead to see the new net: 1 rectangle.
Consider the case with the largest difference. Case 5 in your above example. The way it is now, B-A, there are five rectangles in the end. Subtract A from B instead to see the new net: 1 rectangle.
I understood what you said. Really. And you are correct, in the context of the rectangle subtraction. But unfortunately, it is not what we want.
If I do this:
------------- |B | | | -----| | |A1//| | |////| | |////| | |////| | -----| | | | | | -------------
instead of this
------------- |B1/////////| |///////////| ------------------ |A |B2/| | |///| | |///| | |///| ------------------ |B3/////////| |///////////| -------------
then the area A1 will exist twice in the final rectangle list: it will exist once in the intermediate temporary list that is the result of A-B and once in the list A.
Let's do the same example with sets. This is my way:
A = {1, 2, 3} B = {2, 4, 5} T = B - A = {2, 4, 5} - {1, 2, 3} = {4, 5} R = A + T = {1, 2, 3} + {4, 5} = {1, 2, 3, 4, 5}
In the above example, we end up with a set that all elements are unique. Now let's try your method:
A = {1, 2, 3} B = {2, 4, 5} T = A - B = {1, 2, 3} - {2, 4, 5} = {1, 3} R = A + T = {1, 2, 3} + {1, 3} = {1, 1, 2, 3, 3, 4, 5}
With your way, we end up with a set with duplicate elements. If an element was a rectangle, we would have duplicate rectangles.
A = {1, 2, 3} B = {2, 4, 5} T = A - B = {1, 2, 3} - {2, 4, 5} = {1, 3} R = B + T = {2, 4, 5} + {1, 3} = {1, 2, 3, 4, 5}
EDIT: Where is the union symbol in WinXP charmap? I could find intersection, but union was no where near it.
I'm not sure of your notation, but how difficult is it to remove A from the original list?
(Sorry for the long delay, I had a hurricane take me offline for a few days )
CGamesPlay, nothing guarrantees that by subtracting list A, the algorithm would be more optimizable than it is right now.
Axilmar, you should submit this to pixelate, its an awesome walk through, thanks!
I don't know how Pixelate works. Can anyone submit articles to it?
Yes, but Pixelate is kind of dead now. 