Okay so I have a program that tests for collisions using a complicated and 80% accurate method, but I want 100% accuracy.
Like someone posted earlier about shapes colliding into each other, I realized that there will be cases where my method wont work.
However, I've looked into a calculus book and found a seemingly "easy" solution to the problem.
To be more descriptive...
If I have two vectors, and their cross product is not zero (they're not parallel) then they have the potential to intersect, or collide. So I know I have to implement a cross product (which wont be hard for 2D vectors).
That part is fine.
Here's where things get hard though - I need to determine the collision point for the two vectors.
Say vector a is defined to to have a direction of <3, 4> from point (0, 0). (3, 4) is the end point.
Also vector b is defined to have a direction of <-2, 1> from point (1, 0). (-1, 1) is the end point.
Linearly the two vectors can be defined as--
<3t, 4t> from time 0 to time 1 (where time can be seconds or whatever, doesn't matter).
<-2s + 1, s> from a separate time 0 to time 1 (where time can be anything again, doesn't matter. It just defines the point that vector is from "birth" to full existence.)
Here's the problem. I need to solve this, now, in terms of s and t which I don't know how to do in c++.
On paper it's easy, but doing a relational with variables is fairly difficult.
Basically this becomes a system of equations if I want to find out when the vectors meet at separate times t and s.
To find the collision point, solve for--
3t = -2s + 1
4t = s
3t = -2(4t) + 1
3t + 8t = 1
t(3 + 8) = 1
t = 1/(3 + 8) --> t = 1/11
s = 4/(3 + 8) --> s = 4/11
Solution: since both s and t are less than 1, there must be a collision between the 2 vectors since the vectors are fully defined at t and s = 1. If Either s or t were over 1, then there would be no collision... return false.
I know how to do this mathematically, but now how do I program relations like this? I'm thinking of three options but I'm not sure if they're optimal...
--Create a separate program/class that takes a stream object, empties it into a String (which im not sure if I can or can't do... not too good with c++ yet) and examine the equation listed then "solves" for one variable as a function of the other and finds a comparison between the two.
--Create a point-mapper with a precision factor (basically maps points along one vector and the other) and test the starting point of both vectors for the mapped points to see if either of them have the same direction as the point mapped. Then calculate if their magnitudes can reach this point, and if even one cant then obviously there's no collision between the vectors.
--Find an API that handles vector collisions.
I'm hoping I can find a logical way of doing this... I will post the code that I have so that you can better understand what I am trying to do.
Note: The current collision-check operation bool operator== (Triangle) is only 85% precise at the moment, and I want 100% accuracy. Here's the current code:
#include <cstdlib>
#include <iostream>
#include <math.h>
/**
File test_!.cpp in Project testing_Something.dev
Progress of project: Fairly good progress, collision precision is only 85% accurate. Found a solution for the problem, just need to find out how to code it properly.
*/
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{
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;
};
//~P2DVector(){for(int i = 0; i < 2; i++){ if(points[i] != 0){delete points[i]; points[i] = 0;}}};
static double power(double value, int exponent){
if(exponent < 0)
{
cout << "Negative powers currently unsupported.";
cout << "\nRetrying with positive value." << endl;
return power(value, -exponent);
}
else if(exponent == 0)
return 1;
else
return value * power(value, exponent - 1);
};
/*
static inline double root(double value, int root)
{
double temp = 1.0;
for(double i = 0.000001; i < 10; i += .000001)
{
for(int j = 0; j < root; j++)
temp *= i;
if(static_cast<long>(temp) == value)
return i;
temp = 1.0;
}
return 0.0;
};*/ //not precise enough, and even when it is, it's just too slow
double getXDir(){
return (points[1].getX() - points[0].getX());
};
double getYDir(){
return (points[1].getY() - points[0].getY());
};
double magnitude(){
return sqrt( (power( points[1].getX() - points[0].getX() ,2)
+power(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-] " << points[1].getX() << ", " << points[1].getY();
cout << "\nDirection is <" << getXDir() << ", " << getYDir() <<">";
cout << ".\nContains magnitude: " << magnitude() << "\n" << endl;
};
};
class Triangle{
private:
Point coordinates[3], shortestCollision[3];
P2DVector innerVectors[3], outterVectors[3];
public:
Triangle(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());
//need the natural vectors of the triangle!
outterVectors[0].Set(coordinates[0], coordinates[1]);
outterVectors[1].Set(coordinates[1], coordinates[2]);
outterVectors[2].Set(coordinates[2], coordinates[0]);
//need vectors for opposite sides of points!
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();
cout << "\nWith the inner vector:\n";
innerVectors[i].displayLocation();
cout << "\n" << flush;
}
};
Point getFirstPoint(){
return coordinates[0];
};
Point getSecondPoint(){
return coordinates[1];
};
Point getThirdPoint(){
return coordinates[2];
};
P2DVector firstInnerVector(){
return innerVectors[0];
};
P2DVector secondInnerVector(){
return innerVectors[1];
};
P2DVector thirdInnerVector(){
return innerVectors[2];
};
/**
Currently only 85% precise.
*/
bool operator== (Triangle other){
Point rogueTrianglePts[3] = {other.getFirstPoint(), other.getSecondPoint(), other.getThirdPoint()};
Point thisTrianglePts[3] = {getFirstPoint(), getSecondPoint(), getThirdPoint()};
int amount = 0;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
P2DVector rogueVector (thisTrianglePts[j], rogueTrianglePts[i]);
P2DVector ourVector (thisTrianglePts[i], rogueTrianglePts[j]);
P2DVector rogueInnerVectors[3] = {other.firstInnerVector(), other.secondInnerVector(),
other.thirdInnerVector()};
if(
rogueVector.magnitude() <= innerVectors[j].magnitude()
){
amount++;
}
else if(
ourVector.magnitude() <= rogueInnerVectors[j].magnitude()
){
amount++;
}
}
}
if(amount > 4){
cout << "There was an intersection!" << endl;
return true;
}
else{
cout << "There was NO intersection!" << endl;
return false;
}
};
};
int main(int argc, char *argv[]){
Point myPoints[3];
Point otherPoints[3];
Point anotherOutsider[3];
Point morePoints[3];
myPoints[0].Set(2, 0);
myPoints[1].Set(4, 1);
myPoints[2].Set(2, 3);
otherPoints[0].Set(0, 0);
otherPoints[1].Set(1, 0);
otherPoints[2].Set(1, 1);
anotherOutsider[0].Set(-2, 2);
anotherOutsider[1].Set(0, 0);
anotherOutsider[2].Set(-2, 0);
morePoints[0].Set(0, 0);
morePoints[1].Set(2, 1);
morePoints[2].Set(0, 1);
Triangle tri(1, 1, myPoints);
Triangle otherTri(5, 2, otherPoints);
Triangle lastTriangle(4, 0, anotherOutsider);
Triangle finalTriangle(2, 3, morePoints);
tri.displayParameters();
otherTri.displayParameters();
lastTriangle.displayParameters();
cout << (tri == otherTri) << endl;
cout << (tri==lastTriangle) << endl;
cout << (otherTri==lastTriangle) << endl;
cout << (tri == finalTriangle) << endl;
cout << (finalTriangle == otherTri) << endl;
cin.get();
return 0;
}I am definitely not asking anyone to do this for me. I'd just like to be given the proper direction for implementing this solution into the program.
