The given algorithm:

1. Take two lines and find the intersection point P (precise up to 14 or 15 digits).
2. Calculate the distances from P to the remaining two lines.
3. If both distances are below E (10^-10), then the four lines are said to be intersecting.

The algorithm's assymetry:

From a given example, the algorithm was shown to give different results (intersecting or nonintersecting) depending on which two lines were chosen first (for finding P). Why does this happen? We will attempt to show by geometric example.

Basically, the problem arises from the inconsistency of the valid intersecting region formed from the remaining two lines given different relative orientations. This region is the area in which the point P must lie in order to be close enough to both lines to be considered intersecting. As shown in the figures below, we can graphically show the valid region for a single line by increasing the line's width about its center +/-E (so the line's width is 2E). If P lies on this thick line then it's distance must be less than E (ok, it could be EQUAL to E, but this will still illustrate the point). The intersection of the two thick lines will form the valid intersecting region where a point P in this area will be within distance E of both lines.

The main problem with this inconsistency is that the maximum allowable error from the true intersection point (at the center of the dark regions) increases as the lines become more parallel to each other. Given this, there is no way for there to be symmetry in this algorithm. First of all, the point P is considered to be calculated quite precisely (up to 14 or 15 digits), but the intersection test between P and the remaining lines can be considered intersecting as long as it lies anywhere in the valid intersecting region; however, this region changes based on how parallel those lines are to each other!

Consider the following sets of four lines. The two blue lines have the same intersection point in both images, and so do the red and green lines; however, in the left image they would not be considered to intersection, but in the right image they would NOT because the intersection points moved, but because of the orientation of the red and green lines!

Breaking the assymetry

There are several ways we can modify the algorithm so that it will give the same results regardless of the order of processing the lines. We will suggest only one (without using the distance-from-pt-to-line test):

• Compute all pairwise intersections of lines (6 of them): 1-2,1-3,1-4,2-3,2-4,3-4
• Compute all pairwise distances between the intersections (15 of them).
• If all distances are less then E (a positive epsilon), then the lines are considered intersecting.

It may be possible to simplify this algorithm significantly. Perhaps we need only find the following intersection points: between 1 and 2, 2 and 3, and 3 and 4. If these three points are within distance E of each other, then they intersect.

Or perhaps we can do it with only two intersection calculations and one distance test: find intersection between 1 and 2 and between 3 and 4; if these points are within distance E of each other, they intersect.