1
$\begingroup$

I'm trying to figure this out on my own so no direct answers please - I really am looking for pointers on different ways to approach this problem.

Given some dimensions, a point A, a point B, and a maximum distance, calculate how many possible paths exist from A to B where the distance between A and B is less than or equal to the max distance. If a path intersects a "wall" it will reflect at the angle of incidence. If a path intersects a "corner" it will reflect back the way it came.

For example:

If you have a plane with dimensions 2x3, with point A at $(1,1)$ and point B at $(2,1)$ and a max distance of 4, there are 7 vectors that lead from A to B (with total path length less than or equal to max distance) either directly or by reflecting off a "wall". Examples of some of the $7$ answer vectors are $(0,1), (1,2),(1,-2),(-3,-2)$ which I have diagrammed on the sketch below. The problem is that I don't have any of this vector information, I only have the dimensions, point A and B, and the max distance - all of which are variable depending on the input.

enter image description here

Any pointers or thoughts on how to approach this problem would be appreciated.

Thanks

$\endgroup$
5
  • $\begingroup$ An often useful way to approach such problems is to “unfold” the path by creating multiple reflections of the target points and reflecting surfaces. The possible paths then become straight lines that are much easier to work with and analyze. $\endgroup$ Commented May 29, 2018 at 18:00
  • $\begingroup$ @amd thank you - I have experimented with unfolding, but I haven't been able to find information on determining the number of paths using that method. My dimensions can range at or below 1250 x 1250 units so, while the unfolding definitely helps visualize, at this point I'm unsure of how to apply it. Do you know if counting the various paths in an efficient manner can be achieved with unfolding? $\endgroup$ Commented May 29, 2018 at 18:02
  • $\begingroup$ Each image of the target point (and the point itself, of course) that lies within a circle with radius equal to the max distance corresponds to a path. You basically just need to find an efficient way to generate the reflections without repetition. $\endgroup$ Commented May 29, 2018 at 18:09
  • $\begingroup$ @amd thanks, although the question remains: how to find the paths. In my example above the max distance is 4 which is larger than the dimensions of the plane. But we know that not all paths lead from A to B in under 4 units, even though they are within the radius. Unless I am misunderstanding your comment. $\endgroup$ Commented May 29, 2018 at 18:10
  • $\begingroup$ so you spoke their language and got the challenge... are you one of them now @SynchronizeYourDogma $\endgroup$ Commented Sep 2, 2018 at 4:54

1 Answer 1

Reset to default
1
$\begingroup$

To expand a bit on the suggestion in my comment, you can “unfold” the paths by repeated reflections of the target point $B$ and the reflectors themselves. Each image of $B$ and, of course, $B$ itself, that lies within the maximum distance corresponds to a unique path from $A$ to $B$.

enter image description here

The trick, then, is to efficiently generate these images of $B$, but that seems fairly straightforward to do since the reflecting surfaces parallel the coordinate axes. If the right edge of the box is the line $x=w$, then the $x$-coordinate of the first reflection is $w+(w-x_B)$, the second is $2w+x_B$, the third $3w+(w-x_B)$ and so on. In general, the even-numbered reflections are spaced $2w$ apart, as are the odd-numbered reflections. This pattern holds going to the left as well. The same pattern occurs for the reflections in the top and bottom walls, except that the spacing between reflections with the same parity is $2h$, where $h$ is the height of the box. A pair of nested loops seem like they’d do the trick here.

If you need to trace any of the paths, draw a straight line from $A$ to the corresponding image of $B$. Each time this line crosses one of the grid lines in the above diagram (which are the reflections of the sides of the box), the actual path will change direction.

enter image description here

(Sorry about the near-illegible labels. Text doesn’t appear to survive GeoGebra’s graphics export process any more.)

$\endgroup$
6
  • $\begingroup$ Thank you for this. I will digest it and comment back with any questions. $\endgroup$ Commented May 29, 2018 at 18:45
  • 1
    $\begingroup$ Synchronize: Suppose $A = (0, 1)$ is the midpoint of the left edge, and $B = (1.5, 1)$ is the midpoint of the box. Then there's path of length 1/2 directly from $A$ to $B$, but there's also a path from $A$ to $C = (3, 1)$ and back to $B$. Do you allow this second path, or do your paths have to hit $B$ for the first time at their terminal points? If it's the latter, then in the "star" of rays from $A$ to all the replicates of $B$ in @amd's nice diagram, you have to ignore rays that contain other rays entirely. If it's the former, then amd's answer is spot on. $\endgroup$ Commented May 29, 2018 at 18:52
  • $\begingroup$ @JohnHughes Good point. That’ll require a bit of bookkeeping or a different way to generate the reflections that avoids the “masked” points. $\endgroup$ Commented May 29, 2018 at 18:59
  • $\begingroup$ @JohnHughes The first time the path hits B is a terminal point, which is exactly what I was looking for. While 9 points are within the radius above, the answer I am looking for is actually 7 because of what you have pointed out. This is really great feedback. Thank you $\endgroup$ Commented May 29, 2018 at 19:10
  • $\begingroup$ @SynchronizeYourDogma I count 8 paths in the example from your question. There might be some things you can do up front to avoid overgenerating candidate points if all of the coordinates are integers, but otherwise nothing particularly clever immediately comes to mind. If I do think of something, I’ll update my answer accordingly. Each distinct path corresponds to a different initial direction, so you could collect that information as you go along and use it to eliminate masked paths. $\endgroup$ Commented May 29, 2018 at 21:59

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.