How to know two lines are a pare parallel lines

[lovecreatesbeauty]

For example, line L1 and line L2 are two lines in two-dimensional
space, the start-points and end-points can be described with following
the `point_t' type. The start-points and end-points are: Line L1
(L1_str, L1_end), L2 (L2_str, L2_end).

Can I compare the float value of sloping rate of two lines to determine
whether they are parallel lines? Some paper books tell that float value
can not be compared to float value. Some people also try to convince
others on this point that do not perform the comparing on float values.
Then how can I complete the task of determining whether two lines are
parallel lines by their sloping rate?

/* type for points */
typedef struct
{
double x;
double y;
} point_t;

/* calculate the value of sloping rate of a line */
double slope(point_t pt_start, point_t pt_end);

double sl_L1 = slope (L1_str, L1_end);
double s2_L2 = slope (L2_str, L2_end);

if (s1_L1 == s2_L2) /* CAUTION: compare float data to float, is it ok?
*/
{
/* L1 and L2 are parallel lines */
}
else
{
/* L1 and L2 are not parallel lines */
}

 

[Martin Ambuhl]

For example, line L1 and line L2 are two lines in two-dimensional
space, the start-points and end-points can be described with following
the `point_t' type. The start-points and end-points are: Line L1
(L1_str, L1_end), L2 (L2_str, L2_end).

Can I compare the float value of sloping rate of two lines to determine
whether they are parallel lines? Some paper books tell that float value
can not be compared to float value. Some people also try to convince
others on this point that do not perform the comparing on float values.
Then how can I complete the task of determining whether two lines are
parallel lines by their sloping rate?

You simply need to determine how close to numerical equality the slopes
need to be to count as parallel. This will tell whether, within the
constraints of your measurements and arithmetic precision, you can tell
whether the lines are not parallel. You can never tell that they are
actually parallel when any of the values involved are not expressible
exactly as floating point values. Notice that if your points are
expressible in integral or even rational terms, then you may be able to
avoid floating point representations entirely.

 

[osmium]

For example, line L1 and line L2 are two lines in two-dimensional
space, the start-points and end-points can be described with following
the `point_t' type. The start-points and end-points are: Line L1
(L1_str, L1_end), L2 (L2_str, L2_end).

Can I compare the float value of sloping rate of two lines to determine
whether they are parallel lines? Some paper books tell that float value
can not be compared to float value. Some people also try to convince
others on this point that do not perform the comparing on float values.
Then how can I complete the task of determining whether two lines are
parallel lines by their sloping rate?

<snip>

It is common to compare two floating point numbers to see whether they are
within a "guard band" of one another. An elementary way would be to create
a constant such as this:

const double epsilon = 1.0e-06;

And then see if two numbers are equal + or - one epsilon. For more advanced
usage you could actually compute epsilon so it had some relationship to the
problem you are solving. For example, if you are dealing with the distance
to Pluto and the distance is in centimeters, epsilon might be bigger.

 

[Walter Roberson]

For example, line L1 and line L2 are two lines in two-dimensional
space, the start-points and end-points can be described with following
the `point_t' type. The start-points and end-points are: Line L1
(L1_str, L1_end), L2 (L2_str, L2_end).

Can I compare the float value of sloping rate of two lines to determine
whether they are parallel lines? Some paper books tell that float value
can not be compared to float value. Some people also try to convince
others on this point that do not perform the comparing on float values.
Then how can I complete the task of determining whether two lines are
parallel lines by their sloping rate?

The question implicitly assumes that you need to distinguish the
"very-nearly" parallel lines from the "exactly" parallel lines.
That in turn assumes that the coordinates you have been given
are exact coordinates.

As your coordinates are being paseed in as double, you should instead
be assuming that the coordinates are not precise. You then cannot
calculate the exact slope: you can only calculate a range of slopes
for each of the pairs, and then attempt to determine whether the two
ranges overlap. That comparision in turn might have to be inexact.

In short, I would suggest that you do not try to determine whether
the lines are "exactly" parallel, and instead write your code to
determine whether they are parallel to within a tolerance.
You will find even this to be a challenge to get right in the case
where the coordinate differences are either very small or very large.

 

[Keith Thompson]

The question implicitly assumes that you need to distinguish the
"very-nearly" parallel lines from the "exactly" parallel lines.
That in turn assumes that the coordinates you have been given
are exact coordinates.

As your coordinates are being paseed in as double, you should instead
be assuming that the coordinates are not precise. You then cannot
calculate the exact slope: you can only calculate a range of slopes
for each of the pairs, and then attempt to determine whether the two
ranges overlap. That comparision in turn might have to be inexact.

In short, I would suggest that you do not try to determine whether
the lines are "exactly" parallel, and instead write your code to
determine whether they are parallel to within a tolerance.
You will find even this to be a challenge to get right in the case
where the coordinate differences are either very small or very large.

Right. Checking whether the slopes are exactly equal is relatively
easy, but doesn't work if the input data is inexact (as it almost
inevitably will be). Checking whether the slopes are nearly equal is
tempting, but it breaks down in some cases; for example, two lines
might both be nearly vertical, and therefore nearly parallel to each
other, but have slopes of -1.0e6 and +1.0e6.

Mathematically, I think the best approach is to compute the *angle*
between the lines; if the angle is close to 0, the lines are nearly
parallel. You also need to decide what "nearly" means; determining
whether a small difference in angle comes from roundoff error or
indicates that the lines really aren't parallel is probably the
toughest part of the problem.

comp.graphics.algorithms might be a good place for this kind of thing.
(I base that purely on the name of the newsgroup; browse it and/or
read its FAQ before posting.)

 

[Andrew Poelstra]

Right. Checking whether the slopes are exactly equal is relatively
easy, but doesn't work if the input data is inexact (as it almost
inevitably will be). Checking whether the slopes are nearly equal is
tempting, but it breaks down in some cases; for example, two lines
might both be nearly vertical, and therefore nearly parallel to each
other, but have slopes of -1.0e6 and +1.0e6.

Is that 6 supposed to be negative?

Mathematically, I think the best approach is to compute the *angle*
between the lines; if the angle is close to 0, the lines are nearly
parallel. You also need to decide what "nearly" means; determining
whether a small difference in angle comes from roundoff error or
indicates that the lines really aren't parallel is probably the
toughest part of the problem.

You could simply store rise/run as two distinct integers (or floats, I
guess), and compare those. In the case of integers you will get an exact
match.

Of course, then you have problems with lowest terms; how do you tell if
(6/3) and (2/1) are the same?

 

[Keith Thompson]

Is that 6 supposed to be negative?

No.

A line with a very large positive slope is nearly vertical. A line
with a very large negative slope is also nearly vertical.

A line with a slop of -1.0e-6 or +1.0e-6 would be nearly horizontal;
that doesn't illustrate the point I was making because those two
slopes are numerically close to each other. With slopes of very large
magnitude, you can have nearly parallel lines whose slopes differ
greatly.

On the other hand, if you're really interested in whether the lines
have similar slopes, you can ignore this. It all depends on what the
actual requirements are, and what they're based on.

You could simply store rise/run as two distinct integers (or floats, I
guess), and compare those. In the case of integers you will get an
exact match.

Of course, then you have problems with lowest terms; how do you tell
if (6/3) and (2/1) are the same?

Reducing integer fractions to lowest terms isn't difficult; Euclid
knew how to do it.

If you can get your raw data in a form that's not subject to rounding
errors (multi-precision rationals, for example), you don't have to
worry about approximate results; you can determine whether the lines
are exactly parallel or not. The details depend strongly on the input
data format. Without knowing anything about that, there aren't really
any C issues.

 

[Old Wolf]

Is that 6 supposed to be negative?

No. Consider a line that's almost vertical but not quite (eg.
the side of that tall pointy thing near the white house).
Say its "rise" is 100m and its "run" is 10mm. So its slope is
10000. Then consider a nearby line whose rise is 1000m and
run is 10.01mm. Its slope is 9990. This difference is 10, which
is much larger than our tolerance of 1e-6 so the lines should
not be considered parallel.

But consider the same structure lying on its side. Now the
first line has "rise" 10mm and "run" 100m so its slope is
0.0001. The second line's slope is 0.0001001. The difference
is 0.0000001 which is within our tolerance, so the lines are
now parallel!

Hence the suggestion to consider the angles of the lines,
rather than their slope, ie. arctan(rise/run)

You could simply store rise/run as two distinct integers (or floats, I
guess), and compare those. In the case of integers you will get an
exact match.

Most floats are not exact.

Of course, then you have problems with lowest terms; how do you
tell if (6/3) and (2/1) are the same?

a/b == c/d iff ad == bc.

If you can't multiply due to problems with integer overflow,
then test (a/c).d == b and (a/c).c == a.

 

[Rouben Rostamian]

For example, line L1 and line L2 are two lines in two-dimensional
space, the start-points and end-points can be described with following
the `point_t' type. The start-points and end-points are: Line L1
(L1_str, L1_end), L2 (L2_str, L2_end).

Can I compare the float value of sloping rate of two lines to determine
whether they are parallel lines?

Comparing floating point values is problematic.
Comparing slopes to check for parallelism is even more problematic.
Slope is undefined for lines parallel to the y axis (the axis of
ordinates.)

Here is the proper way to check for parallelism.

Suppose line 1 goes through points A=(a1,a2), B=(b1,b2), and A != B.
Suppose line 2 goes through points C=(c1,c2), D=(d1,d2), and C != D.

Then the lines are parallel if and only if

(b1 - a1) * (d2 - c2) - (b2 - a2) * (d1 - c1) = 0.

This involves no divisions and works for arbitrary lines, including
those that are parallel to the y axis.

 

[Walter Roberson]

Here is the proper way to check for parallelism.

Suppose line 1 goes through points A=(a1,a2), B=(b1,b2), and A != B.
Suppose line 2 goes through points C=(c1,c2), D=(d1,d2), and C != D.

The OP's data structure showed the coordinates to be stored as doubles.
What is the "proper way" to test that A != B or C != D for
pairs of doubles? cf. a recent thread that explored that even
if you had b = a; if (a = b) that you could not be sure
the test would succeed.

Then the lines are parallel if and only if

(b1 - a1) * (d2 - c2) - (b2 - a2) * (d1 - c1) = 0.

This involves no divisions and works for arbitrary lines, including
those that are parallel to the y axis.

Yes, it involves no divisions, but on the other hand it involves
2 multiplications and 4 subtractions -- which not only results
in precision problems, but also leads to the possibility of
arithmetic overflow (e.g., let a1 and c2 be small and b1 and d2 be
very large...)

If you had
b1 = -a1; b2 = -a2; d1 = -c1; d2 = -c2;
then as you changed the signs of all of the components, the two should
have exactly the same slope. Have a look, though, at what the formula
would calculate:

(-a1 - a1) * (-c2 - c2) - (-a2 - a2) *(-c1 - c1)

Evalulated symbolically, that would be

4 * a1 * c2 - 4 * a2 * c1

but in practice it's going to be:

(-2 * a1 + e1) * (-2 * c2 + e2) - (-2 * a2 + e3) * (-2 * c1 + e4)

which differs by

2 * (a2 * e4 + c1 * e3) - 2 * (a1 * e2 + c2 * e1) + e1 * e2 - e3 * e4


Suppose we get really close -- suppose only one of the epsilons (e1)
is 1e-15 and the others are 0. The difference would then be
- 1/500000000000000 * c2 and if c2 were (say) 5e18 then the
difference term would be -10000 which is clearly non-negligable.


When you are doing your numerical analysis, keep in mind that
(-a + -b) is not necessarily going to be the same as (- (a + b))
because rounding can be different for negative and positive
quantities. The rounding scheme that attempts to avoid that is
"round to even" -- but if you "round to even" then if you are
given a particular double P then instead of knowing that the
original value was (P +/- epsilon), you now have to deal with
the original value potentially being (P +/- (2 * epsilon)),
which will change your analysis...

 

[Old Wolf]

Here is the proper way to check for parallelism.

Suppose line 1 goes through points A=(a1,a2), B=(b1,b2), and A != B.
Suppose line 2 goes through points C=(c1,c2), D=(d1,d2), and C != D.

Then the lines are parallel if and only if

(b1 - a1) * (d2 - c2) - (b2 - a2) * (d1 - c1) = 0.

This involves no divisions and works for arbitrary lines, including
those that are parallel to the y axis.

See my other post on this thread. This equation is algebraically
equivalent to subtracting the gradients.

In the case of integer coordinates, this equation runs the
risk of integer overflow. I gave a version that instead uses
division and avoid overflow.

In the case of floating point coordinates, all quantities are
imprecise, so you cannot perform some computation and
check if it equals zero. You must check if it is less than
some small epsilon value. The gradient subtraction has
the problem that an appropriate epsilon also depends on
the gradients themself, eg. lines with angle 89.990 and
89.991 have a gradient diffference of 1086 (this is the
value that your above expression would give), whereas
lines with angle 0.010 and 0.009 have a gradient
difference of .0000165 .

 

[Old Wolf]

a/b == c/d iff ad == bc.

If you can't multiply due to problems with integer overflow,
then test (a/c).d == b and (a/c).c == a.

Note that before doing this test you should reduce the
fractions to their lowest terms.