2

I'm working on a way to determine if given point is "inside" given ellipse, the problem is I've already forgotten all the related mathematics and don't have time to relearn it and find a way to do it.

The problem:

There is a rectangular plane of given width of $a$ and height of $b$, there is an ellipse with center $C[c_1,c_2]$ (which is located in one of the corners) and point $X[x_1,x_2]$ in one of the corners. The $a$ and $b$ are also lengths of major and minor axis of the ellipse.

I need to figure out a simple way to programmatically check whether the point is in or out of the ellipse. This is going to be done for a lot of points (for example a plane of 6000 x 5000 or 20000 x 40000) and i need to check whether all of the points are inside the ellipse or not and give them corresponding value (array of Boolean values, false = outside, true = inside ).

I need to do the same for triangle.

The way I think now I could just check the triangle given by the three corners of the plane that the ellipse does not use as it's center to cut the number of points to half (the other half is inside the ellipse for sure).

What I need is an easy (fast) way to check whether the point is inside the ellipse or not.

P.S.: I'm not that proficient in English when it comes to mathematics, so if you can think about right tags I would appreciate a comment.

Larry B.
  • 3,384
mishan
  • 123

1 Answers1

3

Let $F_1$ and $F_2$ be the foci of the ellipse, and $2a$ be the length of the major axis. If $PF_1+PF_2 > 2a$, then $P$ is outside the ellipse; if $PF_1+PF_2=2a$, then $P$ is on the boundary of the ellipse; otherwise, $P$ is inside the ellipse.

Here it is a way to find the foci (red points) of an ellipse given its vertices: enter image description here

Jack D'Aurizio
  • 353,855
  • 1
    This helps a lot :) Can you also please add a way to find focal points from the given ellipse? – mishan Sep 07 '14 at 22:54
  • 1
    The foci are on the major axis, they are symmetric with respect to the center $O$ of the ellipse and $OF_1=\sqrt{a^2-b^2}$ holds, where $a$ and $b$ are half of the lengths of the axis. – Jack D'Aurizio Sep 07 '14 at 22:57
  • 1
    Heh, sorry for disturbing. I remembered about the existence of google as i pressed send comment :) – mishan Sep 07 '14 at 22:58
  • No problem for me, I also added a "visual proof" for finding the foci. – Jack D'Aurizio Sep 07 '14 at 23:04
  • @mashan If you want to use this to draw an ellipse i fear this approach will be too slow. – Ward Beullens Sep 07 '14 at 23:14
  • @WardBeullens oh, I will post my question to stack overflow then and ask about faster methods – mishan Sep 07 '14 at 23:16
  • In general you want to avoid using square roots and decimals for the best performance. There exists such algoritms for drawing a circle, they can probably be adapted for drawing ellipses.

    http://en.wikipedia.org/wiki/Midpoint_circle_algorithm#Variant_with_Integer-Based_Arithmetic

     – Ward Beullens Sep 07 '14 at 23:21
  • $\sqrt{x}+\sqrt{y}\geq z$ is equivalent to $4xy \geq (z^2-(x+y))^2$, one does not need to compute square roots. – Jack D'Aurizio Sep 07 '14 at 23:24