Given two triangles on the plane - ABC and DEF are determined by the coordinates of their vertices: A (1,1), B (2,2), C (3,4), D (2,1), E (1,3), F (3.3). Determine whether these triangles intersect or not.

What is the algorithm for determining whether they intersect or not? = (

  • ow.com/questions/1585459/whats-the-most-efficient-way-to-detect-triangle-triangle- - Costantino Rupert

3 answers 3

It is necessary to find the intersection of the segments of the sides of the triangles of each with each. There will be 8 checks in the worst case.

    You can check for finding points in the triangle (for the intersection there should be 1-2 points inside another triangle), in the worst case 6 checks. Here they discuss "Point in the triangle"

    • Does the "check for finding points in a triangle" work in the case when the points are not included in triangles? - monty
    • @IVsevolod which points will we choose? if we are talking about vertices, then for the "Star of David" there will be a false result ... - Yura Ivanov
    • And if one triangle is completely inside the second - then checking the intersections will not help - renegator
    • So, to complete the picture, you need to combine two methods. If at least one of them returns true, then there is an intersection. You can also do a preliminary check on [AABB] [1], so as not to run these methods for obviously not intersecting triangles. [1]: gamedev.ru/terms/AABB - fori1ton
    • that's right, you need a combination. - Yura Ivanov

    Here invented a way to check the intersection of 2D shapes of any shape. It can be easily redone (the checkCrossing function) in order to find out how many times one shape crosses the other and where it crosses the coordinates. I don’t know how effective such an algorithm is.

    #include <iostream> #include <vector> using namespace std; struct point{ double x, y; bool operator == (const point p){ if ((x == px) && (y == py)) return true; else return false; } } p; vector<point> buf; void linesArray(double x1, double y1, double x2, double y2) { const double deltaX = abs(x2 - x1); const double deltaY = abs(y2 - y1); const double signX = x1 < x2 ? 1 : -1; const double signY = y1 < y2 ? 1 : -1; double error = deltaX - deltaY; px = x2; py = y2; buf.push_back(p); while(x1 != x2 || y1 != y2) { px = x1; py = y1; buf.push_back(p); const double error2 = error * 2; if(error2 > -deltaY) { error -= deltaY; x1 += signX; } if(error2 < deltaX) { error += deltaX; y1 += signY; } } } bool checkCrossing(){ // функция вернет истину если один многоугольник пересекается с другим for (unsigned int i = 0; i < buf.size(); i++){ for (unsigned int j = 0; j < buf.size(); j++){ if ((buf[i] == buf[j]) && (i != j)) return true; } } return false; } int main() { // загружаем стороны 1 многоугольника linesArray(1.0, 1.0, 2.0, 2.0); // A и B linesArray(2.0, 2.0, 3.0, 4.0); // B и C linesArray(3.0, 4.0, 1.0, 1.0); // C и A // загружаем стороны 2 многоугольника linesArray(2.0, 1.0, 1.0, 3.0); // D и E linesArray(1.0, 3.0, 3.0, 3.0); // E и F linesArray(3.0, 3.0, 2.0, 1.0); // F и D // проверяем на пересечение if (checkCrossing()) cout << "yes crossing" << endl; else cout << "No crossing" << endl; buf.clear(); // ещо проверка (тест - должно совпасть) linesArray(1.0, 0.0, -1.0, 0.0); linesArray(0.0, -1.0, 0.0, 1.0); // проверяем на пересечение if (checkCrossing()) cout << "yes crossing" << endl; else cout << "No crossing" << endl; buf.clear(); // ещо проверка (тест - не должно совпасть) linesArray(1.0, -1.0, -1.0, -1.0); linesArray(1.0, 1.0, -1.0, 1.0); // проверяем на пересечение if (checkCrossing()) cout << "yes crossing" << endl; else cout << "No crossing" << endl; return 0; }

    _NEW FIXED CODE _ _ _ _ _ __

     #include <iostream> #include <vector> using namespace std; struct point{ double x, y; bool operator == (const point p){ if ((x == px) && (y == py)) return true; else return false; } } p; vector<point> buf; void round (double & x, int precision){ // ДОБАВЛЕНО int res = 1; for (int i = 0; i < precision; i++){ res *= 10; } x = x * res; } // точьность (сколько знаков после запятой)!!!! void linesArray(double x1, double y1, double x2, double y2, int precision = 1) { round(x1, precision); // ДОБАВЛЕНО round(y1, precision); // ДОБАВЛЕНО round(x2, precision); // ДОБАВЛЕНО round(y2, precision); // ДОБАВЛЕНО const double deltaX = abs(x2 - x1); const double deltaY = abs(y2 - y1); const double signX = x1 < x2 ? 1 : -1; const double signY = y1 < y2 ? 1 : -1; double error = deltaX - deltaY; px = x2; py = y2; buf.push_back(p); while((x1 != x2) || (y1 != y2)) { px = x1; py = y1; buf.push_back(p); const double error2 = error * 2; if(error2 > -deltaY) { error -= deltaY; x1 += signX; } if(error2 < deltaX) { error += deltaX; y1 += signY; } } } bool checkCrossing(){ // функция вернет истину если один многоугольник пересекается с другим for (unsigned int i = 0; i < buf.size(); i++){ for (unsigned int j = 0; j < buf.size(); j++){ if ((buf[i] == buf[j]) && (i != j)) return true; } } return false; } int main() { // загружаем стороны 1 многоугольника linesArray(1.0, 1.0, 2.0, 2.0); // A и B linesArray(2.0, 2.0, 3.0, 4.0); // B и C linesArray(3.0, 4.0, 1.0, 1.0); // C и A // загружаем стороны 2 многоугольника linesArray(2.3, 1.3, 1.0, 3.0); // D и E linesArray(1.0, 3.0, 3.0, 3.0); // E и F linesArray(3.0, 3.0, 2.3, 1.3); // F и D // проверяем на пересечение if (checkCrossing()) cout << "yes crossing" << endl; else cout << "No crossing" << endl; buf.clear(); // ещо проверка (тест - должно совпасть) linesArray(1.0, 0.0, -1.0, 0.0); linesArray(0.0, -1.0, 0.0, 1.0); // проверяем на пересечение if (checkCrossing()) cout << "yes crossing" << endl; else cout << "No crossing" << endl; buf.clear(); // ещо проверка (тест - не должно совпасть) linesArray(1.0, -1.0, -1.0, -1.0); linesArray(1.0, 1.0, -1.0, 1.0); // проверяем на пересечение if (checkCrossing()) cout << "yes crossing" << endl; else cout << "No crossing" << endl; return 0; }
    • Why are you minus without comments? - perfect
    • This is a hard case just. Run with: // load sides 1 of the polygon linesArray (1.1, 1.1, 2.0, 2.0); // A and B linesArray (2.0, 2.0, 3.0, 4.0); // B and C linesArray (3.0, 4.0, 1.1, 1.1); // C and A // load sides 2 of the polygon linesArray (2.3, 1.3, 1.0, 3.0); // D and E linesArray (1.0, 3.0, 3.0, 3.0); // E and F linesArray (3.0, 3.0, 2.3, 1.3); // F and D - Yura Ivanov
    • corrected the code, now you can set the accuracy of calculations (linesArray function -> last argument - how many characters are used after the comma). Please rate - perfect
    • Any strange algorithm if accuracy of record of number is basic for it? What is its essence? I am not very much in C. - ReinRaus 4:21 pm
    • 2
      O_O (eyes bulging emoticon) That is, to calculate the intersection of two lines with a size of 1 billion points, we will create two arrays in gigabytes and then go over this array instead of simply adding / subtracting / dividing / comparing? - ReinRaus