折线自相交

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;
}

然后，在经历了这段代码的失败之后，我决定改变 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。

问题很可能出在函数

f

的 for 循环中。我已经尝试过一切。 我也尝试过这个：

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

不幸的是，这没有帮助。

你能解释一下为什么代码会崩溃吗？？？

Answer 1

恐怕你不能总是在本地测试这个。在下面的例子中，如果不知道链接的顺序，就不可能判断是否存在交叉。

另一种令人讨厌的情况是，当端点落在链接“上”时，由于数字不准确，可能会检测到零个或两个交叉点，或者更糟糕的是，只有一个。并且增加公差没有帮助！

---

为了解决这些困难的情况，您必须首先询问您想要检测这些自相交的确切原因。因为正确的决定取决于应用程序。

Answer 2

这似乎是您在编程平台上见过的编码问题。你可以看看这个。并且请提供您遇到此问题的资源。如果可能，请提供您的问题的链接。这有助于更轻松地回答您的问题。