Triangles.

[Emerican]

Hello, i have i homework assignment where is need to make this programm.
I have coordinates(They can be anything you like) for two different triangles(It can be triangle ABC and triangle DEF) and i have to find if they have any common points where the sides cross. And i don't have any idea where to begin with this, because this is a whole lot different then any other assignment before.

[vlad from moscow]

You have to begin from mathematics to determine a formula that will give the answer whether the two triangle have any common pointer.

[Stewbond]

I've tried to make something in OOP.

This triangle is constructed with 3 points. It is defined with 3 line segments. Each line segment is constructed with 2 points.

The LineSegment class has a method bool intersects(LineSegment &comp) that tells us whether the lines intersect. The Triangle has a method bool intersects(Triangle &comp) that tells us whether the triangles intersect.

// helper functions
template <typename T> min(T a, T b) { return a < b ? a : b; }
template <typename T> max(T a, T b) { return a < b ? b : a; }

// Classes
struct Point
{
  // Members
  double x;
  double y;
  
  // Constructor
  Point (double _x, double _y) : x(_x), y(_y) {}
};

class LineSegment
{
private:
  // Members
  double m; // y = m * x + b
  double b;
  Point p1; // Bounds of the line segment
  Point p2; // Bounds of the line segment
  
  // Helpers
  double UpperBound() { return p1.x > p2.x ? p1.x : p2.x; }
  double LowerBound() { return p1.x > p2.x ? p2.x : p1.x; }
  
public: 
  // Constructor
  LineSegment (Point &_p1, Point &_p2) // Create a line from 2 points;
  : p1(_p1), p2(_p2)
  {
    m = (_p1.y - _p2.y) / (_p1.x - _p2.x);
    b = _p1.y - m * _p1.x;
  }
  
  // Methods
  bool intersects(LineSegment &comp) // Checks if two lines intersect within the bounds
  {
    if (this->UpperBound() < comp.LowerBound()) return false; // 'this' helps clarify who the method belongs to.
    if (this->LowerBound() > comp.UpperBound()) return false;
  
    double lowerXbound = max(this->LowerBound(), comp.LowerBound());
    double upperXbound = min(this->UpperBound(), comp.UpperBound());
  
    double lowerYdiff = (this->m - comp.m) * lowerXbound + (this->b  - comp.b); // Finds the difference in Y at the lower bound
    double upperYdiff = (this->m - comp.m) * upperXbound + (this->b  - comp.b); // Finds the difference in Y at the upper bound
  
    return (lowerYdiff * upperYdiff) < 0; // Checks if the signs are opposite (ie they have crossed)
  }
};

class Triangle
{
  // Members
  LineSegment l1;
  LineSegment l2;
  LineSegment l3;
public:
  // Constructor
  Triangle (Point &_p1, Point &_p2, Point &_p3) 
  : l1(_p1,_p2), l2(_p2,_p3), l3(_p3,_p1)
  {  }
  
  // Methods
  bool intersects(Triangle &comp) // Checks if two triangles have any intersecting edges
  {
    if ( l1.intersects(comp.l1) ) return true; // Check all of the line segments
    if ( l1.intersects(comp.l2) ) return true;
//  if ( l1.intersects(comp.l3) ) return true; // After some checking, I don't actually need to test this line!
    if ( l2.intersects(comp.l1) ) return true;
    if ( l2.intersects(comp.l2) ) return true;
//  if ( l2.intersects(comp.l3) ) return true; // or this one
    if ( l3.intersects(comp.l1) ) return true;
    if ( l3.intersects(comp.l2) ) return true;
//  if ( l3.intersects(comp.l3) ) return true; // or this one :)
    return false;
  }
};

// Implementation
int main()
{
  Point A(1 ,4), B(2,3), C(3.5, 6);
  Point D(-3,5), E(5,3), F(4.2,-6); 
  Triangle t1(A,B,C);
  Triangle t2(D,E,F);
  
  if (t1.intersects(t2)) 
    cout << "These intersect";
  else
    cout << "These do not intersect";
  
  return 0;
}

[ne555]

// After some checking, I don't actually need to test this line! (line 3)

¿why not? Suppose the case where p2 lies inside the other triangle, and you pass over (precisely) line 3.

Also, vertical lines.

[Stewbond]

Oh wait your right. I didn't consider the case where a point of triangle 1 was in triangle 2 past this line. It CAN be reduced though.

[TheIdeasMan]

I can't help thinking that the OP's homework has been done already !!

[Emerican]

Ok, this script i think is just too much over my level at the moment and there must be an easier way to do this. . Any of you have ideas how could you do it without classes and methods, but just with pure math?

[TheIdeasMan]

Crikey Stewbond - look what you have done ...... :D Very good code - just way over the OP's head !!

@Emerican

Can you see in Stewbond's code the functions that do the calculations? He has used vector mathematics, which I am not sure whether you know about that or not.

Vector maths is often a lot easier than trigonometry.

I am hoping you might be able to pick out the parts that do the calculations, and turn them into your own functions.

Did your Lecturer give you any insight on how to do the math?

[Emerican]

No my lecturer at university definetly has not given me anything that could help me at this state, because this homework is way ahead the current learning topic (The current topic is the very basics like hello world n shit. I'm about two + months ahead of this and we can recieve all homework assignments for the semester at once, so this is like the 3rd one and deadline is maybe only in november... ) Had some other help at the moment i'm probobly going to figure the math thing out.Just don't have the opertunity t odo this at the moment.