0

I would like to know if two surfaces are placed on top of each other on a 2D plane in C++. The method should be adaptative to a N sizes plane. I bet the best way to do that is to use a matrix but I don't know how.

On this picture, we have two triangles. So, the goal is to know if they have a shared space (red part here).

enter image description here

Moreira
  • 576
  • 2
  • 8
Milodupipo
  • 49
  • 1
  • 8

1 Answers1

0

Your question is unclear as to dimension. If you mean higher dimensions, you are not thinking about the problem clearly.

Assuming a 2d plane (and you can take a higher dimensioned object and project into a plane if necessary):

The subquestion you need is how to find when a line intersects another line. You did not draw the only case. One vertex of your triangle could be inside the other.

If you just need to know true or false if two triangles intersect, then test whether any of the lines intersect, or test whether any corner of t2 is "inside" t1 where inside includes being on the line. Note that there can be roundoff problems on the line.

How do you detect where two line segments intersect?

if (t1.contains.t2) {

}

will be true if:

bool contains(double x, double y) {
  return
    (p1 - p2).toLeft(x,y) &&
    (p2 - p3).toLeft(x,y) &&
    (p3 - p1).toLeft(x,y);
}

bool contains(const Triangle& t2) {
   return contains(t2.p1) || contains(t2.p2) || contains(t2.p3);
}

THe algorithm for whether the point is to the left of the line is here: How to tell whether a point is to the right or left side of a line

Community
  • 1
  • 1
Dov
  • 8,000
  • 8
  • 46
  • 75
  • Note that the toLeft solution above assumes that the triangle is in counter-clockwise order. – Dov Apr 09 '16 at 20:23
  • Thanks for your fast answer. I was only thinking in 2d to simplify the problem. But you are right about the case I forgot. Know if lines intersect is fine if we work on 2d but as you said we could have one vertex of he triangle inside the other in 3d. This case is my main problem, do you have a solution about this ? – Milodupipo Apr 09 '16 at 20:39
  • in 3d your question does not make sense. You can have two triangles that intersect each other as a point, a line, or a polygon. Do you really mean all of those cases? It is still similar. You would have to define the plane of the first triangle, see if the second triangle pieces that plane, and if it does, find out if that point is inside the triangle as described – Dov Apr 09 '16 at 21:04
  • I meaned in 2d I have to check intersects between lines of triangles. So in 3d I have to check faces intersects. If I do that for all faces I will know if shapes shared space. This way is adaptative to N dimensions. Is that right ? – Milodupipo Apr 09 '16 at 21:27
  • There is only one face in each triangle, so if that's what you mean, yes I guess. – Dov Apr 10 '16 at 14:42