Vultr DocsLatest Content

Generate Random Point in a Circle

Updated on 30 May, 2025
Generate Random Point in a Circle header image

Problem Statement

The problem requires you to design and implement a class named Solution with functionalities to manage and generate random points inside a circle. This circle is defined by a given radius and the coordinates of its center. The class should instantiate using the constructor Solution(double radius, double x_center, double y_center) where:

  • radius is the radius of the circle.
  • x_center and y_center establish the coordinates of the circle's center.

Another critical function in this class, randPoint(), must generate and return a random point within the bounds of the circle, including its circumference. The function should output the coordinates of this random point as an array [x, y].

This simulates a real-world scenario where random placement of items inside a circular area is needed, ensuring each point lies within the circle's boundary.

Examples

Example 1

Input:

["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]

Output:

[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation:

Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // returns a random point like [-0.02493, -0.38077]
solution.randPoint(); // another random point like [0.82314, 0.38945]
solution.randPoint(); // another random point like [0.36572, 0.17248]

Constraints

  • 0 < radius <= 10^8
  • -10^7 <= x_center, y_center <= 10^7
  • At most 3 * 10^4 calls will be made to randPoint

Approach and Intuition

The task is to select a random point inside a given circle uniformly. This involves understanding both the math of a circle and ensuring uniform randomness:

  1. A circle in a plane is defined by its center (x_center, y_center) and radius r. A point (x, y) is inside the circle if (x - x_center)^2 + (y - y_center)^2 <= r^2.

  2. Simply generating random x and y within a square around the circle leads to non-uniform distribution, as points cluster near the center.

  3. To ensure uniform distribution:

    • Generate a random angle θ from [0, 2π].

    • Generate a random radius r from [0, radius], but use r = sqrt(random()) * radius to correct for area bias.

    • Convert polar coordinates to Cartesian:

      • x = r * cos(θ)
      • y = r * sin(θ)

    • Shift the point by the center coordinates:

      • x += x_center
      • y += y_center

Using this method ensures that the random points are evenly distributed across the entire area of the circle, including the edge. This strategy is mathematically sound and computationally efficient.

Solutions

  • C++
  • Java
cpp 
class RandomPointGenerator {
public:
    double radius, xCenter, yCenter;
    mt19937 rngEngine{random_device{}()};
    uniform_real_distribution<double> distribution{0, 1};

    RandomPointGenerator(double r, double x, double y) {
        radius = r, xCenter = x, yCenter = y;
    }

    vector<double> generate() {
        double distance = radius * sqrt(distribution(rngEngine));
        double angle = distribution(rngEngine) * (2 * M_PI);
        return {distance * cos(angle) + xCenter, distance * sin(angle) + yCenter};
    }
};

Generate a random point within a given circle using the provided C++ class RandomPointGenerator. This solution uses polar coordinates to ensure a uniform distribution of points within the circle. Here's how you can leverage the provided code to achieve this:

  • Initialize the RandomPointGenerator with the circle's radius and the coordinates of its center. This setup involves passing these values through the constructor when creating an instance of the class.

  • Utilize generate() method to produce a random point within the circle. This method calculates a point by:

    • Generating a random distance from the center, which is adjusted with the square root of a uniformly distributed random number to maintain the uniformity of point distribution within the circle.
    • Generating a random angle to represent the direction in which to place the point from the center.

  • The method will then calculate the x and y coordinates of the point using the formulas for conversion from polar to Cartesian coordinates:

    • x = distance * cos(angle) + xCenter
    • y = distance * sin(angle) + yCenter

  • These coordinates are then returned as a vector of doubles.

Use this class by creating an object with the appropriate circle details and call generate as needed to get new, random points within the specified circle. This implementation ensures that all points are evenly distributed within the circle, and it relies on C++'s random number generation utilities.

java 
class RandomPointGenerator {
    double radius, xCenter, yCenter;
    public RandomPointGenerator(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.xCenter = x_center;
        this.yCenter = y_center;
    }

    public double[] generatePoint() {
        double distance = radius * Math.sqrt(Math.random());
        double angle = Math.random() * 2 * Math.PI;
        return new double[]{distance * Math.cos(angle) + xCenter, distance * Math.sin(angle) + yCenter};
    }
}

The problem involves generating a random point within a circle defined by its radius and center coordinates. The Java solution utilizes a class, RandomPointGenerator, which includes methods to both initialize the circle and generate the random points.

Key components of this Java solution include:

  • Class Variables: radius, xCenter, and yCenter to store the circle's characteristics.
  • Constructor RandomPointGenerator(double radius, double x_center, double y_center): Initializes an object with the circle's radius and center coordinates.
  • Method generatePoint(): Generates a random point within the circle.

To generate a point:

  1. Calculate the distance from the center. The distance is the product of the circle's radius and the square root of a random number between 0 and 1. This approach ensures uniform distribution of points within the circle.
  2. Calculating the angle for the point involves multiplying a random number by 2 * Math.PI to cover all possible directions (360 degrees).
  3. Compute the coordinates (x, y) using the trigonometric functions Math.cos and Math.sin for the angle and multiply by the computed distance to scale it to the correct radius. Add xCenter and yCenter to translate the point to the circle's actual location on a plane.

The generatePoint() method returns an array of doubles representing the x and y coordinates of the random point. This method can be called any number of times to generate multiple points within the specified circle.

Comments

No comments yet.