Rectangles algorithm

[Boudewijn Rempt]

On Friday 08 June 2007, Cyrille Berger wrote:
> Hi,
>
> I took the time to experiment writting an algorithm that would create a set
> of rectangles from an other, but with an heuristic which allows to create
> rectangles which have area not cover by the original list of rectangles.
>
> As you can see bellow:
> http://cyrille.diwi.org/tmp/krita/rectangles.optimization.qregion1.png

Oh, cool! Dinner on me, next time we meet!

> Red rectangles are the output of the algorithm.
> Blue rectangles are the rectangles in the input.
>
> In fact the algorithm uses QRegion at the end to eliminates overlap, maybe
> a faster solution can be used, and there are some room to improve it even a
> bit further.
>
> So compared to QRegion it's 10 times faster, but the drawback is that it
> accept to cover a bigger area, so it slightly increase the cost of
> compositing.

That's acceptable, I think -- if it's possible to also subtract rectangles 
from the set. (We need that for setClean()).

> My next step is to see in action in Krita, but that's for next week.
>
> The source code of the test application:
> http://cyrille.diwi.org/tmp/krita/Rectangles.tar.bz2



-- 
Boudewijn Rempt 
http://www.valdyas.org/fading/index.cgi
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part.
Url : http://mail.kde.org/pipermail/kimageshop/attachments/20070608/af3662ad/attachment.pgp