Distance to an ellipse surface

[Trenthan]

Hey guys, this isn't a course work question more independent study to improve something I'm working on for my course, to increase computation time.

It may be in the wrong thread but the others state to post independent study in the homework section so its here. Placed it in maths since its seems most relevant but please feel free to move this thread if its in the wrong place!

Bit of background first
-I'm currently producing a path planning algorithm using potential flows to guide a non-holonomic robot through a field of obstacles.
-To model multiple obstacles we use a weighting function that determines which object is dodged first, and is dependent on the DISTANCE to the SURFACE of THAT OBSTACLE from our robots position in the field.

Now everything works fine, and i can produce smooth trajectories around multiple obstacles in a large field.

Issue is calculating the distance to the surface of an elliptical obstacle and plates (lets ignore plates for now).

This is currently done by generating the coordinates of the ellipse surface, and by searching for the smallest distance between the surface coordinate and robot position. Right away you can see this is inefficient and slow!

It works in real time since its generated step by step while the robot moves, but for simulation purposes its too slow. If it takes the robot in reality 20seconds to trace the path, its takes 20 seconds to generate the simulation for a fake environment of the computer. (if its 2 minutes, than its 2 minutes as well). This makes it difficult when coding and playing around with ideas since i loose a lot of time sitting around waiting to see the result. This section of the code takes up 95% of the computation time so if it can be reduced, it would be a big plus!

I'm curious to know if there is a neat mathematical equation, or some geometric techniques that can easily allow me to find the shortest distance to an ellipse from a point in space**. (If it could be done with the ellipse at any orientation (45, 217 degrees etc) it would be better, but i can easily address this with other algorithms currently implemented).

Im happy to be pointed in the correct direction, I've hunted IEEE, gone through my old course work and nothing on this type of stuff. Searched the web without much luck; more a lot of junk that isn't too useful.

Cheers Trent

 

[micromass]

Hi Trenthan!

Let's get you on the way. The general equation for an ellipse is

$$\left\{\begin{array}{c} x=x_c+a\cos(t)\cos(\varphi)-b\sin(t)\sin(\varphi)\\ y=y_c+a\cos(t)\sin(\varphi)+b\sin(t)\cos(\varphi)\\ \end{array}\right.$$

where $(x_c,y_c)$ is the origin of the ellipse, where a and b describe the length of the major and minor axis and where $\varphi$ is the anlge of the major axis with the x-axis.

Let $(x_0,y_0)$ be the point in space. Your job is now to minimize

$$\sqrt{(x_c+a\cos(t)\cos(\varphi)-b\sin(t)\sin(\varphi)-x_0)^2 + (y_c+a\cos(t)\sin(\varphi)+b\sin(t)\cos(\varphi)-y_0)^2}$$

with respect to t. I.e. you need to find the t that makes the above expression minimal. OF course, the square root can be dropped, so you need to find the t that minimizes

$$(x_c+a\cos(t)\cos(\varphi)-b\sin(t)\sin(\varphi)-x_0)^2 + (y_c+a\cos(t)\sin(\varphi)+b\sin(t)\cos(\varphi)-y_0)^2$$

To do this, calculate the derivative of this expression and see when it equals 0. You may want to use a computer algebra system for that like wolfram alpha...