<p>I would say it’s a <a href="https://en.m.wikipedia.org/wiki/Set_cover_problem" rel="nofollow noreferrer">weighted set covering</a> problem.</p>

<p>In specific, the cost for a set of points is the number of extra pixels in the bounding rectangle of this set.</p>

<p>If the number of diff points is small, you can solve this by linear programming. Otherwise, try some approximated algorithms e.g. greedy.</p>

CC BY-SA 3.0
2017-11-14T17:19:54.190Z
2017-11-14T17:19:54.190Z
mushin
<p>I'd like to develop a system for web animation similar to animated gifs, like <a href="https://www.sublimetext.com/~jps/animated_gifs_the_hard_way.html" rel="nofollow noreferrer">this one</a>. I capture a series of screenshots at fixed time intervals, and then I'd like to animate them. I can trivially calculate the pixels which have changed from one frame to another, but I'd then like to calculate a set of rectangles such that blitting those rectangles over the previous frame results in the new one. There's a tradeoff between the number of rectangles and the number of "wasted" pixels, i.e. the number of pixels stored and copied which have not changed between the two frames. Is there a good algorithm for this which would give me control over the tradeoff parameter in some form?</p>

<algorithm><2d><pixel-graphics>
Calculate set of rectangles covering pixel diffs?
Colin
# Calculate set of rectangles covering pixel diffs?

(Asked by: username_0 on 2017-11-06)

I'd like to develop a system for web animation similar to animated gifs, like [this one](https://www.sublimetext.com/~jps/animated_gifs_the_hard_way.html). I capture a series of screenshots at fixed time intervals, and then I'd like to animate them. I can trivially calculate the pixels which have changed from one frame to another, but I'd then like to calculate a set of rectangles such that blitting those rectangles over the previous frame results in the new one. There's a tradeoff between the number of rectangles and the number of "wasted" pixels, i.e. the number of pixels stored and copied which have not changed between the two frames. Is there a good algorithm for this which would give me control over the tradeoff parameter in some form?

**Tags:** algorithm, 2d, pixel-graphics


---

## 1 answers

### Answer by username_1 on 2017-11-14. Score: 2

I would say it’s a [weighted set covering](https://en.m.wikipedia.org/wiki/Set_cover_problem) problem.

In specific, the cost for a set of points is the number of extra pixels in the bounding rectangle of this set.

If the number of diff points is small, you can solve this by linear programming. Otherwise, try some approximated algorithms e.g. greedy.


---

