# How does TikZ sort intersections?

I used the sort by key for intersections to sort along a line, expecting the intersections to be numbered 1 through 5. Why were they numbered 4, 5, 3, 1, 2? Playing around with it, I could not seem to figure out how the order is determined. The code and image follow.

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

\begin{document}
\begin{tikzpicture}
\draw[name path=grid] [xstep=3,ystep=2] (0,0) grid (9,8);
\draw[->, name path=line] (2,1) -- (7,7);
\draw[name intersections={of=grid and line, sort by=line, name=i, total=\t}]
\foreach \s in {1,...,\t}{(i-\s) node {\s}};
\end{tikzpicture}
\end{document}


• It is because how grid is drawn (first horizontals then verticals) screwing up the sorting mechanism. Draw from (1,1) to (8,7) Mar 6 '18 at 13:20
• @percusse Your comment should be an answer! Mar 6 '18 at 19:14
• @percusse That is kind of correct, but actually the sorting algorithm was just wrong. Jun 26 '20 at 2:03

Mini-Update: I looked a bit into the pgflibraryintersections.code.tex file and according to how I understand things now the perhaps simplest option is to draw the line pretending it is a curve. Everything else seems to amount to really improve the intersections library, which is far beyond my capabilities. More specifically, in pgflibraryintersections.code.tex it is written that

Note that the precise time inside of a segment may be unavailable (currently, it is only computed for curveto paths and not necessarily for lineto).

So if you replace the line by a straight curve, that is a line that pretends to be curve, you get the expected ordering 1,2,3,4,5.

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

\begin{document}
\begin{tikzpicture}
\draw[name path=grid] [xstep=3,ystep=2] (9,8) grid (0,0);
\draw[->, name path=line] (2,1) to[bend left=0] (7,7);
\draw[name intersections={of=grid and line, sort by=line, name=i, total=\t}]
\foreach \s in {1,...,\t}{(i-\s) node {\s}};
\end{tikzpicture}
\end{document}


Interestingly, the computation time increases noticeably when doing this. Again, not too surprising given the statement

Note: at the time of this writing, the library has quadratic runtime. Experimentally, it performed well while computing ~12 intersections of two plots, each with 600 samples. It failed when the number of samples exceeded 700.

• Very nice Sherlock! Strange that the term "time" is used. Mar 6 '18 at 0:57
• @Dr.ManuelKuehner I guess that this is sort of a standard jargon for the parameter of a curve. (Gauss was also a physicist, unfortunately only the magnetic field carries his name... ;-)
– user121799
Mar 6 '18 at 1:23
• @marmot Among physicists, indeed it is. There are so many cases in physics where a curve is parametrized by time that we tend to get carried away and call the parameter "time" even when it really isn't. Mar 6 '18 at 3:16
• Well, I almost thought I have it.
• Not an answer but maybe a start for others.

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

% https://tex.stackexchange.com/questions/417485
% Please don't get started :)
% Needed, otherwise color shift (ASdobe Reader, see for yourself)
\pdfpageattr{/Group <</S /Transparency /I true /CS /DeviceRGB>>}

\begin{document}

% ~~~~~~~~
\begin{tikzpicture}
\draw[name path=grid] [xstep=3,ystep=2] (0,0) grid (9,8);
\draw[->, name path=line] (2,1) -- (7,7);
\draw[name intersections={of=grid and line, sort by=line, name=i, total=\t}]
\foreach \s in {1,...,\t}{(i-\s) node {\s}};
\end{tikzpicture}

\section*{Taken from the Manual}
% ~~~~~~~~
\begin{tikzpicture}
\clip (-0.5,-0.75) rectangle (3.25,2.25);
\foreach \pathname/\shift in {line/0cm, curve/2cm}{
\tikzset{xshift=\shift}
\draw [->, name path=curve] (1,1.5) .. controls (-1,1) and (2,0.5) .. (0,0);
\draw [->, name path=line] (0,-.5) -- (1,2) ;
\fill [name intersections={of=line and curve,sort by=\pathname, name=i}]
[red, opacity=0.5, every node/.style={left=.25cm, black, opacity=1}]
\foreach \s in {1,2,3}{(i-\s) circle (2pt) node {\footnotesize\s}};
}
\end{tikzpicture}

\section*{Playing Around}
% ~~~~~~~~
\begin{tikzpicture}
\draw [->, name path = myCurve, blue] (1,1.5) .. controls (-1,1) and (2,0.5) .. (0,0);
\node[anchor = west, blue] at (1,1.5) {Curve Start};
\node[anchor = east,yshift = -2.5mm, blue] at (0,0) {Curve End};
\draw [->, name path = myLine] (0,-.5) -- (1,2) ;
\fill [name intersections = {of = myLine and myCurve, sort by = myCurve, name = myIntersectionIndex}]
[red, opacity = 0.5, every node/.style={left = 2mm, black, opacity=1}]
% ~~~
\foreach \myForEachCounter in {1,2,3}{
(myIntersectionIndex-\myForEachCounter) circle (2pt) node {\footnotesize\myForEachCounter}
};
% ~~~
\end{tikzpicture}

% ~~~~~~~~
\begin{tikzpicture}
\draw [->, name path = myLine] (1,1) -- (5,5) ;
\draw[name path = myGrid] [xstep = 3, ystep = 2] (0,0) grid (9,8);
\fill [name intersections = {of = myLine and myGrid, sort by = myLine, name = myIntersectionIndex}]
[red, opacity = 0.5, every node/.style={left = 2mm, black, opacity=1}]
% ~~~
\foreach \myForEachCounter in {1,2,3}{
(myIntersectionIndex-\myForEachCounter) circle (2pt) node {\footnotesize\myForEachCounter}
};
% ~~~
\end{tikzpicture}

% ~~~~~~~~
\begin{tikzpicture}
\draw [->, name path = myLine] (0.5,2.5) -- (9,9) ;
\draw[name path = myGrid] [xstep = 2, ystep = 2] (0,0) grid (10,10);
\fill [name intersections = {of = myLine and myGrid, sort by = myLine, name = myIntersectionIndex}]
[red, opacity = 0.5, every node/.style={left = 2mm, black, opacity=1}]
% ~~~
\foreach \myForEachCounter in {1,2,3,4,5,6,7}{
(myIntersectionIndex-\myForEachCounter) circle (2pt) node {\footnotesize\myForEachCounter}
};
% ~~~
\end{tikzpicture}

\end{document}


This was a bug in PGF which I have since fixed

https://github.com/pgf-tikz/pgf/issues/480

With PGF 3.1.5 and newer, the example from your question will produce the correct ordering.

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

\begin{document}
\begin{tikzpicture}
\draw[name path=grid] [xstep=3,ystep=2] (0,0) grid (9,8);
\draw[->, name path=line] (2,1) -- (7,7);
\draw[name intersections={of=grid and line, sort by=line, name=i, total=\t}]
\foreach \s in {1,...,\t}{(i-\s) node {\s}};
\end{tikzpicture}
\end{document}