# 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.

## 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():
'''
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):
'''
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):
'''
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.