3

Перед написанием вопроса читал похожую на SO статью, но мне интересно разобраться в чем именно у меня проблема.

Пишу код для определения самопересекается ли ломаная или нет.
Если хотя бы два звена ломаной пересекаются (в своих внутренних точках), её называют самопересекающейся.
Для начала пишу функцию для определения пересечения двух отрезков intersect. Там использую школьную формулу прямой y = kx + b.

А далее функцию f, где проверяю каждые 2 точки 2х отрезков на пересечение. Впринципе все работает, но код ломается при случае, когда какая-то часть ломаной не то чтобы пересекает, а просто "касается" какого-нибудь другого отрезка данной ломаной. Например, как на тесте: Тест:

4   
0 0   
2 2   
2 1   
1 1  

Код:

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("input.txt");
ofstream fout("output.txt");

class peresec{
    public:
        double x,y;
};

int intersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
{
    double k1, k2, b1, b2, x, y, tmp;

    if(x1>=x2) {tmp=x1; x1=x2; x2=tmp; tmp=y1; y1=y2; y2=tmp;}
    if(x3>=x4) {tmp=x3; x3=x4; x4=tmp; tmp=y3; y3=y4; y4=tmp;}

    if(y1==y2) k1=0; else k1 =  ( y2 - y1 ) / ( x2 - x1 );
    if(y3==y4) k2=0; else k2 =  ( y4 - y3 ) / ( x4 - x3 );
    if(k1 == k2) return 0;
   
    b1=y1-k1*x1;
    b2=y3-k2*x3;

    x = (b2-b1)/(k1-k2);
    y = k1*x + b1;

    if(x1<=x && x3<=x && x2>=x && x4>=x && !((x==x1 && y==y1) || (x==x2 && y==y2) || (x==x3 && y==y3) || (x==x4 && y==y4)))
        {return 1;}
    else
        return 0;
}

void f(peresec *a, int n)
{
    int flag;

    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
        {
            flag=intersect(a[i].x, a[i].y, a[(i + 1) % n].x, a[(i + 1) % n].y, a[j].x, a[j].y, a[(j + 1) % n].x, a[(j + 1) % n].y);
            if(flag==1) {fout << 1; return;}
        }
    if(flag == 0){fout << 0; return;}
}

int main()
{
    long long count;
    peresec *a;
     if( !(fin >> count)){fout<<0; return 0;}
     fin.seekg(0);
    
    
     fin >> count;
     if(count == 0) {fout<<0; return 0;}
    
     a = new peresec[count];
    for(int  i = 0; i < count; i++){ fin >> a[i].x; fin >> a[i].y;}

    f(a,count);

    return 0;
}

Также испытав провал на данном коде решил поменять логику функции intersect и сделал что-то вроде:

bool intersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
{
    double v1, v2, v3, v4;
    v1=(x4-x3)*(y1-y3)-(y4-y3)*(x1-x3);
    v2=(x4-x3)*(y2-y3)-(y4-y3)*(x2-x3);
    v3=(x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
    v4=(x2-x1)*(y4-y1)-(y2-y1)*(x4-x1);
    if((v1*v2<0) && (v3*v4<0)) return true;
    else return false;
}

Но и тут на данном тесте код ломается. Должно выводиться 1, иначе 0. Т.к если пересекает должно выводиться 1.

Скорее всего проблема в цикле в функции f и по каким вершинам прохожусь. Все уже перепробовал.

Можете объяснить почему ломается код???

8
  • На каком тесте ломается ваш код? 26 сен 2022 в 21:47
  • Я прописал в самом вверху ,выше кода
    – Stan
    26 сен 2022 в 22:04
  • Вы хотели чтобы при касании выводился ноль. Он и выводится. 26 сен 2022 в 22:29
  • 1
    А если во втором коде изменить < на <= ?
    – MBo
    27 сен 2022 в 2:12
  • 1
    добавь в вопрос определение: что такое "самопересечение".
    – Grundy
    27 сен 2022 в 7:34

1 ответ 1

1

Используйте второй код с <= вместо < и измените циклы так, чтобы для соседних отрезков не проводилась проверка.

for (int i=0; i<n-2; i++)
    for (int j=i+2; j<n-1; j++)
    {
        flag=intersect...

Проверочка: тест выдаёт 0 для последней точки (4,3) и 1 для последней точки (1,1) или (2,0)

class peresec {
public:
    double x, y;
};

bool intersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
{
    double v1, v2, v3, v4;
    v1 = (x4 - x3)*(y1 - y3) - (y4 - y3)*(x1 - x3);
    v2 = (x4 - x3)*(y2 - y3) - (y4 - y3)*(x2 - x3);
    v3 = (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1);
    v4 = (x2 - x1)*(y4 - y1) - (y2 - y1)*(x4 - x1);
    if ((v1*v2 <= 0) && (v3*v4 <= 0)) return true;
    else return false;
}

void f(peresec *a, int n)
{
    for (int i = 0; i < n - 2; i++)
        for (int j = i + 2; j < n - 1; j++)
        {
            if (intersect(a[i].x, a[i].y, a[i + 1].x, a[i + 1].y, 
                          a[j].x, a[j].y, a[j + 1].x, a[j + 1].y))
            {
                cout << i << " " << j << "  "<< 1;
                return;
            }
        }
    cout << 0;
    return;
}

int main()
{
    long long count;
    peresec *a;
    count = 4;
    a = new peresec[count];
    a[0].x = 0; a[0].y = 0;
    a[1].x = 2; a[1].y = 2;
    a[2].x = 2; a[2].y = 1;
    a[3].x = 4; a[3].y = 4;
    //a[3].x = 1;   a[3].y = 1;

    f(a, count);

    return 0;
}
1
  • Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
    – Grundy
    29 сен 2022 в 9:00

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.