Самопересечение полилинии

Question

Я пишу код, чтобы определить, является ли полилиния самопересекающейся или нет.
Если хотя бы два звена полилинии пересекаются (в своих внутренних точках), она называется самопересекающейся.
Для начала я пишу функцию для определения пересечения двух пересекающихся отрезков. Там я использую школьную формулу прямой 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;
}

Затем, испытав сбой на этом коде, я решил изменить логику функции пересечения и сделал что-то вроде:

      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.

Скорее всего проблема в цикле for в функцииf. Я уже все перепробовал. Я также пробовал это:

      for (int i = 0; i < n - 1; i ++)
        for (int j = i + 2; i < n; j ++)

К сожалению, это не помогло.

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

Answer 1

Боюсь, что вы не всегда можете проверить это локально. В приведенном ниже примере невозможно сказать, есть пересечение или нет, не зная порядка ссылок.

Еще один неприятный случай — когда конечная точка попадает «на» ссылку, и из-за числовых неточностей может быть обнаружено ноль или два пересечения, или, что еще хуже, только одно. И добавление допусков не помогает!

---

Чтобы решить эти сложные случаи, вы должны сначала выяснить точную причину, по которой вы хотите обнаружить эти самопересечения. Потому что правильные решения зависят от приложения.