reflection paths between points in2d

Question

Just wondering if there was a nice (already implemented/documented) algorithm to do the following
boo! http://img697.imageshack.us/img697/7444/sdfhbsf.jpg
Given any shape (without crossing edges) and two points inside that shape, compute all the paths between the two points such that all reflections are perfect reflections. The path lengths should be limited to a certain length otherwise there are infinite solutions. I'm not interested in just shooting out rays to try to guess how close I can get, I'm interested in algorithms that can do it perfectly. Search based, not guess/improvement based.

Answer 1

I think you can do better than computing fans. Call your points A and B. You want to find paths of reflections from A to B.

Start off by reflecting A in an edge, and call the reflection A1. Can you draw a line from A1 to B that only hits that edge? If yes, that means you have a path from A to B that reflects on the edge. Do this for all the edges and you'll get all the single reflection paths that exist. It should be easy to construct these paths using the properties of reflections. Along the way, you need to check that the paths are legal, i.e. they do not cross other edges.

You can continue to find paths consisting of two reflections by reflecting all the first generation reflections of A in all the edges, and checking to see whether a line can be drawn from those points through the reflecting edge to B. Keep on doing this search until the distance of the reflected points from B exceeds a threshold.

I hope this makes sense. It should be easier than chasing fans and dealing with their breakups, even though you're still going to have to do some work.

By the way, this is a corner of a well studied field of billiards on tables of various geometries. Of course, a billiard ball bounces off the side of a table the same way light bounces off a mirror, so this is just another way of thinking of reflections. You can delve into this with search terms like polygonal billiards unfolding illumination, although the mathematicians tend to dwell on finding cases where there are no pool shots between two points on a polygonal table, as opposed to directly solving the problem you've posed.