Just wondering if there was a nice (already implemented/documented) algorithm to do the following
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.
views:
75answers:
4
A:
I do not know of any existing solutions for such a problem. Good luck to you if you find one, but incase you don't the first step to a complete but exponential (with regard to the line count) would be to break it into two parts:
Given an ordered subset of walls A,B,C and points P1, P2, calculate if a route is possible (either no solutions or a single unique solution).
Then generate permutations of your walls until you exceed whatever limit you had in mind.
The first part can be solved by a simple set of equations to find the necessary angles for each ray bounce. Then checking each line against existing lines for collisions would tell you if the path is possible.
The parameters to the system of equations would be
angle_1 = normal of line A with P1
angle_2 = normal of line B with intersection of line A
angle_3 = normal of line C with ...
angle_n = normal of line N-1 with P2
Each parameter is bounded by the constraints to hit the next line, which may not be linear (I have not checked). If they are not then you would probably have to pick suitable numerical non-linear solvers.
Akusete
2010-04-20 00:55:46
A:
Think not in terms of rays but fans. A fan would be all the rays emanating from one point and hitting a wall. You can then check if the fan contains the second point and if it does you can determine which ray hits it. Once a fan hits a wall, you can compute the reflected fan by transposing it's origin onto the outside of the wall - by doing this all fans are basically triangle shaped. There are some complications when a fan partially hits a wall and has to be broken into pieces to continue. Anyway, this tree of reflected fans can be traversed breadth first or depth first since you're limiting the total distance.
You may also want to look into radiosity methods, which is probably similar to what I've just described, but is usually done in 3d.
phkahler
2010-04-20 01:27:19
yeah. That's pretty much what I'm doing. It's pretty tedious code.
Chris H
2010-04-20 01:51:56
How does wall/wall rays work. Would they be trapezoids?
Akusete
2010-04-20 01:59:12
@Akusete - reflected fans can be represented as truncated triangles - chopped off into 4 sided figures... well 3 sided since the far wall is not known until you check for intersections and splits.
phkahler
2010-04-20 13:17:36
+3
A:
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.
brainjam
2010-04-20 03:44:55
At first this seemed simple, but once you reflect the A point, you've expanded the room and when this is repeated it seems like you may create reflected copies of the room that overlap the original. Some good book keeping might take care of that I suppose.
phkahler
2010-04-21 00:53:14
Agreed, this is not as easy as it may first sound. You're right, in a sense the whole room reflect along with the point. But I believe you can ignore that, and just look at whether there is a straight line from the reflected point to `B` that goes through the reflecting edge. If so, you reconstruct the path of reflections from `A` to `B`. But that path may cross other edges of the room, in which case you reject it. You might have caught that earlier if you had reflected the entire room, but as you say that could involve a lot of bookkeeping.
brainjam
2010-04-21 01:50:58
A:
In response to brainjam
You still need wedges....
In this situation, how would you know not to do the second reflection? How do you know what walls make sense to reflect over?
Chris H
2010-04-21 04:21:53
For any generation of reflected point, consider the edge you reflected it through, and see whether you can draw a line to the sink that only crosses that edge. The edges corresponding to I and II are the bottom right and bottom left - call them E and EE. You cannot draw a line from I to sink that crosses E, same for II and EE. So they are not candidates.But, to answer your question, there's not any way to determine whether it makes sense to reflect over a wall or not - you just have to try it, as far as I can tell. (continued next comment)
brainjam
2010-04-21 04:44:23
(continued from last comment) On the other hand, if you reflect across the right wall and then across the top wall, you succeed - but you don't know until the second reflection. Again, you stop reflecting when the path, even if successful, would be too long. But otherwise you just follow the search tree.
brainjam
2010-04-21 04:44:39
Yep, to check M walls for N reflections you'd have to check M^N "rooms". If you use the fans/wedges, you only traverse parts of the reflection tree that are actually possible, so (kM)^N where k is some average fraction of walls struck by a fan.
phkahler
2010-04-21 20:03:27