util: add struct to track union of rectangles

The new struct rect_union is designed to make it easier to
efficiently accumulate a list of rectangles, and then operate
on an exact cover of their union.

Using rect_union, the times needed to added t rectangles, and then
compute their exact cover will be O(t), and something between Ω(t) and
O(t^2), depending on the rectangle arrangement. If one tries to do
the same by storing a pixman_region32_t and updating it with
pixman_region32_union_rect(), then total time needed would be between
Ω(t^2) and O(t^3), depending on the input. Without changing the public
API (data structure + rectangle ordering rules) for pixman_region32_t,
it is impossible to improve its worst case time.

1 files changed, 1 insertions, 0 deletions

diff --git a/util/meson.build b/util/meson.build
index 1cd7f65c..1c3dcd5a 100644
--- a/util/meson.build
+++ b/util/meson.build
@@ -5,6 +5,7 @@ wlr_files += files(
 	'env.c',
 	'global.c',
 	'log.c',
+	'rect_union.c',
 	'region.c',
 	'set.c',
 	'shm.c',