Changing the Ray Algorithm

The original Ray Algorithm is described on the pictures below:

            

As you can see from the presented material, this algorithm cannot be applied to the Diagram Editor. The changed one is described below:

The program takes the first and the last points of line, which have to be optimized. The direction of the line is to be towards the final point, by the X coordinate if the line has been originally drawn from the left to the right or from the right to the left. If the line has been drawn from up to down or from down to up, the direction of the line goes by the Y coordinate.

The program checks whether there is an obstacle on the way from starting point to the final one comparing the coordinates of the given points with all the obstacles. This approach saves CPU time by doing only one comparison instead of running through all the points of the drawing space. 

If there is an obstacle on the way from starting to the final point the line divides into two separate lines with the fixed indent and continues comparison with the remained blocks.

The program works recursively and the similar recursive function is called for the next axis when the final point is not reached yet.

Technical specification of the program for JavaScript implementation:

The program creates an array of “Way” objects, which keeps an id and the coordinates of the calculated (with no intersection) point. The id-s are given to each point in order to find the shortest way back to the start point. The picture of the processed algorithm is presented below with all the actual ids.

As, you can see on the picture, to generate the shortest way back from the last point to the starting point, you can easily find the ID of the next line point, by deleting the last digit of the ID if it ends with 0, or change the last digit from 1 or 2 into 0, if it does not end with 0 digit. The distance from one point to another is calculated during calculating the optimal line. The method used in implementation of calculating and comparison of the shortest path allows to save some memory space, because it uses only 2 arrays for line comparison, during the process of comparing all the possible lines.

The picture above shows that mainly two functions are called for calculating the shortest way. This functions (for checking x and checking y axis) work interchangeably while the final point is not reached yet. This process continues recursively while reaching the final point.

The lines, drawn in Diagram Editor, while not having any visual difference, can differ from each other when they are drawn from different sides. That is the original style designed by Lycos programmers. However, this implementation identifies the type of the line and deals with it as appropriate.

The next technical issue, which is worth to mention is the appropriate sorting of the barriers for further checking. All the barriers are being kept and sorted in an array dynamically, when there is a need to call one of the recursive functions. For example when there is a need for running checking function along the X axis, the blocks are sorted by the X axis, and vice versa for the Y axis. This sorting is necessary for checking the intersections with the barriers efficiently. You can see the sorted blocks in the picture presented below. Notice that the sequence of barriers is not changed in the XML (DOM) document. Only the identical numbers are assigned to each of the barrier.

Another advantage is the ease of changing the indent of the line from the block point. So, if the developer wants to increase the indent of the line, he just needs to change the constant value in the upper part of the program.

The picture presented above describes the work of algorithm when the lines are drawn from right to left.