Re: [pygame] Dirty rect overlapping optimizations

[Greg Ewing <greg.ewing@xxxxxxxxxxxxxxxx>]

Ian Mallett wrote:
> Unfortunately, computing those rectangles is annoying, and 
> also O(n^2) in the number of rectangles

With the right data structures and algorithms, it doesn't have to be.
Apple's Quickdraw had some very efficient ways of representing and
operating on regions made up of collections of rectangles.

There's some info and further pointers about it here:

http://basalgangster.macgui.com/RetroMacComputing/The_Long_View/Entries/2010/8/29_Regions.html

--
Greg