Dealing With Infinity - Vertical Slope

Math and Physics Programming

Started by Milquetoasty December 15, 2006 12:08 AM

9 comments, last by SuperNerd 17 years, 3 months ago

128

Author

December 15, 2006 12:08 AM

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:

    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.

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?

erissian

727

December 15, 2006 12:36 AM

You could always use the line form:
ax + by + c = 0

Which if you look at the form you're using:
y = mx + h

Then h=-c/b and m=-a/b

In the case of an infinite slope, that's because you have b=0, and therefore a division by zero, which computers don't like too much. If you use the other form, things should run smoothly.

We''re sorry, but you don''t have the clearance to read this post. Please exit your browser at this time. (Code 23)

Milquetoasty

128

Author

December 15, 2006 02:26 AM

Well, I wouldn't be able to just take two points on a plane and then jump to the general form (or can I?). My isolated way feels the need to convert the point slope into the general form, which of course causes errors.

sphen_lee

199

December 15, 2006 02:28 AM

In my opinion the best way to represent a line is using the vector representation:
r = (1 - t)*start + t*end
where start, end and r are vectors. t is a number between 0 and 1.

This can be simplified to:
r = origin + direction*t
where origin = start, and direction = end - start

Although this method is good for describing lines, as it removes the infinite gradient problem for a vertical line, and can be extended to 3 dimensions, it makes the intersection formula more complex.

A simpler method perhaps would be to swap x and y for the case when x is less than y (that is when the gradient is greater than 1). This makes vertical lines become horizontal; find the intersection point as normal, and then swap x and y back.

Zakwayda

2,389

December 15, 2006 07:51 AM

Just want to reinforce that there's rarely (if ever) any need to use the 'slope' form for 2D linear components in games or graphics programming. Just forget about y = mx+b and familiarize yourself with the aforementioned parametric form, and perhaps the hyperplane form as well (ax+by+c = 0). Pretty much anything you might need to do (intersection testing, reflection, bouncing, rendering) can be done more readily using these representations.

Zipster

2,420

December 15, 2006 12:04 PM

Quote:Original post by Milquetoasty
Well, I wouldn't be able to just take two points on a plane and then jump to the general form (or can I?). My isolated way feels the need to convert the point slope into the general form, which of course causes errors.

The general form is actually the same as the hyperplane form that jyk points out, which you can determine directly. I recommend this form because once you understand how it works in one or two dimensions, it's easily generalizable to any dimension, and it requires a minimal amount of data to describe the hyperplane (only three values for a line). Personally, I use a slightly modified form of ax + by = c where the constant is on the right side, just because that's the form you'd use a system of equations and it's a bit more intuitive when it comes to calculating the coefficients.

The process for determining the general form of a hyperplane goes something like:

1) Determine a basis for the hyperplane. For a line, this is just the difference between two unique points, (pointB - pointA).

2) Calculate a vector orthogonal to this basis (call it the normal). In 2D, this is known as the perpendicular: perp((x,y)) = (-y,x). Optional, but recommend: normalize the normal.

3) Let the components of the normal be the first N-1 coefficients. So a is the x-component of the normal, and b is the y-component of the normal.

4) Determine the final constant by taking the dot product between the normal and a point on the hyperplane. You can either do dot(normal,pointA) or dot(normal,pointB) since both points are on the line. If c is on the left side of the equation, then you also want to negate the result.

Gagyi

192

December 18, 2006 09:47 AM

This means if you have two points:
P1(x1;y1) P2(x2;y2)
you have the normal:
n(y2-y1;x1-x2)
and the equation
(y2-y1)*X+(x1-x2)*Y=x1*y2-y1*x2

If you want the intersection point, you have to simultaneusly solve the two equations:
a1*X+b1*Y=c1
a2*X+b2*Y=c2

(high school mathematics....)

-----------------------------------"After you finish the first 90% of a project, you have to finish the other 90%." - Michael Abrashstickman.hu <=my game (please tell me your opinion about it)

erissian

727

December 18, 2006 04:44 PM

To continue on that thought, revising the notation a little:
ax + by = c
dx + ey = f

x = (c-bf/e)/(a-bd/e)
y = (c-af/d)/(b-ae/d)

We''re sorry, but you don''t have the clearance to read this post. Please exit your browser at this time. (Code 23)

Milquetoasty

128

Author

December 21, 2006 05:50 PM

I felt like just pursuing the point slope form for kicks n such, and thought you guys might get a kick out of the way I tried to solve it. I take like any of you're guys' advice in doing it, so it's definitely pretty comical with all the special cases and stuff. I intend to try the hyperplane and parametric forms of this stuff -- once I finish applying to colleges. I'm trying not to let school get in the way of my education, but I gotta make an exception for stupid colleges.

Anyways, get ready for a laugh.

bool RotatingPong::CLineSegment::intersects( const CLineSegment & other ){    // Same (note: overloaded equality operator)    if( *this == other )    {        dout << "*this == other\n";        return true;    }    // Both vertical    if( m_vertical && other.m_vertical )    {        // On same line, check containing/overlap        if( m_end.x == other.m_end.x &&            ( (                 m_end.y <= max( other.m_end.y, other.m_start.y ) &&                 m_end.y >= min( other.m_end.y, other.m_start.y )             ) ||            (                 m_start.y <= max( other.m_end.y, other.m_start.y ) &&                 m_start.y >= min( other.m_end.y, other.m_start.y )             ) ||            (                 other.m_end.y <= max( m_end.y, m_start.y ) &&                 other.m_end.y >= min( m_end.y, m_start.y )             ) ||            (                 other.m_start.y <= max( m_end.y, m_start.y ) &&                 other.m_start.y >= min( m_end.y, m_start.y )             ) ) )        {            dout << "verticals\n";            return true;        }        else return false;    }    // One vertical    if( m_vertical && !other.m_vertical )    {        double y =             other.m_slope * m_end.x -             other.m_slope * other.m_end.x +             other.m_end.y;        double vmin_y = min( m_start.y, m_end.y );        double vmax_y = max( m_start.y, m_end.y );        if( y >= vmin_y && y <= vmax_y &&             m_end.x < max( other.m_end.x, other.m_start.x ) &&             m_end.x > min( other.m_end.x, other.m_start.x ) )        {            return true;        }        else return false;    }    // Other vertical    else if( other.m_vertical && !m_vertical )    {        double y =             m_slope * other.m_end.x -             m_slope * m_end.x + m_end.y;        double vmin_y = min( other.m_start.y, other.m_end.y );        double vmax_y = max( other.m_start.y, other.m_end.y );        if( y >= vmin_y && y <= vmax_y &&            other.m_end.x < max( m_end.x, m_start.x ) &&            other.m_end.x > min( m_end.x, m_start.x ) )        {            return true;        }        else return false;    }    // Same slope    else if( abs(m_slope - other.m_slope) < 0.001 )    {        // Special case checking intersection of horizontals        if( abs(m_slope) < 0.001 && abs(other.m_slope) < 0.001 )        {            if( m_end.y == other.m_end.y &&                                ( ( m_end.x <= max( other.m_end.x, other.m_start.x ) &&                     m_end.x >= min( other.m_end.x, other.m_start.x )                 ) ||                (                     m_start.x <= max( other.m_end.x, other.m_start.x ) &&                     m_start.x >= min( other.m_end.x, other.m_start.x )                 ) ||                (                     other.m_end.x <= max( m_end.x, m_start.x ) &&                     other.m_end.x >= min( m_end.x, m_start.x )                 ) ||                (                     other.m_start.x <= max( m_end.x, m_start.x ) &&                     other.m_start.x >= min( m_end.x, m_start.x )                 ) ) )            {                return true;            }                        else return false;        }        // General case checking intersection of lines with same slope        if( m_end.y - other.m_end.y == m_slope * ( m_end.x - other.m_end.x ) ||            m_end.y - other.m_start.y == m_slope * ( m_end.x - other.m_start.y ) )        {            return true;        }        else return false;    }    //    //  General case for line intersection    //      o Solves for point slope representations    //    //    //    //                  yb - ya + ma * xa - mb * xb    //    x      =      --------------------------    //                           ma - mb    //    //            ma * mb * ( xb - xa ) + mb * ya - ma * yb    //    y   =   ----------------------------------------    //                           mb - ma    double x =         ( other.m_end.y - m_end.y - other.m_slope *         other.m_end.x + m_slope * m_end.x ) /            ( m_slope - other.m_slope );    double y =         ( other.m_slope * m_end.y - m_slope * other.m_end.y +         m_slope * other.m_slope * ( other.m_end.x - m_end.x ) ) /                     ( other.m_slope - m_slope );        // x I [x1, x2] && x I [x3, x4]    // y I [y1, y2] && y I [y3, y4]    if( x >= min( m_end.x, m_start.x ) && x <= max( m_end.x, m_start.x ) &&        x >= min( other.m_end.x, other.m_start.x ) && x <= max( other.m_end.x, other.m_start.x ) &&        y >= min( m_end.y, m_start.y ) && y <= max( m_end.y, m_start.y ) &&        y >= min( other.m_end.y, other.m_start.y ) && y <= max( other.m_end.y, other.m_start.y ) )    {        return true;    }    else return false;}

I use this method many times as I check every single border of a quadrilateral for a line intersection! I am very thankful that technology these days makes fast computers, because I'm being very brutal!

bool RotatingPong::CRotatingSquare::intersects( const CRotatingSquare & o ) const{    CPoint ( CRotatingSquare::* vertices [ 4 ] )( void ) const =    {        &CRotatingSquare::tl,        &CRotatingSquare::tr,        &CRotatingSquare::br,        &CRotatingSquare::bl    };    const int v_size = sizeof(vertices) / sizeof(vertices[0]);    for( int i = 0; i < v_size; ++i )    {        CLineSegment c( (*this.*vertices)(), (*this.*vertices[(i + 1) % v_size])() );        for( int j = 0; j < v_size; ++j )        {            CLineSegment d( (o.*vertices[j])(), (o.*vertices[(j + 1) % v_size])() );            if( c.intersects(d) )            {                return true;            }        }    }        return false;}

Gagyi

192

December 25, 2006 05:35 AM

Quote:
To continue on that thought, revising the notation a little:

Sorry, I was lazy to solve the equation too :D

Milquetoasty, your code proves thet calculating with slope is really hard, so many exceptions, infinities... With the parametric form aX+bY=c, you only have to worry about paralell lines.
[edit: some mistakes...]

[Edited by - Gagyi on December 26, 2006 8:35:11 AM]

-----------------------------------"After you finish the first 90% of a project, you have to finish the other 90%." - Michael Abrashstickman.hu <=my game (please tell me your opinion about it)

Dealing With Infinity - Vertical Slope

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Dealing With Infinity - Vertical Slope

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines