Math problem: two squares intersecting each other

[Zwiebelchen]

I got a simple maths problem I simply can not figure out, but I need it to complete a system I am writing atm.

I got two squares of equal edge size containing grid coordinates.

Both squares intersect each other. I need to get a simple formula to gather all grid coordinates that are in square A but not in square B and all coordinates that are in square B but not in square A.

See picture below:

example (edge size = 5):
o o o o o o o 7
o o x x x x x 6
* * / / / x x 5
* * / / @ x x 4
* * @ / / x x 3
* * / / / x x 2 
* * * * * o o 1
o o o o o o o 0
0 1 2 3 4 5 6

@: center coords of squares
crosses and stars are to be enumerated.

Can someone give me the fastest enumeration algorythm that matches the XOR condition here? I need an algorythm that ONLY enums the coordinates that are needed and would like to avoid useless enumerations of the intersection coordinates!
Basicly, an algorythm that uses as few enumeration steps as possible!

 

[Arhowk]

make square C by taking the minimum left X, minimum right X, minimum top Y, minimum bottom Y of both of the squares

than just enum all in square (a or b) and check if not in c

local real lx
local real rx
local real ty
local real by
local rect c3

if GetRectMinX(c1) < GetRectMinX(c2) then
    set lx = GetRectMinX(c2)
else
    set lx = GetRectMinX(c1)
endif
if GetRectMaxX(c1) > GetRectMaxX(c2) then
    set rx = GetRectMaxX(c2)
else
    set rx = GetRectMaxX(c1)
endif
if GetRectMinY(c1) < GetRectMinY(c2) then
    set by = GetRectMinY(c2)
else
    set by = GetRectMinY(c1)
endif
if GetRectMaxY(c1) > GetRectMaxY(c2) then
    set ty = GetRectMaxY(c2)
else
    set ty = GetRectMaxY(c1)
endif

set c3 = Rect(lx,by,rx,ty)

Not tested, but should work. (If only jass had ternary ops )

 

[muzzel]

Since your rects are axis-aligned you can split up the intersection into 9 disjoint areas of which a maximum of 6 are part of the desired resulting shape. Il use rectangles specified by: Rect(minX, maxX, minY, minY), the rectangles you want to intersect are a and b.

int xMinMin = min(a.minX, b.minX)
int xMaxMin = max(a.minX, b.minX)
int xMinMax = min(a.maxX, b.maxX
int xMaxMax = max(a.maxX, b.maxX)
int yMinMin = min(a.minY, b.minY)
int yMaxMin = max(a.minY, b.minY)
int yMinMax = min(a.maxY, b.maxY)
int yMaxMax = max(a.maxY, b.maxY)

Rect(xMaxMin, xMinMax, yMinMin, yMaxMin)
Rect(xMinMin, xMaxMin, yMaxMin, yMinMax)
Rect(xMinMax, xMaxMax, yMaxMin, yMinMax)
Rect(xMaxMin, xMinMax, yMinMax, yMaxMax)

if (a.minX < b.minX && a.minY < b.minY || b.minX < a.minX && b.minY < a.minY)
    Rect(xMinMin, xMaxMin, yMinMin, yMaxMin)
    Rect(xMinMax, xMaxMax, yMinMax, yMaxMax)
else
    Rect(xMinMax, xMaxMax, yMinMin, yMaxMin)
    Rect(xMinMin, xMaxMin, yMinMax, yMaxMax)

Iterate through the rects to get the coordinates (make sure this works for empty rects):

Rect(xMin, xMax, yMin, yMax)
for (x = xMin to xMax)
    for (y = yMin to yMax)
        doSomething(x, y)

You could do the same with some nested if/else instead of the min/max functions, slightly faster but more code. Tell me if required, but its not really a big difference, the above aproach should be pretty much the fastest solution.

 

[Zwiebelchen]

Arhowk:
That's exactly what I wanted to avoid, as it basicly enums all coordinates multiple times.
In the system I wrote, accessing a coordinate is the most operation intensive thing of the script.

For the example I presented above, I would enum:
all coordinates in C: 12
all coordinates in A: 25
all coordinates in B: 25

Plus I would have to compare A and C and B and C, which is at least another 24 operations!

Which makes a total of 86 coordinate access operations!
I only want to get the crosses and stars, so an optimized algorythm should only require 26 coordinate operations, as those are the coordinates that are actually outside of the intersection area.

@Muzzel:
Yeah I also thought of the 6 rectangle approach but couldn't find formulaes for the rect corner points that did not involve a lot of min/max operations. But looks like there is no way around it and at least I only need to get all those corner points once.

Is there a way to make it simpler by assuming A and B are always squares and always have the same size? Something like abusing symmetry?

EDIT:
Tested your algorythm with some actual numbers of the example above and it doesn't seem to be correct:

xMinMin: 0
xMaxMin: 2
xMinMax: 4
xMaxMax: 6

yMinMin: 1
yMaxMin: 2
yMinMax: 5
yMaxMax: 6

Rect(2, 4, 1, 2) //it should be 2, 4, 1, 1
Rect(0, 2, 2, 5) //it should be 0, 1, 2, 5
Rect(4, 6, 2, 5) //it should be 5, 6, 2, 5
Rect(2, 4, 5, 6) //it should be 2, 4, 6, 6

Conditional Rects:
if (0 < 2 && 1 < 2 || 2 < 0 && 2 < 1)
    Rect(0, 2, 1, 2) //it should be 0, 1, 1, 1
    Rect(4, 6, 5, 6) //it should be 5, 6, 6, 6
else
    Rect(4, 6, 1, 2) //it should be 5, 6, 1, 1
    Rect(0, 2, 5, 6) //it should be 0, 1, 6, 6

Probably fixed it:

int xMinMin = min(a.minX, b.minX)
int xMaxMin = max(a.minX, b.minX)
int xMinMax = min(a.maxX, b.maxX
int xMaxMax = max(a.maxX, b.maxX)
int yMinMin = min(a.minY, b.minY)
int yMaxMin = max(a.minY, b.minY)
int yMinMax = min(a.maxY, b.maxY)
int yMaxMax = max(a.maxY, b.maxY)

Rect(xMaxMin, xMinMax, yMinMin, yMaxMin-1)
Rect(xMinMin, xMaxMin-1, yMaxMin, yMinMax)
Rect(xMinMax+1, xMaxMax, yMaxMin, yMinMax)
Rect(xMaxMin, xMinMax, yMinMax+1, yMaxMax)

if (a.minX < b.minX && a.minY < b.minY || b.minX < a.minX && b.minY < a.minY)
    Rect(xMinMin, xMaxMin-1, yMinMin, yMaxMin-1)
    Rect(xMinMax+1, xMaxMax, yMinMax+1, yMaxMax)
else
    Rect(xMinMax+1, xMaxMax, yMinMin, yMaxMin-1)
    Rect(xMinMin, xMaxMin-1, yMinMax+1, yMaxMax)

 

[muzzel]

I had another idea:

if (a.minX < b.minX)
    // swap a, b
    Rect tmp = a
    a = b
    b = tmp

if (a.minX != b.minX)
    Rect(b.maxX, a.maxX, a.minY, a.maxY)
    Rect(b.minX, a.minX, b.minY, b.maxY)

if (a.minY < b.minY)
    Rect(a.minX, b.maxX, a.minY, b.minY)
    Rect(a.minX, b.maxX, a.maxY, b.maxY)

else if (b.minY < a.minY)
    Rect(a.minX, b.maxX, b.minY, a.minY)
    Rect(a.minX, b.maxX, b.maxY, a.maxY)

If you need a and b to be immutable use shallow copies of them instead of a and b directly.

 

[Lordkoon]

Someone address Magtheridon since he enjoys math so much.

 

[Zwiebelchen]

@Muzzel:
Neat idea to swap A and B to shorten the amount of code!
Tried two quick case scenarios:

example 1:
o o o o o o o 7
o o x x x x x 6
* * / / / x x 5
* * / / @ x x 4
* * @ / / x x 3
* * / / / x x 2 
* * * * * o o 1
o o o o o o o 0
0 1 2 3 4 5 6

a.minX = 2
a.maxX = 6
b.minX = 0
b.maxX = 4
a.minY = 2
a.maxY = 6
b.minY = 1
b.maxY = 5

if (2 < 0)
    ---

if (2 != 0)
    Rect(4, 6, 2, 6) //should be 5, 6, 2, 6
    Rect(0, 2, 1, 5) //should be 0, 1, 1, 5

if (2 < 1)
    ---

if (1 < 2)
    Rect(2, 4, 1, 2) //should be 2, 4, 1, 1
    Rect(2, 4, 5, 6) //should be 2, 4, 6, 6


example 2:
o o o o o o o 7
o o o o o o o 6
* * * * * O O 5
* * / / / x x 4
* * @ / / x x 3
* * / / @ x x 2 
* * / / / x x 1
o o x x x x x 0
0 1 2 3 4 5 6

a.minX = 2
a.maxX = 6
b.minX = 0
b.maxX = 4
a.minY = 0
a.maxY = 4
b.minY = 1
b.maxY = 5

if (2 < 0)
    ---

if (2 != 0)
    Rect(4, 6, 0, 4) //should be 5, 6, 0, 4
    Rect(0, 2, 1, 5) //should be 0, 1, 1, 5

if (0 < 1)
    Rect(2, 4, 0, 1) //should be 2, 4, 0, 0
    Rect(2, 4, 4, 5) //should be 2, 4, 5, 5

if (1 < 2)
    ---

So basicly this suffers from the same (border)-problem.
I think this should be correct:

if (a.minX < b.minX)
    // swap a, b
    Rect tmp = a
    a = b
    b = tmp

if (a.minX != b.minX)
    Rect(b.maxX+1, a.maxX, a.minY, a.maxY)
    Rect(b.minX, a.minX-1, b.minY, b.maxY)

if (a.minY < b.minY)
    Rect(a.minX, b.maxX, a.minY, b.minY-1)
    Rect(a.minX, b.maxX, a.maxY+1, b.maxY)

if (b.minY < a.minY)
    Rect(a.minX, b.maxX, b.minY, a.minY-1)
    Rect(a.minX, b.maxX, b.maxY+1, a.maxY)

Viewing this as a matrix, swapping both rects inside the lower two cases, the changes seem to have an internal logic, so I guess this makes sense:

(+1 0 0 0 )
(0 -1 0 0 )
(0 0 +1 0 )
(0 0 0 -1 )

I'll try two more case scenarios when I'm at home to confirm this. But I think you can't get it any shorter so basicly this is going to be the way I'll do it.

 

[muzzel]

For some reason i was assuming continuous coordinates, however your correction for discrete values looks valid.

 

[Zwiebelchen]

Did a little bit more of testing and this is the final piece of code that catches all cases flawlessly (btw: we also forgot the case in which the squares do not overlap at all).
Instead of swapping the squares for the c < lc case, I simply did the maths again and used an else stub for less overhead.

I will use this in DestructableHider and upload the new version asap.

private function ChangeTiles takes integer r, integer c, integer lr, integer lc returns nothing
    local integer AminX = c-TILE_RESOLUTION
    local integer AmaxX = c+TILE_RESOLUTION
    local integer AminY = r-TILE_RESOLUTION
    local integer AmaxY = r+TILE_RESOLUTION
    local integer BminX = lc-TILE_RESOLUTION
    local integer BmaxX = lc+TILE_RESOLUTION
    local integer BminY = lr-TILE_RESOLUTION
    local integer BmaxY = lr+TILE_RESOLUTION
    if AminX < 0 then
        set AminX = 0
    endif
    if AminY < 0 then
        set AminY = 0
    endif
    if BminX < 0 then
        set BminX = 0
    endif
    if BminY < 0 then
        set BminY = 0
    endif
    if AmaxX >= columns then
        set AmaxX = columns-1
    endif
    if AmaxY >= rows then
        set AmaxX = rows-1
    endif
    if BmaxX >= columns then
        set BmaxX = columns-1
    endif
    if BmaxY >= rows then
        set BmaxX = rows-1
    endif
    
    if BmaxX < AminX or AmaxX < BminX or BmaxY < AminY or AmaxY < BminY then
        call EnumRectangle(AminX, AmaxX, AminY, AmaxY, true)
        call EnumRectangle(BminX, BmaxX, BminY, BmaxY, false)
    else
        if c >= lc then
            if c != lc then
                call EnumRectangle(BmaxX+1, AmaxX, AminY, AmaxY, true)
                call EnumRectangle(BminX, AminX-1, BminY, BmaxY, false)
            endif
            if AminY < BminY then
                call EnumRectangle(AminX, BmaxX, AmaxY+1, BmaxY, false)
                call EnumRectangle(AminX, BmaxX, AminY, BminY-1, true)
            elseif BminY < AminY then
                call EnumRectangle(AminX, BmaxX, BmaxY+1, AmaxY, true)
                call EnumRectangle(AminX, BmaxX, BminY, AminY-1, false)
            endif
        else
            call EnumRectangle(AminX, BminX-1, AminY, AmaxY, true)
            call EnumRectangle(AmaxX+1, BmaxX, BminY, BmaxY, false)
            if AminY < BminY then
                call EnumRectangle(BminX, AmaxX, AminY, BminY-1, true)
                call EnumRectangle(BminX, AmaxX, AmaxY+1, BmaxY, false)
            elseif BminY < AminY then
                call EnumRectangle(BminX, AmaxX, BminY, AminY-1, false)
                call EnumRectangle(BminX, AmaxX, BmaxY+1, AmaxY, true)
            endif
        endif
    endif
endfunction

c, r, lc and lr are the center points of the two squares. TILESIZE is the number of coordinates from the center to the edge of the square.

 

[muzzel]

(btw: we also forgot the case in which the squares do not overlap at all).

in your first post it says "both squares intersect each other" :>