CODEWITHSUNDEEP
pythonmathregion
valentino8
valentino8

Reputation: 1

How to generate points in the regions bounded by intersecting circles, and how to define these unique regions?

I am trying to divide a plane (10x10) into areas using circles with different centres and radii. The lines created by the circles intersect and create many smaller bounded regions. What I want to end up with is a descripition of the different regions and for all these regions I want to generate a point (does not matter where in the region) inside of it. So for instance I could have five circles that divide the plane into 15 regions, how do i describe these regions while only having the information of the circles (centres and radii) and also obtain 15 points that are all inside different regions.

I have thought of a possible way to define the regions by saying for all the circles if it is inside or outside the circle. Say I have three circles I would have the following: Region1 is inside circle 1, inside circle 2 and outside circle 3. Then I could generate random points and see if they satisfy the definition of the region. However I think this is computationally quite expensive and am curious if there is a better more efficient way.

Upvotes: 0

Views: 126

Answers (1)

Alverciito
Alverciito

Reputation: 13

I just figured out a fast algorithm to provide a fast solution. I understand that the metric that defines a point inside a circle is a euclidean distance in 2d.

import numpy as np
def euclidean_distance(center, point):
     dist = np.sqrt((center.x - point.x) ** 2 + (center.y - point.y) ** 2)
     return float(dist)

Then, you must compute all the distances to the centers. You probably can not optimize this step, because you need to evaluate the if the point is inside the regions.

# my_centers is already defined, a list of points.
# my_rad is already defined, a list of floats with the radius.
def get_region(point):
    region_code = list()
    for cent, rad in zip(my_centers, my_rad):
        dist = euclidean_distance(cent, point)
        is_inside = 1 if dist <= rad else 0
        region_code.append(is_inside)
    return region_code

Then, you have a region_code with a one-hot encode. This means that, for each circle, you have 1 or 0 indicating if it is inside of it or not. If you do not like this type of encoding you can compute the binary value of the one-hot code as:

def one_hot_2_number(code):
    number = 0
    for index, value in enumerate(code):
        number += value * (2 ** index)
    return number

With the new encoding you have a number between 0 and the number of possible regions. Note that some regions may not exist if some circles do not intersect.

At this point, your regions are already defined for your favorite encoding. You can create a mesh grid with the desired affinity if you want to define the regions point by point. Just use numpy.

We define class Point just to pack the access to x and y. Then we create a mesh grid in numpy and generate all the possibilities in the defined bounds. The bounds are defined as x_min, x_max and y_min and y_max. The number of points indicate the affinity of your grid.

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def define_regions(x_points: int, y_points: int, min_x, max_x, min_y, max_y):
    x = np.linspace(min_x, max_x, x_points)
    y = np.linspace(min_y, max_y, y_points)
    points_and_regions = list()
    for x_point, y_point in np.meshgrid(x, y):
        point = Point(x_point, y_point)
        region = one_hot_2_number(get_region(point))
        points_and_regions.append((x_point, y_point, region))
    return points_and_regions

This function ends up giving a list of x and y points and the region number of your grid without generating random numbers.

I hope it helped.

Upvotes: 0

Related Questions