• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

shortest path in a polygon space

toughwimp11

toughwimp11

Senior member
Suppose you have a 2-d space with (non-intersecting) convex polygons in it and you're trying to get from one vertex on a polygon to another vertex on some other (or potentially the same) polygon without going through any polygon. Why does the shortest path between any two vertices only consist of straight segments connecting vertices? I have to explain this for a math problem and although it makes sense, i'm really having a hard time putting it into words so help would be appreciated.
 
Draw a of a picture of a simple example, It will help with your explanation.
I would draw it myself but I'm lazy. 😛
 
Seems to me, at least the way you've phrased it, is just an extension of the idea that the shortest distance between two points is a straight line. If you have an obstructing polygon that you are not allowed to bisect, you are now looking at making the shortest distance between your original starting point and the polygon, then the shortest distance along the polygon, then the shortest distance between that point and your endpoint. Since the line segments between vertices represent the shortest path between the points on the interfering polygon, traveling between those would represent the shortest path around the obstruction.
 
Atomic Playboy said:
Seems to me, at least the way you've phrased it, is just an extension of the idea that the shortest distance between two points is a straight line. If you have an obstructing polygon that you are not allowed to bisect, you are now looking at making the shortest distance between your original starting point and the polygon, then the shortest distance along the polygon, then the shortest distance between that point and your endpoint. Since the line segments between vertices represent the shortest path between the points on the interfering polygon, traveling between those would represent the shortest path around the obstruction.
Click to expand...
You are basically describing my thought process every time I walk to/from work on a miserable day (cold, hot, rainy, etc).

1) The shortest distance is a straight line from where you are at to the end point.
2) If that path is blocked, then you have to go around the obstacle.
3) It should be obvious that the shortest distance is NOT a wide path around the obstacle but instead a path that just grazes the outside of that obstacle.
4) If I were in fact infinitely narrow, the shortest walking path would put me exactly on at least one corner of that obstacle (a vertex of the polygon).
5) Go back to #1.

I can't count the number of times I've thought this out while walking, hoping to come up with a shorter path. It inevitably leads to me thinking about building/programing a robot to run a maze.
 
dullard said:
You are basically describing my thought process every time I walk to/from work on a miserable day (cold, hot, rainy, etc).

1) The shortest distance is a straight line from where you are at to the end point.
2) If that path is blocked, then you have to go around the obstacle.
3) It should be obvious that the shortest distance is NOT a wide path around the obstacle but instead a path that just grazes the outside of that obstacle.
4) If I were in fact infinitely narrow, the shortest walking path would put me exactly on at least one corner of that obstacle (a vertex of the polygon).
5) Go back to #1.

I can't count the number of times I've thought this out while walking, hoping to come up with a shorter path. It inevitably leads to me thinking about building/programing a robot to run a maze.
Click to expand...

I just had an image of you walking directly into people, sidling along them until you've cleared them, then continuing on your route. I think I'm going to try that...
 
Atomic Playboy said:
I just had an image of you walking directly into people, sidling along them until you've cleared them, then continuing on your route. I think I'm going to try that...
Click to expand...
That is where the interesting part comes along. Movable obstacles. Or obstacles that you didn't know about (e.g. a water puddle). There must be a long term goal (the next fixed object's vertex) and a short term goal (the vertex of the item you just got new information about).

Oh and be careful doing what you are planning near me. We might have a head-on collision as we both try to occupy the same vertex at the same instant.
 
dullard said:
3) It should be obvious that the shortest distance is NOT a wide path around the obstacle but instead a path that just grazes the outside of that obstacle.
Click to expand...

While this is probably true, a rigorous proof probably need to do better than starting with "It should be obvious..."
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top