The general idea
We are located at a point that is initially (X,Y), we move towards a direction vector (dx,dy). This movement will generate a straight line. This line will touch a mirror and then the ray of light bounces or gets destroyed. Whenever a light bounces, we update (dx,dy) and (X,y) accordingly. The process finishes when the ray of light touches the original point, gets destroyed or when its total length exceeds D.
From here on we got to clarify some things.
Light movement towards a direction vector?
The direction vector (dx,dy) means that for every dx units moved in the horizontal axis, we move dy units in the vertical axis or vice versa. When the starting point of the trajectory is (X,Y). Let us rush to mention that (X,Y) and (dx,dy) together form a straight line. However, note that the direction means that only the positive side of the straight line matters to us, so (dx,dy) not only specify the direction but also the sense of it ... The equation of the straight line is either (y = Y + (x - X)*dy/dx) or (x = X + (y - Y)*dx/dy) (We used the point-slope form).
Light strikes a mirror
Given a mirror, any mirror, imagine it as a square that is surrounded by segments. The segments are what is important. Basically, the effect of bouncing happens when the line from the equation above intersects a side of a mirror. The good thing about our mirrors is that all of their sides are parallel to either the x or y axis. If we have a horizontal segment that goes from coordinates (x=s.x, s.y) to (x= s.x, s.y1) then the segment's line equation is simply (x = s.x). To find the intersection between the segment and the line from the direction is as easy as replacing x=7 in the first equation. If there is a solution to this equation, we will find a value of y such that the segment's line and the line cross at that point. But of course, we also want the intersection to be inside the segment, this just requires our value of y to be inside [s.y0 , s.y1]. After we confirm the segment intersection, we also need to verify that the point lies towards the correct sense as given by (dx,dy).
There are many special cases all specified by the problem statement. For starters, we should not usually consider the intersection if it is touching the very corner of a mirror. Unless the corner is actually adjacent to another mirror (and thus the sides of the mirrors act as a single segment). There is also the two special cases when the corner either destroys the light ray or makes it bounce completely.
There are many ways to deal with these issues, I will do one that is a little odd but does the job. First of all, consider that mirror segments can come from many different mirrors that stand together but also have an empty space in the appropriate side:
A maximal sequence of # characters in the input that are adjacent and have empty spaces (.) above forms a horizontal segment. Likewise, a maximal sequence that has an empty space (.) bellow forms another kind of horizontal segment. Vertical segments are a similar story. One main idea behind this transformation is that I wanted the logic to simply ignore all intersections between the direction and an end point of a mirror segment, so we need multiple mirrors to form larger segments to avoid light getting lost when it should not. The other idea is to reduce the overall amount of segments, this is a good idea to improve execution speed.
Note how this does not generate any segment for the outer area, that is good because light will never bounce there.
We will ignore intersections with the border of a segment. This introduces a new problem, and it is that sometimes we do need to detect when a ray of light hits a corner. There are two cases: a) The light bounces on a corner (because the mirrors make a concave corner) and b) The light gets destroyed because the light hit a convex corner.
Magic points and evil squares
I happen to use such silly, graphical language to stuff involved in a problem, because it somehow makes it clearer to my brain. The idea is that a magic point is a corner that allows bouncing. When this corner gets hit by the ray of light, it will be returned to the opposite direction. In order to detect this event, you would need to calculate the intersection between the line equation and a single point (If the point is contained by the line equation and in the correct side). Do not worry about precision, since we at the end want to detect if the ray of light hits the starting point, we will need to do this kind of line-point intersection accurately anyway.
Magical points are simply those points that are adjacent to three mirror squares (#) and an empty square (.) so that they form an L-like shape. They are the corners at which light could bounce in some situations. Evil squares are those squares that could destroy light, they possess corners that are surrounded by 3 empty spaces in a similar L-shape. In the image, magical points are green and evil squares are red:
Detecting when an evil square "destroys" the light is tricky. But it is all about the ray of light not only touching one of its corners (Take a look at the image, one of the evil squares has a corner that is also a magical point). (In the statement, there is also a case in which a ray goes though the corners of two squares adjacent diagonally) . It has to be one of the convex corners. A good way to detect this is if the direction line touches a corner AND also intersects the square itself. The square is made of 4 segments so you can detect an intersection against those segments easily.
There is a catch and it is that the evil square's edges may coincide with the mirror's segments. My suggestion is to consider squares that are slightly smaller (subtract an Epsilon from each dimension). Also, note that hitting the corner is necessary, a square will not destroy light if it does not hit a corner (light will bounce),
In the image, note how both crossing a corner of the square and intersecting with the smaller square are necessary conditions to destroy the light. In practice, the square will be smaller but only slightly smaller, just a distance to separate it from the mirror segments but ensuring that every light that is supposed to be destroyed can still intersect with the evil square.
The movement algorithm
So let us say we have extracted the starting position, the segments, the magic points and the evil squares from the input. Then we kindly multiplied everything by 2 so that all the relevant coordinates are integer. The next step is to just simulate the light trajectory for each (dx,dy) pair. Thus solve this problem:
- The current position is (X,Y).
- The current direction vector is (dx,dy)
- Light has already traveled usedD distance units.
- Does the current direction take us to a) The starting location. b) A mirror's segment. c) A magic point. d) An evil square or e) The remaining distance (D - usedD) is too short and thus the trajectory ends before doing anything else.
- If the light does hit something, the position (X,Y) gets updated to the point at which the something got hit and when there is reflexion, (dx,dy) have to be updated, how to update it? (used D increases by the distance between original (X,Y) and the new value).
Reflection: Try it in some paper, you shall see that bouncing against a horizontal mirror means multiplying dy by -1. A vertical mirror means multiplying by -1 and a magical point multiplying both dx and dy, by -1.
What object gets hit first?: We now how to know if the light intersects one of the objects or not. But there are usually going to be many objects and of different types. Let us say we have a list of all the intersections between the line that starts at (X,Y) and uses the direction vector (dx,dy), there are going to be many of them, we will call each of these intersections an event. The actual object that will be hit is the object that is closest to (X,Y), so let us pick the event with the minimum distance. When we pick the event with the minimum distance, we move to a new (X,Y) and we update usedD and (dx,dy).
There is a literal corner case that is related to evil squares. The location of the intersection with an evil square is the corner (cx,cy). But if we do things recklessly, this corner could also be a magical point. The solution is to either only check against the relevant (convex) corners of the square or you can also check against all corners, but add priorities to the events, so if two events are at the same distance from (X,Y), you can use the kind of event as a tie breaker and give less priority to evil squares.
In the image, you will see a couple of different thins that can happen moving from (X,Y). The direction line intersects with the segment that is even going through (X,Y), but this should not be the first event - The only way for this to happen is if it actually was the previous event - We should ignore any event within 0 units of distance to avoid any infinite loop of picking the same location all the time - . The next closest event is the corner of an evil square, but it does not count - Since the line is not going through the square's edges, there is no intersection to it. Next closest event is a magical point, this is the closest valid event, so the result is to pick this event. There are two remaining events which both are valid but since the magical point happens before them, we have to ignore them - There is an intersection with an evil square, and this one is valid because it crosses the square and touches the intersection - {Even though this intersection is valid, it should not be. Luckily, when this happens there should always be another event at a lower distance when this issue of hitting the square at the wrong corner.
No comments :
Post a Comment