Given a table of Rectangle of different sizes (and can be merged together), how would you generate a point in it with equal probability?

[iiau]

Say, for example, you got several Rectangles in a table like this,

And you want to get a point with equal probability like this;

How would I write a function that would get a point with equal probability across all rectangles?
No rotations.

[XAXA]

The quick way (not in terms of efficiency, but in terms of implementing what you want) would probably be:

1. Get the bounding box of all the rectangles.
2. Generate a random point inside this bounding box (this is trivial).
3. Iterate through all the rectangles and check if it’s inside one of them. If it is, then there’s you’re random point! Otherwise, repeat 2 until you do.

This would perform really badly if, for example, the rectangles are very far apart. Just keep that in mind! If after enough iterations you still don’t find a point, you can select a random rectangle and generate a random point inside that rectangle as a fallback. If you want to be more sophisticated, you can weigh the rectangles based on their area.

[Xan_TheDragon (Xan)]

I had a solution in mind.

What you could do is, since your rectangles seem to be grid aligned, use a range on X and Y to generate your points (random between each of the four corners, or basically a random within the rectangle).

What you should do is, for every point generated, use a test of that point’s position to see if it’s inside of another rectangle.

You should then, if the amount of rectangles that contain that point is >1, do another random chance which is 1/n where n is the amount of rectangles. Here it is visualized for you:

For checking collision you should keep it simple: For every rectangle, make the following check:

function PointCollidesIn(a, b, point)
	-- a is the top left corner of the rectangle as a Vector2
	-- b is the lower right corner of the rectangle as a Vector2
	-- point is your point as a Vector2
	if (point.X >= a.X and point.X <= b.X) and (point.Y >= a.Y and point.Y <= b.Y) then
		-- The parenthesis are not necessary, it's just something that helps organize the operands.
		return true
	end
	return false
end


local pointCollisions = 0
for _, rectanglePart in pairs(someArrayOfRectangles) do
	-- Assume you've already formatted the args to conform to the requirements of PointCollidesIn
	-- Also assume you've created a "point" variable that is a point within one of your rectangles. How you select which rectangle the point is generated in is on you to decide.
	if PointCollidesIn(a, b, point) then
		pointCollisions = pointCollisions + 1
	end
end

if math.random() < 1/pointCollisions then
	-- Place the point
else
	-- Scrap the point
end

Something along these lines should (ideally) make you the right result. I’m not very good with working with complex shapes like this so there may be a better, much faster way. I’m afraid I’m unable to present such a solution, however.

[People_InTHE20s]

How would you then merge it altogether?