Find point where a line of multiple vertices overlaps itself Since I'm not familiar with a lot of mathematical terminology, I will explain this problem with a little story.
Imagine you and your friend Anne have a piece of string each, and place it on a coordinate system. You decide to form a loop with your string, so the string will overlap itself at some point on the coordinate system.
Now both you travel along the string with a marker, and after every centimeter, you note down the coordinates of that Point.
Once you are done, you will have two lists of vertices that are on their respective strings. From looking just at these lists, how can I find out which one of them contains a loop using mathematics? Furthermore, how can I find the exact coordinates of the point of intersection (this point may not be part of the listed vertices, as this list has a 'resolution' of one centimeter)?
Here is a little MS Paint thing I made to illustrate the problem.

I think you're going to have to make some assumptions here. There can certainly be examples of lists which could represent both overlapping and non-overlapping strings, as there are lots of choices of strings to interpolate the points, and we may have that only some of them cause a self-intersection. There will be cases (such as in your illustration) in which this ambiguity does not arise, but there still may be many possible points of intersection.
If you make the assumption that the string follows a straight line between the sampled points (a reasonable assumption if your step size is sufficiently small), the above problem goes away, and there is an easy solution; for each of the line segments (consecutive pairs of sampled points), you simply test if it overlaps any other line segment. If so, you can find the point of intersection between the line segments; if not, the string does not self-intersect.
