How to know two lines are a pare parallel lines

Discussion in 'C Programming' started by lovecreatesbeauty, Apr 27, 2006.

  1. 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
    lovecreatesbeauty, Apr 27, 2006
    #1
    1. Advertising

  2. 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.
    Martin Ambuhl, Apr 27, 2006
    #2
    1. Advertising

  3. lovecreatesbeauty

    osmium Guest

    "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?


    <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.
    osmium, Apr 27, 2006
    #3
  4. In article <>,
    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?


    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
    Walter Roberson, Apr 27, 2006
    #4
  5. -cnrc.gc.ca (Walter Roberson) writes:
    > In article <>,
    > 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?

    >
    > 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) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Apr 27, 2006
    #5
  6. 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 <http://www.wpsoftware.net/blog>
    Every prime number in a series as a joke
    Made all the patterns clear when I took that final toke
    Andrew Poelstra, Apr 27, 2006
    #6
  7. 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) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Apr 27, 2006
    #7
  8. lovecreatesbeauty

    Old Wolf Guest

    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.
    Old Wolf, Apr 27, 2006
    #8
  9. In article <>,
    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?


    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
    Rouben Rostamian, Apr 28, 2006
    #9
  10. In article <e2rieu$ogd$>,
    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, 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...
    --
    There are some ideas so wrong that only a very intelligent person
    could believe in them. -- George Orwell
    Walter Roberson, Apr 28, 2006
    #10
  11. lovecreatesbeauty

    Old Wolf Guest

    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 .
    Old Wolf, Apr 28, 2006
    #11
  12. lovecreatesbeauty

    Old Wolf Guest

    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.
    Old Wolf, Apr 28, 2006
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Soren
    Replies:
    4
    Views:
    1,228
    c d saunter
    Feb 14, 2008
  2. Vivek Menon
    Replies:
    5
    Views:
    3,307
    Paul Uiterlinden
    Jun 8, 2011
  3. Vivek Menon
    Replies:
    0
    Views:
    1,744
    Vivek Menon
    Jun 10, 2011
  4. Andries

    I know, I know, I don't know

    Andries, Apr 23, 2004, in forum: Perl Misc
    Replies:
    3
    Views:
    208
    Gregory Toomey
    Apr 23, 2004
  5. PerlFAQ Server
    Replies:
    0
    Views:
    153
    PerlFAQ Server
    Jan 14, 2011
Loading...

Share This Page