Line Segment Class Implementation - Dealing With Infinity!

This is a discussion on Line Segment Class Implementation - Dealing With Infinity! within the Game Programming forums, part of the General Programming Boards category; I can't really wrap my brain around infinity. But more importantly, my program can't either. I have this line segment ...

  1. #1
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465

    Line Segment Class Implementation - Dealing With Infinity!

    I can't really wrap my brain around infinity. But more importantly, my program can't either. I have this line segment class that just goes something like this:

    Code:
        class CLineSegment
        {
    
        public:
    
            CLineSegment( const CPoint & start, const CPoint & end );
            CLineSegment( double tx, double ty, double rx, double ry );
            ~CLineSegment( void );
    
            void setStart( const CPoint & start );
            void setEnd( const CPoint & end );
    
            const CPoint & getStart( void ) const;
            const CPoint & getEnd( void ) const;
    
            bool intersects( const CLineSegment & other );
            bool operator == ( const CLineSegment & other );
    
        private:
    
            CPoint m_start, m_end;
            double m_slope;
    
        };
    You can probably already see the problem. Yep. Slope. Vertical lines. Blowin' my programs mind. Indeterminate -1.#IND00. The thing is, I kind of need to know the slope, because I kinda determined these equations to figure out the points of intersections.

    Code:
    y - ya = ma * ( x - xa )
    y - yb = mb * ( x - xb )
    
    x = ( yb - ya - mb * xb + ma * xa ) / ( ma - mb )
    y = ( mb * ya - mb * yb + ma * mb * ( xb - xa ) ) / ( mb - ma )
    Of course, I dealt with the special cases of things being paralell and being the same to avoid divide by 0's in these equations, but I can't think of a way to test for the verticals. Is it bad to leave that indeterminate form in? Can I check for it or something and then make a special case?

    ╔╗╔╦══╦╗╔╦══╦╗
    ║╚╝║╔╗║╚╝║╔╗║║
    ║╔╗║╠╣║╔╗║╠╣╠╣
    ╚╝╚╩╝╚╩╝╚╩╝╚╩╝

    codez http://code.google.com/p/zxcvbn/

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,424
    maybe you should change the line equation to
    a*x+b*y = 1
    and see what formulas you get in this case... maybe you will have less special cases
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  3. #3
    Registered User
    Join Date
    Dec 2006
    Posts
    30
    Quote Originally Posted by vart
    maybe you should change the line equation to
    a*x+b*y = 1
    then you couldn't represent lines that go through the origin (since a*0+b*0 != 1)

  4. #4
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    I think I could use the general form ax + by + c = 0

    ╔╗╔╦══╦╗╔╦══╦╗
    ║╚╝║╔╗║╚╝║╔╗║║
    ║╔╗║╠╣║╔╗║╠╣╠╣
    ╚╝╚╩╝╚╩╝╚╩╝╚╩╝

    codez http://code.google.com/p/zxcvbn/

  5. #5
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,584
    Fortunately you know when the slope is going to be zero so you can check for this condition and return 0 instead of attempting to calculate it.

    Same holds true for things like arccosine and other functions that have exceptions to the rule or that have certain limits.

    To further illustrate:

    The formula for the gravitational attraction between two objects is:

    Attraction=G(mass1)(mass2)/(dist^2)

    Where G=6.67 * 10^-11 (N/m^2).

    So when the distance between two objects is zero this formula completely fails....or does it? Can you realistically have two objects at zero distance and if so would not the attraction between them be zero since they would both occupy the same space at the same point in time? This formula when used in a game context could be checked to ensure that if distance=0 then the result is most certainly 0. What the formula is really saying is that the results are undefined which is true since to get the result you would have to break a fundemental law of physics.
    Last edited by VirtualAce; 12-15-2006 at 01:18 AM.

  6. #6
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    >> Fortunately you know when the slope is going to be zero so you can check for this condition and return 0 instead of attempting to calculate it.

    Well, yes, but unfortunently I can't just return zero (unfortunently). I will create situations where things will have a vertical slope (unfortunently), and I still need to deal with them (unfortunently). And I don't know about the general equation of a line thing. I mean, I can't just take two points on the grid and just come up with that form magically. It actually ends up that the slope sticks around.

    Code:
    y - ya = ma * (x - xa)
    y - ma * x - ya - ma * xa = 0;
    
    ax = - ma * x
    by = y
    c = - ya - ma * xa
    I'd assume I'd get similar results solving for a and b of the equation ax + by = 1
    Last edited by Tonto; 12-15-2006 at 01:27 AM.

    ╔╗╔╦══╦╗╔╦══╦╗
    ║╚╝║╔╗║╚╝║╔╗║║
    ║╔╗║╠╣║╔╗║╠╣╠╣
    ╚╝╚╩╝╚╩╝╚╩╝╚╩╝

    codez http://code.google.com/p/zxcvbn/

  7. #7
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    Why not just treat vertical lines as a special case? Before doing your normal equations, check for any vertical lines. (And be sure to check for parallels!) I might not rely on m_slope here - I think indeterminate can perserve sign, so you might just write a bool IsVertical() function (do the two x coordinates equal each other?)

    Once you know that only _one_ line is vertical, then your intersection x is the x coordinate of both of the line's points, and your intersection y is the y value of the non-vertical line at that the intersection x. Something like:
    Code:
    int CLineSegment::GetIntersection(CLineSegment &l2, CPoint &result)
    {
       // Parallel tests...
       if(IsVertical() && l2.IsVertical()) return 1; // Parallel, or same line.
       if(GetSlope() == l2.GetSlope()) return 1; // Ditto.
    
       // Vertical
       if(IsVertical())
       {
           ix = GetStart().x;
           iy = l2.GetValueAtX(ix);
           result = CPoint(ix, iy);
           return 0;
       }
       // Vertical
       if(l2.IsVertical())
       {
          // Same as above, but swapping l2 & *this.
       }
    
       // Two non vertical lines, do normally.
    }
    Change to fit your function prototype as needed.
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  8. #8
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    Yeah, that is what I started doing, just carrying around a vertical boolean flag.

    >> if(IsVertical() && l2.IsVertical()) return 1;
    >> if(GetSlope() == l2.GetSlope()) return 1;

    They can be overlapping or 'inside' one another. So yeah. I basically have implemented exactly what you advised. And it works great. It would be interesting to know how to check for indeterminate forms of IEEE floats though, unless diving by zero or checking it's just a time consuming operation or anything crazy (I've heard of floating point exceptions? Anything like thrown exceptions?)

    ╔╗╔╦══╦╗╔╦══╦╗
    ║╚╝║╔╗║╚╝║╔╗║║
    ║╔╗║╠╣║╔╗║╠╣╠╣
    ╚╝╚╩╝╚╩╝╚╩╝╚╩╝

    codez http://code.google.com/p/zxcvbn/

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. PLease Help with Class Implementation
    By Dilmerv in forum C++ Programming
    Replies: 13
    Last Post: 04-28-2006, 09:36 AM
  2. gcc problem
    By bjdea1 in forum Linux Programming
    Replies: 13
    Last Post: 04-29-2002, 06:51 PM
  3. Dealing with i/o streams in a class
    By ender in forum C++ Programming
    Replies: 3
    Last Post: 03-22-2002, 04:26 PM
  4. Difficulty superclassing EDIT window class
    By cDir in forum Windows Programming
    Replies: 7
    Last Post: 02-21-2002, 04:06 PM
  5. Exporting Object Hierarchies from a DLL
    By andy668 in forum C++ Programming
    Replies: 0
    Last Post: 10-20-2001, 01:26 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21