# How to optimize this 2D overlap code for rotated rectangles

Hi!

Note: I’m not able to use already existing Roblox functions for this as everything relating to editing the drawing is happening on a ‘virtual’ UV grid.

I’m currently making a drawing game and I decided to add an eraser to it. Because the drawing may have a lot of parts, I wouldn’t be able to simply check where each parts of the drawing overlaps with the erased area so I decided to firstly do a simple rotated bound check so reduce significantly the number of complex checks needed.

So I’ve got this code that checks for overlaps between two rectangles but it seems that it could be optimized further as originally, it was made to handle pretty much any polygones with 4 points and not just only rotated rectangles.

``````function checkRectangleOverlap(rect1, rect2)
-- Get the axes of the rectangles

local rect1Axes = {
{rect1[2][1] - rect1[1][1], rect1[2][2] - rect1[1][2]},
{rect1[3][1] - rect1[2][1], rect1[3][2] - rect1[2][2]},
}

local rect2Axes = {
{rect2[2][1] - rect2[1][1], rect2[2][2] - rect2[1][2]},
{rect2[3][1] - rect2[2][1], rect2[3][2] - rect2[2][2]},
}

--print(rect1Axes, rect2Axes)

-- Check for overlap along each axis
for i = 1, 2 do
-- Get the projection of each rectangle onto the current axis
local rect1Min, rect1Max = math.huge, -math.huge--
local rect2Min, rect2Max = math.huge, -math.huge--

for j = 1, 4 do--
local dot = rect1[j][1] * rect1Axes[i][1] + rect1[j][2] * rect1Axes[i][2]
--print(dot)
rect1Min = math.min(rect1Min, dot)
rect1Max = math.max(rect1Max, dot)
end--

for j = 1, 4 do--
local dot = rect2[j][1] * rect1Axes[i][1] + rect2[j][2] * rect1Axes[i][2]
rect2Min = math.min(rect2Min, dot)
rect2Max = math.max(rect2Max, dot)
end--

-- Check if the projections overlap
if rect1Max < rect2Min or rect2Max < rect1Min then
return false
end
end

for i = 1, 2 do
-- Get the projection of each rectangle onto the current axis
local rect1Min, rect1Max = math.huge, -math.huge--
local rect2Min, rect2Max = math.huge, -math.huge--

for j = 1, 4 do--
local dot = rect1[j][1] * rect2Axes[i][1] + rect1[j][2] * rect2Axes[i][2]
rect1Min = math.min(rect1Min, dot)
rect1Max = math.max(rect1Max, dot)
end--

for j = 1, 4 do--
local dot = rect2[j][1] * rect2Axes[i][1] + rect2[j][2] * rect2Axes[i][2]
rect2Min = math.min(rect2Min, dot)
rect2Max = math.max(rect2Max, dot)
end--

-- Check if the projections overlap
if rect1Max < rect2Min or rect2Max < rect1Min then
return false
end
end

-- If all checks passed, the rectangles overlap
return true
end
``````

This code isn’t too slow but at really high number of parts it will cause lag. Further optimizations will also be implemented to reduce the number of bound checks but I still want to be safe by having this part as optimized as possible (50K checks take ~0.1s)

Thanks!

2 Likes

First of all, the script expects rectangles represented as tables in the format of {{x1, y1}, {x2, y2}, {x3, y3}, {x4, y4}} but it seems to be missing the fourth point, it should be {{x1, y1}, {x2, y2}, {x3, y3}, {x4, y4}}.

Second, in the following line of code:
local dot = rect1[j][1] * rect1Axes[i][1] + rect1[j][2] * rect1Axes[i][2]
and
local dot = rect1[j][1] * rect2Axes[i][1] + rect1[j][2] * rect2Axes[i][2]
rect1Axes or rect2Axes should be used instead of rect1.

Third, the function does not account for the case when rect1 and rect2 are the same rectangle, in this case, the function should return true.

Here is the fixed version of the script:

``````function checkRectangleOverlap(rect1, rect2)
if rect1 == rect2 then
return true
end
-- Get the axes of the rectangles
local rect1Axes = {
{rect1[2][1] - rect1[1][1], rect1[2][2] - rect1[1][2]},
{rect1[3][1] - rect1[2][1], rect1[3][2] - rect1[2][2]},
}

local rect2Axes = {
{rect2[2][1] - rect2[1][1], rect2[2][2] - rect2[1][2]},
{rect2[3][1] - rect2[2][1], rect2[3][2] - rect2[2][2]},
}

-- Check for overlap along each axis
for i = 1, 2 do
-- Get the projection of each rectangle onto the current axis
local rect1Min, rect1Max = math.huge, -math.huge
local rect2Min, rect2Max = math.huge, -math.huge

for j = 1, 4 do
local dot = rect1[j][1] * rect1Axes[i][1] + rect1[j][2] * rect1Axes[i][2]
rect1Min = math.min(rect1Min, dot)
rect1Max = math.max(rect1Max, dot)
end

for j = 1, 4 do
local dot = rect2[j][1] * rect2Axes[i][1] + rect2[j][2] * rect2Axes[i][2]
rect2Min = math.min(rect2Min, dot)
rect2Max = math.max(rect2Max, dot)
end

-- Check if the projections overlap
if rect1Max < rect2Min or rect2Max < rect1Min then
return false
end
end

-- If all checks passed, the rectangles overlap
return true
end``````

Hi!

Some of the changes that you made didn’t really makes sense to me but the code was only working when one of the rectangles was oriented. I did manage to find a way to optimize the code tough.

``````function checkRectangleOverlapOPti(rect1, rect2)
-- Get the axes of the rectangles

local rect1Axes = {
{rect1[2][1] - rect1[1][1], rect1[2][2] - rect1[1][2]},
{rect1[3][1] - rect1[2][1], rect1[3][2] - rect1[2][2]},
}

local rect2Axes = {
{rect2[2][1] - rect2[1][1], rect2[2][2] - rect2[1][2]},
{rect2[3][1] - rect2[2][1], rect2[3][2] - rect2[2][2]},
}

-- Check for overlap along each axis
for i = 1, 2 do
-- Get the projection of each rectangle onto the current axis
local rect1Min, rect1Max = math.huge, -math.huge
local rect2Min, rect2Max = math.huge, -math.huge

if i == 1 then
local dot = rect1[1][1] * rect1Axes[i][1] + rect1[1][2] * rect1Axes[i][2]
local dot2 = rect1[2][1] * rect1Axes[i][1] + rect1[2][2] * rect1Axes[i][2]

rect1Min = math.min(rect1Min, dot, dot2)
rect1Max = math.max(rect1Max, dot, dot2)
else
local dot = rect1[1][1] * rect1Axes[i][1] + rect1[1][2] * rect1Axes[i][2]
local dot2 = rect1[3][1] * rect1Axes[i][1] + rect1[3][2] * rect1Axes[i][2]

rect1Min = math.min(rect1Min, dot, dot2)
rect1Max = math.max(rect1Max, dot, dot2)
end

for j = 1, 4 do
local dot = rect2[j][1] * rect1Axes[i][1] + rect2[j][2] * rect1Axes[i][2]

rect2Min = math.min(rect2Min, dot)
rect2Max = math.max(rect2Max, dot)
end

-- Check if the projections overlap
if rect1Max < rect2Min or rect2Max < rect1Min then
return false
end
end

for i = 1, 2 do
-- Get the projection of each rectangle onto the current axis
local rect1Min, rect1Max = math.huge, -math.huge
local rect2Min, rect2Max = math.huge, -math.huge

for j = 1, 4 do
local dot = rect1[j][1] * rect2Axes[i][1] + rect1[j][2] * rect2Axes[i][2]
rect1Min = math.min(rect1Min, dot)
rect1Max = math.max(rect1Max, dot)
end

if i == 1 then
local dot = rect2[1][1] * rect2Axes[i][1] + rect2[1][2] * rect2Axes[i][2]
local dot2 = rect2[2][1] * rect2Axes[i][1] + rect2[2][2] * rect2Axes[i][2]

rect2Min = math.min(rect2Min, dot, dot2)
rect2Max = math.max(rect2Max, dot, dot2)
else
local dot = rect2[1][1] * rect2Axes[i][1] + rect2[1][2] * rect2Axes[i][2]
local dot2 = rect2[3][1] * rect2Axes[i][1] + rect2[3][2] * rect2Axes[i][2]

rect2Min = math.min(rect2Min, dot, dot2)
rect2Max = math.max(rect2Max, dot, dot2)
end

-- Check if the projections overlap
if rect1Max < rect2Min or rect2Max < rect1Min then
return false
end
end

-- If all checks passed, the rectangles overlap
return true
end
``````

Because both sides of the rectangle are pretty much the same, you could just get the dot product for both of these sides instead of doing it 4 times (as it just gives the same result but 2 extra times).

With this optimization, 50K tests take 0.085s when none of the rectangles intersect and 0.140s when they all do.

Would there be anything else that could optimize the code?

1 Like

If it works then I would not change anything with it.