Sign in to follow this  

Dealing With Infinity - Vertical Slope

This topic is 4010 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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....)

Share this post


Link to post
Share on other sites
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[i])(), (*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;
}

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
If you don't want to change your way of doing your line class. when you draw it you can use the isfinite() function to check for an undefined slope. If it is undefined isfinite returns false otherwise returns true.

Share this post


Link to post
Share on other sites

This topic is 4010 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this