The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » Software » comp.soft-sys.matlab

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

"Modestas Sekreckis" <> wrote in message <iau50s$btr$>...
> "Modestas Sekreckis" <> wrote in message <iapfr4$luv$>...
> > 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.

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.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.