   Check if triangle overlaps with restricted plane in 3D
  Suppose I have N vertices defining a part of a plane in 3D space. I then have an algorithm to find if other points (triangles) are on the full plane (I check if triangle has the same normal and is on the plane). The only thing I need to know, is if a given triangle overlaps with the restricted plane area.So I have N vertices in one plane defining an area. I then have M * 3 other vertices defining triangles that are in the plane as well. I need to know if the surface of the defined area and of a certain triangle overlap. This all happens in 3D, but since we work on one plane I suppose we could translate it to be a 2D problem.Thanks for any suggestions :)Decrius   
  I guess you want to clip the triangle against the restricted area, and see if they are inside each other. If the restricted area is convex this is very easy, just test if any point of the triangle is inside the area, or if any point on the edge of the area is inside the triangle.To see if a point is inside the area, test it's distance to the edges of the area. For a convex area, the point must be on the correct side of every edge for it to be inside the area.If you want to stay in 3D, make a new plane for every edge, from the 3 points p0, p1, p0+normal, where p0 and p1 are the two points of an edge, and normal is the plane normal. This plane will be perpendicular to the plane with the area on it. Then check the distance from the point to this new plane, and see if it's on the correct side.If you have a concave shape it's a harder problem. You need to divide it into several convex areas and do the same test on each area then, using a BSP or similar.   ;  Thank you very much! ;-), yes it's indeed a convex shape.I had thought of checking if the triangle has any points inside the convex, but not vice versa ;). Thanks for the advice.But how do I know to which edge I need to calculate the distance to? And how would I discover if it's on the correct side?Thanks!   ;  You must calculate the distance to every edge, and the point must be on the same side of every edge, for it to be inside. The correct side is either where the point has a positive distance, or where it has a negative distance, depending on what direction your edges are facing. It should be easy to test.   ;  I would recommend using the separating axis test rather than a per-feature test (IMO, the SAT would be a little cleaner and simpler, and might be more stable as well). You can either project both polygons to a 2-d plane and perform the test there, or do the test in 3-d and use the normals of the polygon edge planes as the potential axes to test.   ;  Thanks guys! I've managed to write it myself :D, here's the code if anyone is interested (took me about 2-3 hours):main.hppstruct Vertex{    double x, y, z;    Vertex(double x = 0, double y = 0, double z = 0) :   x(x),   y(y),   z(z)    {    }    Vertex operator- (const Vertex &vertex)    {   return Vertex(x - vertex.x, y - vertex.y, z - vertex.z);    }};double dot_product(const Vertex &vertex1, const Vertex &vertex2);Vertex cross_product(const Vertex &vertex1, const Vertex &vertex2);bool point_inside_triangle(Vertex vertex, Vertex triangle[3], bool edge1_included = false, bool edge2_included = false, bool edge3_included = false);bool triangle_overlaps_triangle(Vertex triangle1[3], Vertex triangle2[3], bool edge1_included = false, bool edge2_included = false, bool edge3_included = false);bool convex_overlaps_triangle(unsigned int n, Vertex *convex, Vertex triangle[3], bool edge1_included = false, bool edge2_included = false, bool edge3_included = false);bool triangle_overlaps_convex(Vertex triangle[3], unsigned int n, Vertex *convex);bool convex_overlaps_convex(unsigned int n1, Vertex *convex1, unsigned int n2, Vertex *convex2);main.cpp#include <iostream>#include "main.hpp"// outputs 'Triangle inside convex' :-)int main(){    Vertex triangle[] = {Vertex(0, 0), Vertex(2, 0), Vertex(1, 2)};    Vertex convex[] = {Vertex(0, 1), Vertex(2, 1), Vertex(2, 3), Vertex(0, 3)};    if (convex_overlaps_triangle(4, convex, triangle))    {   std::cout << "Convex inside triangle\n";    }    else if (triangle_overlaps_convex(triangle, 4, convex))    {   std::cout << "Triangle inside convex\n";    }    else    {   std::cout << "No collision\n";    }    return 0;}double dot_product(const Vertex &vertex1, const Vertex &vertex2){    return (vertex1.x * vertex2.x) + (vertex1.y * vertex2.y) + (vertex1.z * vertex2.z);}Vertex cross_product(const Vertex &vertex1, const Vertex &vertex2){    return Vertex(   (vertex1.y * vertex2.z) - (vertex1.z * vertex2.y),   (vertex1.z * vertex2.x) - (vertex1.x * vertex2.z),   (vertex1.x * vertex2.y) - (vertex1.y * vertex2.x)    );}bool point_inside_triangle(Vertex vertex, Vertex triangle[3], bool edge1_included = false, bool edge2_included = false, bool edge3_included = false){    Vertex v0 = triangle[1] - triangle[0];    Vertex v1 = triangle[2] - triangle[0];    Vertex v2 = vertex - triangle[0];    double dot00 = dot_product(v0, v0);    double dot01 = dot_product(v0, v1);    double dot02 = dot_product(v0, v2);    double dot11 = dot_product(v1, v1);    double dot12 = dot_product(v1, v2);    double inverse_divider = 1 / (dot00 * dot11 - dot01 * dot01);    double u = (dot11 * dot02 - dot01 * dot12) * inverse_divider;    double v = (dot00 * dot12 - dot01 * dot02) * inverse_divider;    return (   ((u > 0) || (u == 0 && edge3_included)) &&   ((v > 0) || (v == 0 && edge1_included)) &&   (((u + v) < 1) || ((u + v) == 1 && edge2_included))    );}bool triangle_overlaps_triangle(Vertex triangle1[3], Vertex triangle2[3], bool edge1_included = false, bool edge2_included = false, bool edge3_included = false){    for (unsigned int i = 0; i < 3; i++)    {   if (point_inside_triangle(triangle1, triangle2, edge1_included, edge2_included, edge3_included))   {  return true;   }    }    return false;}bool convex_overlaps_triangle(unsigned int n, Vertex *convex, Vertex triangle[3], bool edge1_included = false, bool edge2_included = false, bool edge3_included = false){    for (unsigned int i = 0; i < n; i++)    {   if (point_inside_triangle(convex, triangle, edge1_included, edge2_included, edge3_included))   {  return true;   }    }    return false;}bool triangle_overlaps_convex(Vertex triangle[3], unsigned int n, Vertex *convex){    if (n > 2) // has it got any surface?    {   unsigned int changing = 0,  // next changing vertex of convex triangle cw_i = 1, // current vertex clockwise ccw_i = n - 1; // current vertex counter clockwise   Vertex convex_triangle[3] = {convex[0], convex[1], convex[n - 1]};   bool is_cw[3] = {true, true, false}; // which convex triangle vertices do currently use cw or ccw value   unsigned int included_edge = 0;   // go through all neccessary triangles within the convex to cover the whole convex   for (unsigned int i = 0; i < (n - 2); i++) // n - 2 triangles   {  if (i)  { if (is_cw[changing]) {ccw_i--;convex_triangle[changing] = convex[ccw_i];is_cw[changing] = false; } else {cw_i++;convex_triangle[changing] = convex[cw_i];is_cw[changing] = true; } changing++; if (changing == 3) {changing = 0; }  }  if (i || i < (n - 3))  { if ((included_edge == 0 && triangle_overlaps_triangle(triangle, convex_triangle, true,  false, false)) ||(included_edge == 1 && triangle_overlaps_triangle(triangle, convex_triangle, false, true,  false)) ||(included_edge == 2 && triangle_overlaps_triangle(triangle, convex_triangle, false, false, true )) ) {return true; } included_edge++; if (included_edge == 3) {included_edge = 0; }  }  else if ( (!i &&(    (n != 3 && triangle_overlaps_triangle(triangle, convex_triangle, true,  false, true )) ||    (n == 3 && triangle_overlaps_triangle(triangle, convex_triangle, false, false, false))) ) || (i &&(included_edge == 0 && triangle_overlaps_triangle(triangle, convex_triangle, true,  false, true )) ||(included_edge == 1 && triangle_overlaps_triangle(triangle, convex_triangle, true,  true,  false)) ||(included_edge == 2 && triangle_overlaps_triangle(triangle, convex_triangle, false, true,  true )) )  )  { return true;  }   }    }    return false;}bool convex_overlaps_convex(unsigned int n1, Vertex *convex1, unsigned int n2, Vertex *convex2){    if (n1 > 2 && n2 > 2) // has it got any surface?    {   unsigned int changing = 0,  // next changing vertex of convex triangle cw_i = 1, // current vertex clockwise ccw_i = n2 - 1; // current vertex counter clockwise   Vertex convex_triangle[3] = {convex2[0], convex2[1], convex2[n2 - 1]};   bool is_cw[3] = {true, true, false}; // which convex triangle vertices do currently use cw or ccw value   unsigned int included_edge = 0;   // go through all neccessary triangles within the convex to cover the whole convex   for (unsigned int i = 0; i < (n2 - 2); i++) // n - 2 triangles   {  if (i)  { if (is_cw[changing]) {ccw_i--;convex_triangle[changing] = convex2[ccw_i];is_cw[changing] = false; } else {cw_i++;convex_triangle[changing] = convex2[cw_i];is_cw[changing] = true; } changing++; if (changing == 3) {changing = 0; }  }  if (i || i < (n2 - 3))  { if ((included_edge == 0 && convex_overlaps_triangle(n1, convex1, convex_triangle, true,  false, false)) ||(included_edge == 1 && convex_overlaps_triangle(n1, convex1, convex_triangle, false, true,  false)) ||(included_edge == 2 && convex_overlaps_triangle(n1, convex1, convex_triangle, false, false, true )) ) {return true; } included_edge++; if (included_edge == 3) {included_edge = 0; }  }  else if ( (!i &&(    (n2 != 3 && convex_overlaps_triangle(n1, convex1, convex_triangle, true,  false, true )) ||    (n2 == 3 && convex_overlaps_triangle(n1, convex1, convex_triangle, false, false, false))) ) || (i &&(included_edge == 0 && convex_overlaps_triangle(n1, convex1, convex_triangle, true,  false, true )) ||(included_edge == 1 && convex_overlaps_triangle(n1, convex1, convex_triangle, true,  true,  false)) ||(included_edge == 2 && convex_overlaps_triangle(n1, convex1, convex_triangle, false, true,  true )) )  )  { return true;  }   }    }    return false;}