22

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

An example demonstrating the situation.

20

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.

enter image description here

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}

enter image description here

5
  • 5
    +1. I took the liberty of editing your answer to add the TikZ version of your idea (it seemed pointless to provide an independent answer, since the idea was yours). I hope it is OK, but if not, just let me know to undo the editing. Apr 3 '15 at 1:25
  • @Gonzalo Medina Personally I think that you should make an independent answer containing this code: the fact that you used another drawing middle than mine is in my opinion quite sufficient to justify this, even if the idea behind your answer is the same as mine. Apr 3 '15 at 9:25
  • 1
    Knuth recommends this approach in the answer to Exercise 14.17 in The METAFONTbook. It is (apparently) the reason for METAFONT's "shuffled-binary search procedure" for finding intersections, that is explained on p.137.
    – Thruston
    Apr 3 '15 at 18:53
  • 1
    @Thruston I've got the book, and yet I overlooked this exercise completely. Surely the two double-bend signs frightened me. I'm proud to see I've reached this level of “Metaness” without being aware of it :-) Apr 3 '15 at 19:09
  • With TikZ this method can fail spectacularly on a grid-curve, giving many false positives (in fact, it seems we get one "intersection" for each grid-point where the curve is not smooth).
    – User12345
    May 28 '20 at 21:53
1

I must admit that I was quite astonished to discover this question and that the accepted answer works. I need to look up the details of the algorithm to understand why!

Not knowing of this feature of the algorithm by which MetaPost and PGF find intersections, for the knots library then I implemented a method of finding self intersections that works by exploding a path into sub-paths and then finding the intersections between those.

On further analysis, I'm not going to replace my algorithm with the above because when I ran the code from the accepted answer and compared it with mine then there is a significant difference in the length of time it takes to compile.

lualatex selfintersection.tex  88.85s user 1.84s system 96% cpu 1:33.89 total
lualatex selfintersection.tex  4.56s user 1.50s system 95% cpu 6.374 total

Obviously, this is just one example.

My code is as follows, it uses version 2.0 of the spath3 package (released on 2021-01-22):

\documentclass{article}
%\url{https://tex.stackexchange.com/q/236550/86}

\usepackage{tikz}
\usetikzlibrary{intersections, spath3}

\begin{document}

\begin{tikzpicture}
\draw[spath/save=lines]  (0,0)--(3,0)--(2,1)--(1,-1) ;

\tikzset{
  spath/split at self intersections=lines,
  spath/get components of={lines}\lcpts
}

\foreach[count=\k] \cpt in \lcpts
{
  \fill[red, opacity=0.5] (spath cs:{\cpt} 1) circle[radius=2pt] node[above, black, opacity=1] {\(\k\)};
}
\end{tikzpicture}

\begin{tikzpicture} % A single Bézier curve.
\draw[spath/save=curve]  (0,0) .. controls (5,1) and (0,3) .. (2,-1);
\path[overlay, spath/save=marker] (spath cs:curve .5) +(-.2,-.2) -- +(.2,.2);
\tikzset{
  spath/split at intersections={curve}{marker},
  spath/spot weld=curve,
  spath/split at self intersections=curve,
  spath/get components of={curve}\ccpts
}

\foreach[count=\k] \cpt in \ccpts
{
  \fill[red, opacity=0.5] (spath cs:{\cpt} 1) circle[radius=2pt] node[above, black, opacity=1] {\(\k\)};
}
\end{tikzpicture}

\end{document}

It does something slightly different to what the question describes, but hopefully is enough to demonstrate the capability. What it does is to split the path at the points where it self-intersects. That is, if we imagine that the relevant part of the original path was just a straight line from (0,0) to (1,0) and the intersection point was at (.5,0) then the corresponding part of the new path looks like what you get from the path specification:

(0,0) -- (.5,0) (.5,0) -- (1,0)

Once these splits are in place, there is the capability to extract the components of the path and work with them individually, including using them for specifying coordinates. In the above code this means that the intersection point gets used twice (once for each time the path goes through it) and the end of the path also gets marked, but these are simple enough to deal with.

There is one slight hiccough with the bézier curve in that it is specified as a single curve that self-intersects. I do have code to automatically split such a curve, but I appear not to have included that in the split at self intersections code - an oversight that I will remedy. In the meantime, we can introduce another path to split against to make the single bézier into two pieces to simulate this.

Marking self-intersections of paths

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.