Generate random (x, y) within an area

• Given a rectangular on a 2D coordinate, write a function to return (x, y) pair so that the distribution of the return value is uniform within the rectangular.

Followup 1: What if you are given multiple non-overlapping rectangular areas? How to generate uniformly distributed (x, y) pair?

Followup 2: What if you are given an arbitrary shaped area?

• In general, to uniformly randomly select a (x,y) from inside a rectangle, you can independently sample the x coordinate and the y coordinate. Note that the rectangle might not be aligned along the axes (i.e. could be at an angle), but one can always find linear transformations to transform the rectangle so that its axes are parallel to the X and Y axes.

Followup 1: If you know the areas of the rectangles, you can first randomly chose one of the rectangle (where the probability of choosing a rectangle is proportional to its area) and then use the previous function to randomly choose a point from within that rectangle.

Followup 2: How is the shape information provided to us ? Do we know the area ?

• I didn't have any time left for followup 2.
But I would assume the input is similar to previous 2 questions - you are given a list of vertices (could be of any number and could form any shape).
Any ideas?

• @hellowworld Ok, just hand-waving ideas. You can always find the minimal rectangle(or circle that) covers the shape given and then randomly sample from that rectangle (or circle) and discard points that are not lying inside the shape. The caveat with this method is that it might be time consuming since you will have to reject a few samples (which like outside the shape).

Circle might be easier since you can easily find the centroid of the given vertices of your shape and then use that to sample your random points. To sample points from a circle randomly you can use their parametric form. Randomly generate R and \theta and then map them to the circle using R cos \theta and R sin \theta

• @Santy-8128 Thanks for sharing your thought. But how can we check if a point is within an arbitrary shape?

• @hellowworld You would need to create a separate function for that. Idea given here:
https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/

• @Santy-8128 Thanks a lot

• @hellowworld It seems you were asked many statistics and geometric questions in your interview loop, is that because of the role you applied for?

I am going for an onsite next week for a general SWE developer role and I have not prepared for such advanced math problems like that =)

• A random idea for 2:
Any poligon is a collection of triangles. You can calculate their sum, use the trick with areas from (1) and adjust the function to find a random number from inside a triangle.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.