458,110 Members | 1,541 Online Need help? Post your question and get tips & solutions from a community of 458,110 IT Pros & Developers. It's quick & easy.

# How to know two lines are a pare parallel lines

 P: n/a 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 */ } -- Sincerely, lovecreatesbeauty Apr 27 '06 #1
11 Replies

 P: n/a lovecreatesbeauty wrote: 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. Apr 27 '06 #2

 P: n/a "lovecreatesbeauty" writes: 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? 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. Apr 27 '06 #3

 P: n/a In article <11**********************@t31g2000cwb.googlegroups .com>, lovecreatesbeauty wrote:For example, line L1 and line L2 are two lines in two-dimensionalspace, the start-points and end-points can be described with followingthe `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 determinewhether they are parallel lines? Some paper books tell that float valuecan not be compared to float value. Some people also try to convinceothers on this point that do not perform the comparing on float values.Then how can I complete the task of determining whether two lines areparallel 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. -- I was very young in those days, but I was also rather dim. -- Christopher Priest Apr 27 '06 #4

 P: n/a ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) writes: In article <11**********************@t31g2000cwb.googlegroups .com>, lovecreatesbeauty wrote:For example, line L1 and line L2 are two lines in two-dimensionalspace, the start-points and end-points can be described with followingthe `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 determinewhether they are parallel lines? Some paper books tell that float valuecan not be compared to float value. Some people also try to convinceothers on this point that do not perform the comparing on float values.Then how can I complete the task of determining whether two lines areparallel 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. 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.) -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Apr 27 '06 #5

 P: n/a Keith Thompson wrote: 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? -- Andrew Poelstra Every prime number in a series as a joke Made all the patterns clear when I took that final toke Apr 27 '06 #6

 P: n/a Andrew Poelstra writes: Keith Thompson wrote: 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? 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. 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? 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. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Apr 27 '06 #7

 P: n/a Andrew Poelstra wrote: Keith Thompson wrote: 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? 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. Apr 27 '06 #8

 P: n/a In article <11**********************@t31g2000cwb.googlegroups .com>, lovecreatesbeauty wrote:For example, line L1 and line L2 are two lines in two-dimensionalspace, the start-points and end-points can be described with followingthe `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 determinewhether 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. -- Rouben Rostamian Apr 27 '06 #9

 P: n/a In article , Rouben Rostamian wrote: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, includingthose 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... -- There are some ideas so wrong that only a very intelligent person could believe in them. -- George Orwell Apr 28 '06 #10

 P: n/a Rouben Rostamian wrote: 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 . Apr 28 '06 #11

 P: n/a Old Wolf wrote: Andrew Poelstra wrote: 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. Note that before doing this test you should reduce the fractions to their lowest terms. Apr 28 '06 #12

### This discussion thread is closed

Replies have been disabled for this discussion. 