Maths: Perpendicular lines

[Kyon]

I've been playing around with Grapher (Mac OSX utility program) these days, I made two main formulas:

y = ax+b
y = (-x+x_p)/a + y_p

To create (in order) a basic line and a line perpendicular to it which passes the point (x_p,y_p). a, b, x_p and y_p are all defined and it works great.

I did some calculations with it, for example, a should be equal to: (-2b + 2y_p)/2x_p + or - (p√(4b²-8bq+4y_p²+4x_p²)) to do something special (kudos if you find out what it will do in that scenario).

The problem I'm having is finding the point where they cross (ax+b = (-x+x_p)/a + y_p) and drawing a point at that spot.

I've been writing formulas down and what not, but I end up getting the same I started with. :/

[hamsterman]

You want to find where the two perpendicular lines cross?

lines y = ax+b and y = cx+d cross when..
ax+b = cx+d
ax-cx = d-b
x = ( d-b )/( a-c )

when 2'nd line is perpendicular to 1'st, ..
y = (-x+x_p)/a + y_p = -(1/a) * x + (x_p/a + y_p)
so
c = -1/a
d = x_p/a + y_p
so
x = ( x_p/a + y_p-b )/( a+1/a )

have fun

[Kyon]

Thanks, that worked. :D Can you find out in what scenario a equals the above? (See first post) :P

[hamsterman]

(-2b + 2y_p)/2x_p + or - (p√(4b²-8bq+4y_p²+4x_p²))
what is p and q here?

[Kyon]

Just put those name to differentiate them from x and y. They are defined as:

y = ax+b
y = (-x+x_p)/a + y_p

To create (in order) a basic line and a line perpendicular to it which passes the point (x_p,y_p).

EDIT:
Shorter (and cleaner) way to write it:

-b+y_p±√(b²-2by_p+y_p²+x_p²)
a= _________________________
x_p

HINT Something to do with intersection.

[hamsterman]

that 'thing' seems to be a root of equation
x_p/2*a² + (b-y_p)*a + x_p/2 = 0
from this I got that
(a-1/a)/2 = (y_p-b) / x_p

(a-1/a)/2 is the average of the coefficients of the two lines and
(y_p-b) / x_p is the coefficient of the line form (0;b) to (x_p;y_p)

don't see anything else..

[Kyon]

The intersection point of the lines is at p/2 when a equals either of those values. ± determines if it's up or down (since it can be both to still cross the point). I figured perpendicular lines were good to use for normals in 2d games and whatnot, that's why I started playing with them like this.

Next up is finding the length of the normal. Gonna try that myself. :P

[hamsterman]

in a game, your line will most likely not be represented by a y=ax+b, but by two points A and B.
from two points you can get a vector A^->B = (x; y)
a vector perpendicular to that is either (-y;x) or (y;-x).

[Kyon]

Hm, good point. :P (Mind the pun. :P)

[Disch]

I've tried many techniques to find line intersections. Most of my early attempts started out with finding the slope and doing a lot of calculations (like you're doing), but it was always messy and complicated.

The big problem with slope is that vertical lines have undefined slope, which means you have to throw in all sorts of special cases to work with vertical lines. I always had to write 2x the code (one for vertical and one for non-vertical), and it was a big headache.

Not to mention the math is quite complicated. I mean just look at your equation there in Kyon's post. That's nuts.

I've since abandoned slope calculations in favor of basic linear algebra, which I admittedly don't fully understand, but I know more or less how to use it.

Here's a simple line intersection function I'm currently using in my game:

// support functions
inline double Dot(const Point& a,const Point& b)                        { return (a.x*b.x) + (a.y*b.y); }
inline double PerpDot(const Point& a,const Point& b)                    { return (a.y*b.x) - (a.x*b.y); }

bool LineCollision( const Point& A1, const Point& A2,
                    const Point& B1, const Point& B2,
                    double* out                                )
{
    Point a(A2-A1);
    Point b(B2-B1);

    double f = PerpDot(a,b);
    if(!f)      // lines are parallel
        return false;

    Point c(B2-A2);
    double aa = PerpDot(a,c);
    double bb = PerpDot(b,c);

    if(f < 0)
    {
        if(aa > 0)     return false;
        if(bb > 0)     return false;
        if(aa < f)     return false;
        if(bb < f)     return false;
    }
    else
    {
        if(aa < 0)     return false;
        if(bb < 0)     return false;
        if(aa > f)     return false;
        if(bb > f)     return false;
    }

    if(out)
        *out = 1.0 - (aa / f);
    return true;
}

A2-A1 is a line segment, as is B2-B1. out (if provided) is how far along line B you can move before the intersection (scaled between [0..1]). This was more useful than the exact intersect point for my purposes (seeing how far something can move before it hits a wall, for example).

If you need the intersect point, you can change it like so:

bool LineCollision( const Point& A1, const Point& A2,
                    const Point& B1, const Point& B2,
                    Point* out                                )
{
    //...

    if(out)
        *out = (b * (1.0 - (aa / f))) + B1;  // this could probably be simplified -- but I'm lazy
    return true;
}

This code will work to find intersection between any two line segments of any angle and length. As you can see the code is actually pretty short and simple, and it's surprisingly fast.

I've had much better luck with this than with any method that involved calculating slope. What's more, when you get more familiar with other linear algebra concepts, the slope becomes less and less useful.

EDIT:

Oh wait, I just read that this was for some graphing program and not for a C++ program. Har. Oh well. XD

[Kyon]

It was interesting to read, though. :P Would you mind posting your class definition of Point?

[Disch]

It's a typedef of sf::Vector2<double>

http://www.sfml-dev.org/documentation/1.6/Vector2_8hpp-source.htm

I renamed it to 'Point' even though it represents a vector because it use it to keep track of points as well as vectors.

[hamsterman]

This is how I find my intersections:

We have lines AB and CD.
I'll write vectors as vAB instead of A^->B, since I'm lazy.

Every point P on line AB can be expressed as P = A + vAB*k, where k is any real value. If 0 <= k <= 1, P is between A and B.
The same is true for Q = C + vCD*m

If AB and CD intersect, P = Q
A + vAB*k = C + vCD*m is a simple system of two linear equations (for x and y components)
vAB*k = C-A + vCD*m
vAB*k = vAC + vCD*m

vABx*k = vACx + vCDx*m
vABy*k = vACy + vCDy*m

I'll skip the actual solving..

...

so in the end,
k = ( vACx*vCDy - vCDx*vACy ) / ( vABx*vCDy - vCDx*vABy )
m = ( vACx*vABy - vABx*vACy ) / ( vABx*vCDy - vCDx*vABy )

note that the bottom parts are the same.

so the code would be

bool LineCollision(Point A, Point B, Point C, Point D, Point* out){
   float b = ( B.x-A.x )*( D.y-C.y ) - ( D.x-C.x )*( B.y-A.y );
   float k = ( ( C.x-A.x )*( D.y-C.y ) - ( D.x-C.x )*( C.y-A.y ) ) / b;
   float m = ( ( C.x-A.x )*( B.y-A.y ) - ( B.x-A.x )*( C.y-A.y ) ) / b;

   if(k >= 0 && k <= 1 && m >= 0 && m <= 1){
      if(out){
         out->x = A.x + (B.x-A.x)*k;
         out->y = A.y + (B.y-A.y)*k;
      }
      return true;
   }
   return false;
}

This is quite similar to Disch's. Maybe a bit easier to understand..

[Disch]

Yeah it looks like you're doing the exact same thing, just with a different approach.

Although I never saw it explained as clearly as that. Very nice.

The only thing that concerns me is that you'd have problems if b == 0, which will happen when AB and CD are parallel. You would have divisions by zero. Although if that returns NaN for floats (does it?), your code would still work.

[Kyon]

I believe x/0.00 evaluates to inf for doubles.

Those codes really look a bit simpler than using lines.. I'll definitely take a look at vector maths and the like later on.

[Kyon]

The b == 0 can easily be worked around, just add another if.

bool LineCollision(Point A, Point B, Point C, Point D, Point* out){
   float b = ( B.x-A.x )*( D.y-C.y ) - ( D.x-C.x )*( B.y-A.y );
   if (b)
   {
     float k = ( ( C.x-A.x )*( D.y-C.y ) - ( D.x-C.x )*( C.y-A.y ) ) / b;
     float m = ( ( C.x-A.x )*( B.y-A.y ) - ( B.x-A.x )*( C.y-A.y ) ) / b;

      if(k >= 0 && k <= 1 && m >= 0 && m <= 1){
         if(out){
            out->x = A.x + (B.x-A.x)*k;
            out->y = A.y + (B.y-A.y)*k;
         }
         return true;
      }
   }
   return false;
}

[Kyon]

Further optimized function.

bool LineCollision(Point A, Point B, Point C, Point D, Point& out)
{   if ((B.x-A.x)*(D.y-C.y)!=(D.x-C.x)*(B.y-A.y))
    {   float k = ( C.x-A.x )*( D.y-C.y ) - ( D.x-C.x )*( C.y-A.y );
        float m = ( C.x-A.x )*( B.y-A.y ) - ( B.x-A.x )*( C.y-A.y );
        if((k >= 0) && (m >= 0))
        {   float b = ( B.x-A.x )*( D.y-C.y ) - ( D.x-C.x )*( B.y-A.y );
            if(k <= b && m <= b)
            {   k/=b;
                out.x = A.x + (B.x-A.x)*k;
                out.y = A.y + (B.y-A.y)*k;
                return true;}}}
    return false;}

Now that we are on the collision subject, what are the main "collision types"? I know of:

Point point
Point line
Point circle
Line line
Line circle
Circle circle

[rocketboy9000]

In my games I have used also:
rectangle - rectangle
rectangle - line
rectangle - circle
rectangle - point
rectangle - arc (like a ballistic trajectory)
3d line - 3d surface (for a perfect ai for pong)

[Kyon]

I've been trying to write a code to calculate the surface of any vertex shaped n-sided polygon (by using triangulation) but I'm stuck on a part, the calculation of the area of the triangle.

Given:
A = 1/2 * SIDE * HEIGHT
In which SIDE is equal to the length of any line and HEIGHT is equal to the length of the linepiece that goes from the line from which SIDE was calculated to the last point, so that the two lines are perpendicular.

I have this so far:

#include <iostream>
#include <cmath>
using namespace std;

struct Point
{   Point(double xx=0, double yy=0):x(xx),y(yy){}
    double x, y;
    bool operator==(const Point& a) const {return (x == a.x && y == a.y);}
    Point operator+(const Point& a) const {return (Point(x+a.x,y+a.y));}
    Point operator-(const Point& a) const {return (Point(x-a.x,y-a.y));}
    Point operator*(double d) const {return (Point(x*d,y*d));}
    Point operator/(double d) const {return (Point(x/d,y/d));}};

struct Line
{   Line(const Point& a, const Point& b):A(a),B(b){}
    Point A, B;
    double Length() {return sqrt(pow(A.x-B.x,2)+pow(A.y-B.y,2));}};

struct Triangle
{   Triangle(Point a, Point b, Point c):A(a),B(b),C(c){if(a == b || a == c || b == c) throw 0;}
    Point A, B, C;
    double Area()
    {   //      SIDE              * HEIGHT                                          /2
        return (Line(A,B).Length()*Line(/* What needs to be put here? */,C).Length()/2);
    }};

int main()
{
    Triangle T(Point(0,0),Point(3,0),Point(3,3));
    cout << T.Area();
    return 0;
}

[hamsterman]

I bet you'll have a lot of fun with concave polygons..
As for the area, you may want to use http://en.wikipedia.org/wiki/Hero's_Formula