Vector Collision class - for 2D Graphics

18 Years Ago Alex Edwards 0 226 Views

This is a program I designed that implements a little bit of vector-math to determine the collision between 2 vectors.

Hopefully this program will be useful to those out there designing 2D graphics programs and need a better solution to determining graphical object-to-object collisions when two objects meet, without having to rely on the famous "bounding box" that many graphical objects are defined by. One can simply implement this class and define their object to consist of these vectors and call upon the Set command for each vector whenever the graphical object is moved.

This is still experimental code, but the tests show that if the vectors meet at a point or intersect then there will be an Intersection met notice when the vectors are compared.

This class does NOT deal with the difference of shapes within shapes. If a shape is fully inscribed within another shape then a vector collision may fail. However, this may be useful if programs want to implement objects bouncing within other objects.

#include <cstdlib>
#include <iostream>
#include <math.h>
#include <iomanip>

/*
 *A Simple collision-detecting class
 *Made by Alex Edwards, modified by Ancient Dragon
 **/
using namespace std;

class Point;
class Triangle;
class P2DVector;

class Point{     
      private:
             double xP;
             double yP;
             
      public:
             Point(double x, double y){
                   xP = x;
                   yP = y;
             };
             Point() {xP = 0; yP = 0;}
             void Set(double x,double y) {xP = x; yP = y;}
             double getX(){return xP;};
             double getY(){return yP;};
             void showCoord(){
                  cout << "(" << getX() << ", " << getY() << ")" << endl;
             };
};

/*
 *class P2DVector
 *Named P2DVector to differentiate between the vector class and 3D vectors.
 **/
class P2DVector{
      private:
             Point points[2]; 
      
      public:
             P2DVector(Point& first, Point& second){
                      points[0] = first;
                      points[1] = second;        
             };
             P2DVector() {points[0] = Point(0,0); points[1] = Point(0,0); }
             void Set(Point& first, Point& second){
                      points[0] = first;
                      points[1] = second;        
             };
             double getXDir(){
                    return (points[1].getX() - points[0].getX());
             };
             double getYDir(){
                    return (points[1].getY() - points[0].getY());
             };
             double magnitude(){
                    return sqrt( (pow( points[1].getX() - points[0].getX() ,2) 
                                 +pow(points[1].getY() - points[0].getY() ,2)));
             };
             Point startPoint(){
                   Point p(points[0].getX(), points[0].getY());
                   return p;
             };
             Point endPoint(){
                   Point p(points[1].getX(), points[1].getY());
                   return p;
             };
             P2DVector unitP2DVector(){      
                    Point unitPoint[2];
                    unitPoint[0].Set(points[0].getX() / magnitude(), points[0].getY() / magnitude());
                    unitPoint[1].Set(points[1].getX() / magnitude(), points[1].getY() / magnitude());
                    P2DVector temp (unitPoint[0], unitPoint[1]);
                    return temp;
             };
             void displayLocation(){
                  cout << "This P2DVector Starts-> " << "" << points[0].getX() << ", " << points[0].getY();
                  cout << "\nEnds-] " << "\t\t\t" << points[1].getX() << ", " << points[1].getY();
                  cout << "\nDirection: "<< "\t\t" << "<" << getXDir() << ", " << getYDir() <<">";
                  cout << "\nContains magnitude: \t" << magnitude() << "\n" << endl;
             };
             bool operator==(P2DVector &other){
                  double otherXDirection = other.getXDir();
                  double otherYDirection = other.getYDir();
                  double xDirection = getXDir();
                  double yDirection = getYDir();
                  
                  //The statements below are a solution to a system of equations for vector-to-vector collisions
                  double time2 = ((other.startPoint().getY()-startPoint().getY())-
                  (((other.getYDir())*((other.startPoint().getX())-(startPoint().getX())))
                  /(other.getXDir())))/((getYDir())-((other.getYDir())*((getXDir())/(other.getXDir()))));    
                              
                  double time1 =  ((startPoint().getX() - other.startPoint().getX())
                                  + ((getXDir()) * (time2)))/(other.getXDir());
                                   
                 return time1 >= 0 && time1 <=1 && time2 >= 0 && time2 <=1;
             };
};

/*
 *A Sample shape that utilizes the vectors
 **/
class Triangle{
      private:
              Point coordinates[3], shortestCollision[3];
              P2DVector innerVectors[3], outterVectors[6];
      
      public:
             Triangle(double xLoc, double yLoc, Point points[3]){       
                  Set(xLoc, yLoc, points);
             };
             void Set(double xLoc, double yLoc, Point points[3]){         
                  for(int i = 0; i < 3; i++)
                        coordinates[i].Set( xLoc + points[i].getX(), yLoc + points[i].getY());    
                                          
                  outterVectors[0].Set(coordinates[0], coordinates[1]);
                  outterVectors[1].Set(coordinates[1], coordinates[2]);
                  outterVectors[2].Set(coordinates[2], coordinates[0]);
                  outterVectors[3].Set(coordinates[1], coordinates[0]);
                  outterVectors[4].Set(coordinates[2], coordinates[1]);
                  outterVectors[5].Set(coordinates[0], coordinates[2]);                  
                  
                  shortestCollision[0].Set(outterVectors[1].startPoint().getX() 
                  + ((outterVectors[1].getXDir() ) / 2),outterVectors[1].startPoint().getY() 
                  + ((outterVectors[1].getYDir() ) / 2));
                  innerVectors[0].Set(coordinates[0], shortestCollision[0]);
                  
                  shortestCollision[1].Set(outterVectors[2].startPoint().getX() 
                  + ((outterVectors[2].getXDir() ) / 2), outterVectors[2].startPoint().getY() 
                  + ((outterVectors[2].getYDir() ) / 2));
                  innerVectors[1].Set(coordinates[1], shortestCollision[1]);
                  
                  shortestCollision[2].Set(outterVectors[0].startPoint().getX() 
                  + ((outterVectors[0].getXDir() ) / 2), outterVectors[0].startPoint().getY() 
                  + ((outterVectors[0].getYDir() ) / 2));
                  innerVectors[2].Set(coordinates[2], shortestCollision[2]);                                 
             };             
                                     
             void displayParameters(){
                  cout << "This triangle is defined by the points/vectors (in this order):\n" << flush;
                  for(int i = 0; i < 3; i++){
                          coordinates[i].showCoord();
                          outterVectors[i].displayLocation();
                          cout << "\n" << flush;
                  }
             };
             Point *getPoints(){
                   return coordinates;
             };
             P2DVector *getInnerVectors(){
                   return innerVectors;
             }
             P2DVector *getOutterVectors(){
                   return outterVectors;
             }        
             bool operator==(Triangle &other){
                  P2DVector myVectors[] = {getOutterVectors()[0], getOutterVectors()[1], 
                                           getOutterVectors()[2], getOutterVectors()[3], 
                                           getOutterVectors()[4], getOutterVectors()[5]};                                           
                                           
                  P2DVector rogueVectors[] = {other.getOutterVectors()[0], other.getOutterVectors()[1], 
                                           other.getOutterVectors()[2], other.getOutterVectors()[3], 
                                           other.getOutterVectors()[4], other.getOutterVectors()[5]};                                         
                  
                  for(int i = 0; i < 6; i++){
                          for(int j = 0; j < 6; j++){
                                  if(myVectors[i] == rogueVectors[j]){
                                      cout << "Intersection met!" << endl;
                                      return true;
                                  }
                          }
                  }
                  cout << "No intersection met!" << endl;
                  return false;
             };                         
};

/*
 *Tests the shapes, which are triangles in this case, for a collision.
 **/
int main(int argc, char *argv[]){
    Point myPoints[3], otherPoints[3], finalPoints[3];
    myPoints[0].Set(0, 0), myPoints[1].Set(2, 2), myPoints[2].Set(2, 1);
    otherPoints[0].Set(0, 0), otherPoints[1].Set(0, 1), otherPoints[2].Set(1, 0);
    finalPoints[0].Set(0, 0), finalPoints[1].Set(1, 1), finalPoints[2].Set(1, 0);
    Triangle tri(0, 2, myPoints), otherTri(1.5, 2, otherPoints), finalTri(2, 2, finalPoints);
    
    tri.displayParameters();
    otherTri.displayParameters();
    finalTri.displayParameters();
    
    (tri == otherTri); //Checking for intersection between the first triangle with the second
    (tri == finalTri); //Checking for intersection between the first triangle with the third
    (otherTri == finalTri); //Checking for intersection between the secondtriangle with the third
    
    cout << "\n" << endl;
    finalTri.Set(1.5, 2, otherPoints);
    cout << "Setting the 3rd triangle to same coords as 2nd...\n" << endl;
    
    (tri == otherTri); //Checking for intersection between the first triangle with the second
    (tri == finalTri); //Checking for intersection between the first triangle with the third
    (otherTri == finalTri); //Checking for intersection between the secondtriangle with the third    
    
    cin.get();
    return 0;
}

Dani AI

Generated 7 Months Ago

A neat, compact edge-based collision idea from — good for replacing crude bounding-box tests when objects are represented by their edges. The current Triangle implementation checks every pair of directed edges for intersection, which is fine for many cases but, as noted in the original post, it does not detect full containment or handle degenerate cases robustly.

Key correctness and robustness issues to address:

The P2DVector::operator== math divides by other.getXDir() without handling zero (vertical segments) — risk of division-by-zero and NaN.
Exact comparisons on floating-point times are used; a small epsilon is required to avoid instability.
operator== is used for an intersection test and also prints side effects; a clearly named intersects(const P2DVector&) const is more appropriate and should be const.
unitP2DVector currently scales points instead of producing a true unit direction; this should return a normalized direction or an endpoint computed as start + unitDir.
Triangle-level collision only compares edges; containment requires a point-in-triangle test (barycentric or sign-of-area) or a polygon method like the Separating Axis Theorem for convex shapes.

Concrete replacement idea (robust segment test): compute 2D cross products (orientation), test sign combinations for strict intersection, and explicitly handle colinear overlap with an on-segment check. Example outline:

double cross(const Point& a,const Point& b,const Point& c){
  return (b.getX()-a.getX())*(c.getY()-a.getY()) - (b.getY()-a.getY())*(c.getX()-a.getX());
}
// Use cross products d1..d4 and an eps; if d1*d2 < 0 && d3*d4 < 0 -> intersect.
// If any di ~ 0, use on-segment checks to detect colinear overlap.

Other practical improvements: cache dx/dy/magnitude inside P2DVector and update on Set, add a small EPS (e.g. 1e-9) for comparisons, make methods const and pass parameters by const&, avoid using namespace std, and add unit tests covering vertical/horizontal, colinear overlapping, endpoint-touching, and full containment. These changes keep the original design intent but make collisions reliable in production code.

Be the first to reply

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.