Polyline self-intersection

Question

I am writing code to determine if a polyline is self-intersecting or not.
If at least two links of a polyline intersect (at their internal points), it is called self-intersecting.
To begin with, I write a function to determine the intersection of two intersect segments. There I use the school straight line formula y = kx + b.

And then the function f, where I check every 2 points of 2 segments for intersection. In principle, everything works, but the code breaks when some part of the polyline does not exactly intersect, but simply "touches" some other segment of this polyline. For example, as in the test:

Test:

Code:

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

Then, having experienced a failure on this code, I decided to change the logic of the intersect function and did something like:

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

But even here the code breaks on this test. Should output 1 if there is a self-intersection, otherwise 0.

Most likely the problem is in the for loop in the function f. I've already tried everything. I also tried this:

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

Unfortunately, it did not help.

Can you explain why the code breaks???

On what input data does the code with your second implementation of `intersect` fail? (I just ran it on the test you posted, and it worked fine (output 0)). One thing to watch out for is that floating points are not real numbers, and so you cannot in general solve an equation two different ways and get equal (`==`) answers. If two segments are collinear or just "touch", you might get false positives. The program might calculate that they intersect when they really don't. — jcarpenter2, Sep 28 '22 at 01:35
Also I think your first implementation of `intersect` will have problems with vertical segments, `k` will end up being infinity. Your second implementation looks right to me (at least for segments that do not just touch) (but don't take my word for it). — jcarpenter2, Sep 28 '22 at 01:43
On the second program, code fails so often than first program. For example, 4 0 0 2 2 2 1 4 3, output is 1. But it no have self intersections. There are no such problem on the first program. @jcarpenter2 — Murad Mammadzada, Sep 28 '22 at 04:50
If it has self intersections, output is 1, otherwise output 0. Test that i posted has self intersection, so it should output 1. You can see it if you draw it. @jcarpenter2 — Murad Mammadzada, Sep 28 '22 at 04:54
Are you including the line between the last point and the first point? In that example, `4 3 0 0` (last-to-first) intersects `2 2 2 1` (second-to-third). It outputs 1 correctly for me. — jcarpenter2, Sep 28 '22 at 04:55
If you need to handle the case where a segment "touches" another segment, you shouldn't use `double`, you should use `int` if all the coordinates are integers or some fractional type (find a library or write your own) if you have fractional coordinates. Doubles are not good for exact arithmetic, e.g. `cout << (0.1 + 0.2 == 0.3)` (try it!). But aside from that, if you post a case where the "touching" logic is wrong, maybe we can help you debug it and see if double arithmetic is the problem or if something else is. — jcarpenter2, Sep 28 '22 at 04:59
@jcarpenter2: switching to int does not help, unless you perform arithmetic using a longer integer type. — , Sep 28 '22 at 08:30

score 0 · Answer 1 · 2022-09-28T08:33:46.863

0

I am afraid that you cannot always test this locally. In the example below, it is impossible to tell if there is a crossing or not without knowing the order of the links.

Another nasty case is when an endpoint falls "on" a link, and due to numerical inaccuracies, there could be zero or two intersections detected, or, even worse, only one. And adding tolerances does not help !

In order to resolve these difficult cases, you must first question the exact reason why you want to detect those self-intersections. Because the correct decisions are application-dependent.

edited Sep 28 '22 at 08:33

answered Sep 28 '22 at 08:17

First of all, one doesn't have to calculate intersection point to detect its existence. – Will Ness Oct 01 '22 at 01:25
@WillNess: first of all, who said that it was calculated in the above discussion ? – Oct 01 '22 at 06:40
"there could be zero or two intersections detected, or, even worse, only one" I think "one" implies it. – Will Ness Oct 01 '22 at 11:26
@WillNess: I said *detected* on purpose. Please pay attention. A useful contribution of yours would be appreciated. – Oct 01 '22 at 12:08

Polyline self-intersection

1 Answers1