Re: [pygame] Dirty rect overlapping optimizations

[Ian Mallett <ian@xxxxxxxxxxxxxx>]

On Mon, Mar 27, 2017 at 5:26 PM, Greg Ewing <greg.ewing@xxxxxxxxxxxxxxxx> wrote:

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.

​I mean this in a fundamental, mathematical sense. With O(n) rectangles, you can produce O(n^2) regions that cannot be decomposed into fewer than O(n^2) disjoint rectangles.

Ian​