[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] Dirty rect overlapping optimizations

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.