0
$\begingroup$

The title is pretty self explanatory - I trying to implement an algorithm that determines whether a point lies on the edge of an ellipse, given a nontrivial edge thickness.

Reference this question to see the motivation:

The ellipse is defined by the diagonal line through the bounding rectangle, where $(x_1, y_1)$ is the top left corner of the bounding rectangle, and $(x_2, y_2)$ is the bottom right corner of the bounding rectangle.

See this diagram made with my mad MS Paint skills:

Mad paint skillz

I have an existing algorithm at my disposal to determine whether a point is inside an ellipse, so one thought I had was to create two new ellipses, slightly larger and slightly smaller, and determine if the point lies in one but not the other. I think this would work, but I would have to work out where to position the new ellipses to ensure that they are centered on top of each other.

I'm wondering if that is the simplest approach, or if there is some simpler closed form solution.

Note that the thickness extends in either direction from the center of the edge, both to the inside of the ellipse and to the outside equally.

An acceptable solution could be an algorithm that determines the distance to the nearest edge (meaning the centerline of the edge) of the ellipse in terms of the given variables; calculating the rest would be trivial then I think.

$\endgroup$
  • 1
    $\begingroup$ The two-ellipse method is the easiest one, but it is not very accurate because thickness would not be constant. $\endgroup$ – Aretino Nov 5 '17 at 9:52
  • $\begingroup$ From the algorithm you have, you should be able to find from its residue its normal/minimum distance of a given point to the ellipse. (btw the inner ellipse not an ellipse strictly). $\endgroup$ – Narasimham Nov 5 '17 at 18:55
1
$\begingroup$

To do an accurate job you should:

  1. Find the equation of the ellipse without thickness.

  2. Find the distance between the point to be tested and that ellipse.

  3. If the thickness is $2\delta$, check that the distance computed above is $\le\delta$.

The hard part is 2. because the distance must be computed numerically: see here for some methods.

If you can tolerate some tiny inaccuracy you can resort to the method you outlined. The equation of the ellipse without thickness is: $${(x-x_C)^2\over a^2}+{(y-y_C)^2\over b^2}=1$$ where $x_C=(x_1+x_2)/2$, $y_C=(y_1+y_2)/2$, $a=|x_2-x_1|/2$ and $b=|y_2-y_1|/2$.

If the thickness is $2\delta$, then the equations of the inner and outer ellipse are: $$ {(x-x_C)^2\over(a-\delta)^2}+{(y-y_C)^2\over(b-\delta)^2}=1 \quad\hbox{and}\quad {(x-x_C)^2\over(a+\delta)^2}+{(y-y_C)^2\over(b+\delta)^2}=1. $$ It is easy to check if a point $P$ is inside or outside one of those ellipses: just plug the coordinates of $P$ into the equation and check if the left-hand sides evaluate to more or less than $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.