Commits

Anonymous committed c2affd5

Merge processing for rects #15 & #18. Other tiny optimizations.

  • Participants
  • Parent commits 7068c3e

Comments (0)

Files changed (1)

optimize_dirty_rects.py

 # optimize_dirty_rects
 """Optimize a list of dirty rects so that there are no overlapping rects
 
+    File version: 1.1
+
     Minimum Python version: 2.4
 
     Inspirations:
     # Determine the maximum possible size of all the rects combined
     extent_of_all_r = r.unionall(queue)
 
-    # If r covers the extent of all r, then no further optimization is
-    # possible.
+    # If any input rectangle covers the maximum possible size of all the rects
+    # combined, then that rectangle is optimal.
     if r == extent_of_all_r:
         #####debug('shortcut 1\n')
         return [r]
+    for r2 in queue:
+        if r2 == extent_of_all_r:
+            #####debug('shortcut 2\n')
+            return [r2]
 
     # Create lists that will always be sorted by left edge position,
     # right edge position, top edge position and bottom edge position.
     while queue:
 
         r = pop_from_queue()
-
-        if r == extent_of_all_r:
-            #####debug('shortcut 2\n')
-            return [r]
-
         r_id = id(r)
 
         ### Use bisect_left and set to get potential collisions ###
                 #r.bottom < r2.bottom:
                     elif r.left < r2.left:
 
-                        if r.right == r2.right:
-                            #####debug('p015')
+                        if r.right >= r2.right:
+                            #####debug('p015|p018')
                             # 15: RBT-R-TL:
                             # Crop r2 to the part that is below r.
                             # Update r2's location in edges_t.
                             # .|++. -> .|||.
                             # ..--.    ..--.
                             # .....    .....
+                            # 18: -BT-R-TL:
+                            # Crop r2 to the part that is below r.
+                            # Update r2's location in edges_t.
+                            # .....    .....
+                            # .|+|.    .|||.
+                            # .|+|. -> .|||.
+                            # ..-..    ..-..
+                            # .....    .....
                             _remove_r_from_edges_t(r2, r2_id, edges_t)
                             r2.height -= r.height
                             r2.top = r.bottom
                             insort(edges_t, (r2.top, r2_id))
 
-                        elif r.right < r2.right:
+                        else: #r.right < r2.right
                             #####debug('p016|p017')
                             # 16: RBT---TL:
                             # Crop r2 to the part that is below r.
                             insort(edges_t, (r2.top, r2_id))
                             r.width = r2.right - r.left
 
-                        else: #r.right > r2.right
-                            #####debug('p018')
-                            # 18: -BT-R-TL:
-                            # Crop r2 to the part that is below r.
-                            # Update r2's location in edges_t.
-                            # .....    .....
-                            # .|+|.    .|||.
-                            # .|+|. -> .|||.
-                            # ..-..    ..-..
-                            # .....    .....
-                            _remove_r_from_edges_t(r2, r2_id, edges_t)
-                            r2.height -= r.height
-                            r2.top = r.bottom
-                            insort(edges_t, (r2.top, r2_id))
-
             #r.top == r2.top:
                 #r.bottom < r2.bottom:
                     else: #r.left > r2.left
                             # .-...    .=...
                             # .....    .....
                             r3 = Rect(r.left, r.bottom, r2.width, r2.bottom - r.bottom)
+                            _remove_r_from_edges_b(r2, r2_id, edges_b)
                             _add_r(r3, id(r3), r_dict, edges_l, edges_r, edges_t, edges_b)
-                            _remove_r_from_edges_b(r2, r2_id, edges_b)
                             r2.height = r.top - r2.top
                             insort(edges_b, (r2.bottom, r2_id))
 
                             # ..-..    ..=..
                             # .....    .....
                             r3 = Rect(r2.left, r.bottom, r2.width, r2.bottom - r.bottom)
+                            _remove_r_from_edges_b(r2, r2_id, edges_b)
                             _add_r(r3, id(r3), r_dict, edges_l, edges_r, edges_t, edges_b)
-                            _remove_r_from_edges_b(r2, r2_id, edges_b)
                             r2.height = r.top - r2.top
                             insort(edges_b, (r2.bottom, r2_id))
 
                             # ..--.    ..==.
                             # .....    .....
                             r3 = Rect(r2.left, r.bottom, r2.width, r2.bottom - r.bottom)
+                            _remove_r_from_edges_b(r2, r2_id, edges_b)
                             _add_r(r3, id(r3), r_dict, edges_l, edges_r, edges_t, edges_b)
-                            _remove_r_from_edges_b(r2, r2_id, edges_b)
                             r2.height = r.top - r2.top
                             insort(edges_b, (r2.bottom, r2_id))
                             r.width = r2.right - r.left
                             # .--.    .==..
                             # .....    .....
                             r3 = Rect(r2.left, r.bottom, r2.width, r2.bottom - r.bottom)
+                            _remove_r_from_edges_b(r2, r2_id, edges_b)
                             _add_r(r3, id(r3), r_dict, edges_l, edges_r, edges_t, edges_b)
-                            _remove_r_from_edges_b(r2, r2_id, edges_b)
                             r2.height = r.top - r2.top
                             insort(edges_b, (r2.bottom, r2_id))
                             r.width = r.right - r2.left