The Ellipse Problem

Last time, I’d introduced Monte Carlo Method and its application to solve the Snake Problem. Today I will use the same method in a different application, find the overlap area of two ellipses.

Get code


Idea

An ellipse is an extension of a circle. By definition, “A circle is the locus of all points equidistant from a central point“. It could be addressed mathematically like “\quad\left| PO \right| =r\quad“, where P is a point, O is the central point, and r is the radius. On the other side, an ellipse, by definition, is a curve in a plane surrounding two focal points such that the sum of the distances to the two focal points is constant for every point on the curve. It is addressed mathematically like \quad\left| PF_{1} \right| +\left| PF_{2} \right| =2a\quad.

Given that formula, we could use Monte Carlo Method to count success/total simulation and get the probability that a point fall on both ellipse planes. Once we have that, we could get the overlap area by multiplying the probability by the frame area.

 


Structure Chart

To solve this problem, we first have to create an ellipse class to hold ellipse properties.


class ellipse():
    '''
    About:
        This is a class represent a ellipse.
    Args:
        f1 (object): An point object
        f2 (object): An point object
        a (float): The length of semi-major axis
    '''
    ...

After we got two ellipses, we pass these ellipses to simulate_many. In simulate_many, it does three things. First it call the function “frame” to get the frame area.


def frame(e1,e2):
    '''
    About:
        To construct a frame based on two given ellipses
    Args:
        e1 (ellipse): an ellipse obejct
        e2 (ellipse): an ellipse obejct
    return:
        tuple: the horizontal range
        tuple: the vertical range
        float: the frame area
    '''
    ...

Second, it iteratively call simulate_once to get every simulation result.


def simulate_once(e1,e2,h,v):
    '''
    About:
        To test whether a random point (within the range) fall on the overlap area
    Args:
        e1 (ellipse): an ellipse obejct
        e2 (ellipse): an ellipse obejct
        h (tuple): the horizontal range
        v (tuple): the vertical range
    return:
        boolean: whether a random point fall on the overlap area
    '''
    ...

Third, it calculates the probability that a point falls on the overlap area, multiplies it by the frame area, and return the overlap area.


def simulate_many(n,e1,e2):

    ## get horizontal_range, vertical_range, frame_area
    h ,v, area = frame(e1,e2)

    ## init the success count and total count
    success = 0
    total = 0
    ## n times simulation
    for i in range(n):
        ## recording the success and total count
        success += simulate_once(e1,e2,h,v)
        total += 1

    ## get probability
    p = success/total
    return p*area

 


Test Cases

At the end, I provide 4 test cases to validate the simulations.