Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Find a path from point A to point B while avoiding obstacles
Replies: 15   Last Post: Nov 4, 2010 10:36 PM

 Messages: [ Previous | Next ]
 Alan Posts: 151 Registered: 7/24/09
Re: Find a path from point A to point B while avoiding obstacles
Posted: Nov 4, 2010 11:16 AM

"Modestas Sekreckis" <modestas.sekreckis@gmail.com> wrote in message <iau50s\$btr\$1@fred.mathworks.com>...
> "Modestas Sekreckis" <modestas.sekreckis@gmail.com> wrote in message <iapfr4\$luv\$1@fred.mathworks.com>...
> > I have two points in 3D space (A and B) and some sort of obstacle between them, I need to find a path to avoid colliding with an obstacle.
> > Does anybody have an idea of how I might do this using a smart approach instead of just manually doing it?
> > Thanks in advance.

> I try to make it easier to get the job done 2D plane. How to find the point C (x, y). The system is shown in the picture. http://img502.imageshack.us/img502/193/51082985.jpg

If you know you want a two-line-segment path, that is entirely outside the convex hull of the shape, then here is a simple, but not optimal, approach to try:

1. Choose one plane on which your intermediate point will lie. For simplicity, choose the plane perpendicular to line AB, and passing through the centroid of the obstacle.
2. Find the perspective projection of the obstacle onto the plane, with respect to both point A, and point B. These projections represent regions on the plane where the intermediate point can NOT be.
3. Look at the union of these two regions, and find the point on the perimeter closest to the centroid of the obstacle. This is your intermediate point.

Even for convex objects, this will be much longer than the shortest path, in the cases where one or both of the points is relatively close to the obstacle. If you don't care about the path length, the above should suffice. You could also replace the object with a pre-determined, appropriately sized sphere, to simplify the calculations further. Or use a PCA box if the shape is very irregular.

If you need a shorter path length, but don't need it to be optimal, then you can try doing the same thing, but with two planes - both still be perpendicular to line AB, but one passes through the point on the obstacle closest to point A, and one through the point closest to point B. You'll need two intermediate points, which means you'll need to check many combinations of points between the two projection regions, but it seems to me that one of those combinations will get you a fairly short path, though not optimal in general.

Date Subject Author
11/2/10 Modestas Sekreckis
11/2/10 Sean
11/2/10 Walter Roberson
11/2/10 Alan
11/2/10 Walter Roberson
11/2/10 Mopps The Geek
11/4/10 ImageAnalyst
11/4/10 ImageAnalyst
11/2/10 Jan Simon
11/2/10 Walter Roberson
11/4/10 Jan Simon
11/4/10 Steven Lord
11/4/10 Modestas Sekreckis
11/4/10 Alan
11/4/10 Walter Roberson
11/4/10 Walter Roberson