Optimize "diff" movement over spatial grid

I'm trying to find an efficient way to update a spatial grid which contains information about which object is on which grid cell. The objects move. For example:

···AAA···
···AAA···
···AAA···
·········

The object A occupies 9 cells in the grid. Now it moves down and to the right one position:

·········
····AAA··
····AAA··
····AAA··

The "brute force" approach would remove object A from all cells and then it would add A to the new cells. This however is very inefficient because 4 of the cells involved already contain A. What I would like to do instead is only to operate on the "diff":

···---···
···-··+··
···-··+··
····+++··

This is, adding "A" to the cells with a + and remove it from the cells with a -. Leaving the rest as they are.

A can be considered to be defined by its left,right,top and bottom coordinates:

Before: l0,r0,t0,b0
After: l1,r1,t1,b1

The movement can occur in any direction, not just always left and bottom. The object can change in size as it moves, so the "After" could become bigger or smaller than the "Before". "Before" and "After" don't always overlap, the objects can "teleport" around.

I would like to avoid even iterating over cells that are not part of the diff, it at all possible.

I'm implementing this in Lua, but I would appreciate an efficient algorithm in any language that I can translate.

Solution

I think I got it. Back to this image:

···---···
···-··+··
···-··+··
····+++··

The - and the + in the figure above both are "uppercase L" shapes. Depending on how the rectangles intersect the updated areas can take many "shapes". Most of them are rectangles. The Ls can take 4 "orientations" (⌜,⌝,⌞,⌟). Some Ls will have thick or thin "necks" and "bases". Optimally though, all you need to draw any uppercase L shape is two rectangles.

If one of the rectangles is bigger than the other ones, there can be some "C" shapes or even an "O" shape (one rectangle fully contains the other, which is smaller). So in the worst possible case we need 2 to "update" 4 rectangles.

Getting those rectangles calculated is tricky. I did ask ChatGPT, which put me on the right track, although I did have to massage and test the code quite a lot. Here's the result:

  -- "old" and "new" are intersecting
  if l1<r2 and l2<r1 and t1<b2 and t2<r2 then
    if l1<l2 then removecells(l1,t1,l2-1,b1) end
    if r1>r2 then removecells(r2+1,t1,r1,b1) end
    if t1<t2 then removecells(max(l1,l2),t1,min(r1,r2),t2-1) end
    if b1>b2 then removecells(max(l1,l2),b1,min(r1,r2),b2+1) end

    if l2<l1 then addcells(l2,t2,l1-1,b2) end
    if r2>r1 then addcells(r1+1,t2,r2,b2) end
    if t2<t1 then addcells(max(l1,l2),t2,min(r1,r2),t1-1) end
    if b2>b1 then addcells(max(l1,l2),b1+1,min(r1,r2),b2) end
  
  -- "old" and "new" are not intersecting. Apply the "brute force"
  -- option unless they are exactly the same, in which case we don't need
  -- to do any updates
  elseif l1~=l2 or r1~=r2 or t1~=t2 or b1~=b2 then
    removecells(l1,t1,r1,b1)
    addcells(l2,t2,r2,b2)
  end

From outside-in:

There's a special case where the "old" and "new" don't intersect. In that case you want to use the "brute force" approach and just add to all and delete from all cells. Even this has a special case; if "old" and "new" are the same you don't need to do anything.
When they intersect, you draw at most 2 small rectangles for deleting and adding. They can take any shape.
There's several call to min and max that ensure there's no "overlap" between the rectangles. You never delete or add more than once from the same rectangles.
There's several +1s and -1s in key places. This is mostly done to preserve the "common zone" between "old" and "new". Without those 1s we would end up "unnecessarily deleting/adding one extra column/row" from the common zone.