computed by substituting using the above calculations and equating the results:
y1 = (C1 - A1x1) / B1
y2 = (C2 - A2x2) / B2
(C1 - A1x1) / B1 = (C2 - A2x2) / B2
If x1 == x2, we get
(C1 - A1x) / B1 = (C2 - A2x) / B2
x = (C1B2 - C2B1) / (A1B2 - A2B1)
Even if A1, B1, C1, A2, B2, and C2 are all integers, this involves a floating point division, which is expensive. Not only that, but the slope of a vertical line is infinite, so some special case handling is necessary anyway.
In computer graphics and integrated circuit design, lines often have a slope of +1 or -1 (45 degrees up or down). Here the y coordinate changes by one unit up or down for every unit that the x coordinate changes. We can take advantage of this to convert the floating point division to an integer addition or subtraction.
Similar logic applies when one of the two lines is vertical or horizontal: the x or y coordinate of the intersection is fixed, so only the second coordinate must be computed using the slope of the non-orthogonal line (which is often stored anyway, since it is used so often).
Finally, no calculations are needed if both lines are orthogonal; the appropriate x or y coordinate can simply be used directly.
Thus considerable computational cost can be avoided by considering all of the special cases for lines in the problem domain. More lines of code are required, and the instructions necessary to select the additional special cases have some cost, but on low-power hardware these optimizations are always worthwhile, and they usually provide some savings even on workstation-class machines.
Finding Common Patterns in Your Code
The optimizations for computational geometry are well-known, and someone writing plane geometry code now would probably implement the speedups from the start. If your problem domain is new or less well-defined, you will have to develop your own patterns.
For me, pattern matching has been of most benefit when I am trying to reduce runtime, so most of this discussion will focus there. Similar logic will apply when you have a computation that requires a large amount of memory: look at the parameters of the computation to see whether some memory use can be avoided for that problem instance.
Once you have found some of the patterns that appear most often, look at the code which is to be executed. Make a copy of it, select a common pattern, and start simplifying the copy based on what you know about the parameters in this pattern. Some calculations will simply disappear; others will require much less code because the relationships between parameters will now be known. Conditional logic will become much simpler as well. When you know that a condition is true or false, you no longer need to test for it. The code becomes more of a straight execution line, allowing you to simplify and combine even more.
Invoke the new function by adding code which tests for the common pattern in the original function. Do this for several common patterns, until you run out of good patterns or the original function begins to get cluttered.
Test each of the new code blocks to ensure they still perform the same function as the original, generalized code. Often you can do this by running the new code at the same time as the original - run the optimized version, then the general version, and compare results on the fly. These test runs will obviously be slower than the original, but you need to continue following the rule "make it right before making it faster."
Once you have some of the most common cases coded, tested, and integrated, stop invoking the generalized calculations and see how much improvement you get. You might find that you get no improvement whatsoever! This can happen when the specialized code is not much shorter than the generalized code, or when the code needed to select the specialized case has a high cost relative to the general calculation.
Sometimes the overhead of calling special-case routines can be high enough to notice, in which case you can bring the special-case code back into the original routine. This requires caution, because larg