Вычислительная геометрия

Вопрос задан: 6 лет 8 месяцев назад   просмотров: 7
0

Даны два треугольника на плоскости – ABC и DEF определяются координатами своих вершин: А(1,1), B(2,2), C(3,4), D(2,1), E(1,3), F(3,3). Определить, пересекаются эти треугольники или нет.

Каков алгоритм определения, пересекаются или нет? =(

ow.com/questions/1585459/whats-the-most-efficient-way-to-detect-triangle-triangle- - 19-06-2013 в 13:10:52

Ответы   3

0

Надо найти пересечение отрезков сторон треугольников каждой с каждой. Будет 8 проверок в худшем случае.

Ответил: 19-06-2013 в 01:39:35
0

Можно проверить на нахождение точек в треугольнике (для пересечения должны находиться 1-2 точки внутри другого треугольника), в худшем случае 6 проверок. тут обсуждают "Точка в треугольнике"

Ответил: 19-06-2013 в 08:39:58
А разве "проверка нахождения точек в треугольнике" работает в том случае, когда точки не входят в треугольники? - 19-06-2013 в 11:34:30
@IVsevolod какие точки будем выбирать? если речь о вершинах, то для "звезды давида" будет ложный результат... - 19-06-2013 в 13:28:20
А если один треугольник целиком внутри второго - то проверка пересечений не поможет - 19-06-2013 в 13:36:17
Значит, для полноты картины нужно комбинировать два метода. Если хоть один из них вернул true, то пересечение есть. Можно ещё делать предварительную проверку по [AABB][1], чтобы не запускать эти методы для заведомо не пересекающихся треугольников. [1]: gamedev.ru/terms/AABB - 19-06-2013 в 13:44:13
все верно, нужна комбинация. - 19-06-2013 в 13:58:25
0

Вот изобрел способ проверки пересечения 2D фигур любой формы. Его можно легко переделать (функция checkCrossing) для того чтобы узнавать сколько раз пересекает одна фигура другую и координаты где пересекает. Не знаю правда насколько эффективен такой алгоритм.

#include <iostream> #include <vector> using namespace std; struct point{ double x, y; bool operator == (const point p){ if ((x == p.x) && (y == p.y)) 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; p.x = x2; p.y = y2; buf.push_back(p); while(x1 != x2 || y1 != y2) { p.x = x1; p.y = 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; }

_НОВЫЙ ИСПРАВЛЕННЫЙ КОД_______

#include <iostream> #include <vector> using namespace std; struct point{ double x, y; bool operator == (const point p){ if ((x == p.x) && (y == p.y)) 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; p.x = x2; p.y = y2; buf.push_back(p); while((x1 != x2) || (y1 != y2)) { p.x = x1; p.y = 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; }
Ответил: 20-06-2013 в 13:35:52
почему минусуете без комментариев? - 20-06-2013 в 14:07:29
Это тяжелый случай просто. Запустите с: // загружаем стороны 1 многоугольника linesArray(1.1, 1.1, 2.0, 2.0); // A и B linesArray(2.0, 2.0, 3.0, 4.0); // B и C linesArray(3.0, 4.0, 1.1, 1.1); // 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 - 20-06-2013 в 14:49:22
исправил код, теперь можно задавать точность вычислений (функция linesArray -> последний аргумент - сколько знаков используется после запятой). прошу оценить - 20-06-2013 в 18:11:13
Какой-то странный алгоритм, если для него принципиальна точность записи числа? В чем его суть? Я не очень в Си. - 20-06-2013 в 20:21:39
О_О (смайлик выпученных глаз) То есть для расчета пересечения двух линий размером 1 млрд точек мы создадим два массива по гигабайту и потом пробежимся по этому массиву, вместо того, чтобы просто сложить/отнять/разделить/сравнить ? - 20-06-2013 в 22:53:54