Is there a fast algorithm for checking if a polygon line intersects with itself?

Question

Algorithms

There is a polygon defined by some array of points forming straight lines (about 4000). We need to check if these lines intersect with themselves.
The array iteration method in an array takes a very long time. Is there a faster way?

Answer 1

Well, in general, there is a tricky way) You need to create a bitmap (canvas) and draw all these lines there, for example, with alpha 0.5, And then go through all the points and check the alpha coordinate, and if it is at least one pixel more than 0.5, then it means that there is approximately in that place intersection. Naturally, there are many subtleties and settings of this method. And it's not a fact that it will be faster)
Then, when iterating over an array with an array, a double check situation may arise. For example 100x200 and 200x100. You can reduce the calculation time at least a couple of times:

for(var i = 0; i < 4000; i++)
{
    for(var j = i + 1; j < 4000; j++ )
    {
          // check i vs j
    }
}

Answer 2

Are there any features of the polygon known, or can each next vertex be anywhere?
In the general case, a polygon is no different from a set of independent segments, where you have to check each-with-each, except for adjacent neighbors. You can optimize: beat into subgroups, sort, etc.