How to optimize this 2D overlap code for rotated rectangles

Help and Feedback Code Review
#1

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
#2

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
#3

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
#4

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