Algorithm for finding self-intersections of a two-dimensional contour

Question

C++ / C#

There is a contour in the standard representation for computer vision tasks, a vector of points.

It is required to find the coordinates of its self-intersection points, and quickly.

So far, from what I found / thought of:
1. Find a rectangle described around the contour.
2. Create an array the size of this rectangle
3. And draw a contour point by point there
4. Checking if the new point falls exactly on the first line
5. And if there are others nearby, in case of diagonal combing.

Can more effectively check the neighborhood after rendering if the outline is dense.

The development is in C ++ under OpenCV, but, of course, is ready to accept in other languages, verbal descriptions and just links

Answer 1

It is better to check pairs of segments for intersection.
Of course, it is not necessary to check neighboring segments, as well as already checked pairs.
There will also be a problem if two segments partially coincide: then the set of intersection points is infinite.
You can read about checking segments on RSDN , where there are code examples. Or googling something else.

Answer 2

A purely mathematical approach:
http://www.exponenta.ru/educat/systemat/lapteva/3a.asp
I don’t know if it will work with discrete data, but at first glance it is quite feasible

Answer 3

A simple but slow solution is to check all pairs of segments for intersection. This works for the quadratic complexity of the number of segments in the contour.
Checking the intersection of two segments is quite simple. You can intersect 2 straight lines given parametrically (2 linear equations, solution on a piece of paper), and then check that the intersection point on each straight line is inside the segment (you can set a parametric equation of a straight line so that the segment corresponds to parameters from 0 to 1). Another, faster way is with the cross product. It is necessary to check that the points of each segment lie on opposite sides of the line on which the other segment lies.
There is a complicated, but faster solution to the problem - with the help of a sweeping line. It is described in detail here: e-maxx.ru/algo/intersecting_segments
Runs in O(n log n), where n is the number of segments. True, it will have to be slightly corrected so as not to take into account the intersections of adjacent segments.