Даны два треугольника на плоскости – ABC и DEF определяются координатами своих вершин: А(1,1), B(2,2), C(3,4), D(2,1), E(1,3), F(3,3). Определить, пересекаются эти треугольники или нет.
Каков алгоритм определения, пересекаются или нет? =(
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуДаны два треугольника на плоскости – ABC и DEF определяются координатами своих вершин: А(1,1), B(2,2), C(3,4), D(2,1), E(1,3), F(3,3). Определить, пересекаются эти треугольники или нет.
Каков алгоритм определения, пересекаются или нет? =(
Надо найти пересечение отрезков сторон треугольников каждой с каждой. Будет 8 проверок в худшем случае.
Можно проверить на нахождение точек в треугольнике (для пересечения должны находиться 1-2 точки внутри другого треугольника), в худшем случае 6 проверок. тут обсуждают "Точка в треугольнике"
Вот изобрел способ проверки пересечения 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;
}