[Tex/LaTex] How to get intersection points of a self intersecting path

Question

(Tricky question.) I'm trying to get intersection points of one individual/arbitrary curve instead of searching intersection points among many curves. We can get intersection points of two different curves easily (even of two, the same curves as shown in the example below) in all major TeX-related graphics engines (Metapost, PSTricks, Asymptote, TikZ, you name it).

The first example in TikZ (picture on left) demonstrates a trick I'm using. I define a single curve which is then loaded and named as first and second. If curve consists of line segments, we get intersection points right away. After adding the sort by parameter, we get proper points of both curves and after using only odd/even intersection points (1,3,...) in the loop, we get intersection points of a single curve. Still, the result is incorrect as points 3 and 5 consist the end or the beginning of two consecutive line segments.

Solution would be to split this curve into many line segments (individual curves) and compare them in two, inner+outer \foreach cycles excluding the connection points between line segments (in practice comparison would be: the second line segment with the first one, the third segment with the previous two etc.).

• The first line segment would consist of (0,0)--(3,0),
• the second line segment would consist of (3,0)--(2,1), and,
• the third one would consist of this portion of the original curve (2,1)--(1,-1).

There is only one solution, point 1. It would require some programming, but it can be done.

But how to solve the case of the Bézier curves? Let me demonstrate it on the next example (picture on right). In this situation, we are getting many intersection points as curves lie on each other again, we could use those points (distance between them, if I'm not mistaken, is 1pt, to draw a lot of line segments. Maybe we could use window test, that's probably our best shot. In practice, I use a set of individual curves, which don't cross themselves, but isn't there a better approach how to get all intersection points of a single curve?

In the second example, there is only one solution: crossing is located nearby point 113.

% *latex mal-intersections.tex
% (It takes a couple of seconds to get PDF.)
\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage{tikz}
\usetikzlibrary{intersections}

\begin{document}
\begin{tikzpicture} % Curve consists from line segments.
\def\thecurve{ (0,0)--(3,0)--(2,1)--(1,-1) } 
\draw[name path=first] \thecurve;
\draw[name path=second] \thecurve;
\fill [name intersections={of=first and second, name=i, total=\t, sort by=first}]
[red, opacity=0.5, every node/.style={above, black, opacity=1}]
\foreach \s in {1,3,...,\t}{(i-\s) circle (2pt) node {\footnotesize\s}};
\end{tikzpicture}
%
\begin{tikzpicture} % A single Bézier curve.
\def\thecurve{ (0,0) .. controls (5,1) and (0,3) .. (2,-1) } 
\draw[name path=first] \thecurve;
\draw[name path=second] \thecurve;
\fill [name intersections={of=first and second, name=i, total=\t, sort by=first}]
[red, opacity=0.5, every node/.style={above, black, opacity=1}]
\foreach \s in {1,9,...,\t}{(i-\s) circle (2pt) node {\tiny\s}};
\end{tikzpicture}
\end{document}

Answer 1

A trick which seems to work here: searching the intersection of the curve… and its reverse. Applied with MetaPost.

u := 3cm;
path curve[];
curve1 = ((0,0)--(3,0)--(2,1)--(1,-1)) scaled u;
curve2 = ((0,0) .. controls (5,1) and (0,3) .. (2,-1)) scaled u;

def self_intersection(expr curve) = 
  draw curve;
  drawdot curve intersectionpoint reverse curve withpen pencircle scaled 6bp;
enddef;

beginfig(1);
  self_intersection(curve1);
  self_intersection(curve2 shifted (3.5u, 0));
endfig;
end.

The same idea seems to also work with TikZ:

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{intersections}

\begin{document}

\begin{tikzpicture}
\draw[name path=curve1] 
  (0,0) -- (3,0) -- (2,1) -- (1,-1);
\path[name path=curve1r] 
  (1,-1) -- (2,1) -- (3,0) -- (0,0);
\path[name intersections={of=curve1 and curve1r, by={a}}]
  node[fill,circle,inner sep=1.5pt] at (a) {};  
\begin{scope}[xshift=4cm]
\draw[name path=curve2] 
  (0,0) .. controls (5,1) and (0,3) .. (2,-1);
\path[name path=curve2r] 
  (2,-1) .. controls (0,3) and (5,1) .. (0,0);
\path[name intersections={of=curve2 and curve2r, by={b}}]
  node[fill,circle,inner sep=1.5pt] at (b) {};  
\end{scope}
\end{tikzpicture}

\end{document}