Automatically connect nodes without overlapping other nodes or connections

Question

In making a tree diagram with TikZ. Say that I've got the following nodes

\node(a) {\(A\)};
\node(b1) at ($(a)+(4,1)$){\(B_1\)};
\node(b2) at ($(b1)+(0,-1)$){\(B_2\)};
\node(c) at ($(b1)+(1,-0.9)$){\(C\)};
\node(d) at ($(c)+(2,0)$){\(D\)};
\node(e) at ($(d)+(1,0.5)$){\(E\)};

and that I want to draw the following connections

• (a) to (b1)
• (a) to (b2)
• (b1) to (d)
• (b2) to (e)

but I want no or as few connections as possible to overlap another node or another connection (without changing the placement of the nodes).

If I draw straight lines between the nodes

\documentclass{article}

\usepackage{tikz}
\usetikzlibrary{calc}

\begin{document}

\begin{tikzpicture}
\node(a) {\(A\)};
\node(b1) at ($(a)+(4,1)$){\(B_1\)};
\node(b2) at ($(b1)+(0,-1)$){\(B_2\)};
\node(c) at ($(b1)+(1,-0.9)$){\(C\)};
\node(d) at ($(c)+(2,0)$){\(D\)};
\node(e) at ($(d)+(1,0.5)$){\(E\)};
\draw[->] (a) to (b1);
\draw[->] (a) to (b2);
\draw[->] (b1) to (d);
\draw[->,red] (b2) to (e);

\end{tikzpicture}

\end{document}

I end up with an overlap of C and an overlap of the line B₁ and D (the red line):

Also, if I make the lines somewhat curved

\documentclass{article}

\usepackage{tikz}
\usetikzlibrary{calc}

\begin{document}

\begin{tikzpicture}
\node(a) {\(A\)};
\node(b1) at ($(a)+(4,1)$){\(B_1\)};
\node(b2) at ($(b1)+(0,-1)$){\(B_2\)};
\node(c) at ($(b1)+(1,-0.9)$){\(C\)};
\node(d) at ($(c)+(2,0)$){\(D\)};
\node(e) at ($(d)+(1,0.5)$){\(E\)};
\draw[->] (a) to[out=20,in=180] (b1);
\draw[->] (a) to[out=0,in=180] (b2);
\draw[->] (b1) to[out=0,in=160] (d);
\draw[->,red] (b2) to[out=0,in=180] (e);
\draw[->,red,dashed] (b2) to[out=-40,in=240] (e);

\end{tikzpicture}

\end{document}

I get the same kind of overlap:

What I'm after is a result like the dashed red line that don't overlap anything but without having to manually set what angles the lines should enter and exit nodes from.

In short, is there a way to avoid overlaps of nodes and other lines except for manually changing angles for lines, i.e. can I tell TikZ to avoid drawing over other nodes and lines and draw around them instead?

Answer 1

I have a very strong suspicion that the general problem is not really tractable by TeX/TikZ. This is based on the fact that there are programs like graphviz which have really complicated routines for solving this sort of problem. Moreover, I think that it's going to be impossible in general in that there will be configurations where there is no solution with no crossings.

So what I have to offer is the following code. This defines a to path which goes from its start to its end through a particular point. The intention being that you use it to avoid a node by saying that you want your path to go through a particular corner of the node you want to avoid; thus we use the node as the region to avoid.

To make the problem tractable, I've used a different family of curves than is used by the to[out=angle, in=angle] curves.

Here's the proof-of-concept code:

\documentclass{standalone}
%\url{http://tex.stackexchange.com/q/27899/86}
\usepackage{tikz}
\usetikzlibrary{calc}

\makeatletter
\tikzset{
  through point/.style={
    to path={%
      \pgfextra{%
        \tikz@scan@one@point\pgfutil@firstofone(\tikztostart)\relax
        \pgfmathsetmacro{\pt@sx}{\pgf@x * 0.03514598035}%
        \pgfmathsetmacro{\pt@sy}{\pgf@y * 0.03514598035}%
        \tikz@scan@one@point\pgfutil@firstofone#1\relax
        \pgfmathsetmacro{\pt@ax}{\pgf@x * 0.03514598035 - \pt@sx}%
        \pgfmathsetmacro{\pt@ay}{\pgf@y * 0.03514598035 - \pt@sy}%
        \tikz@scan@one@point\pgfutil@firstofone(\tikztotarget)\relax
        \pgfmathsetmacro{\pt@ex}{\pgf@x * 0.03514598035 - \pt@sx}%
        \pgfmathsetmacro{\pt@ey}{\pgf@y * 0.03514598035 - \pt@sy}%
        \pgfmathsetmacro{\pt@len}{\pt@ex * \pt@ex + \pt@ey * \pt@ey}%
        \pgfmathsetmacro{\pt@t}{(\pt@ax * \pt@ex + \pt@ay * \pt@ey)/\pt@len}%
        \pgfmathsetmacro{\pt@t}{(\pt@t > .5 ? 1 - \pt@t : \pt@t)}%
        \pgfmathsetmacro{\pt@h}{(\pt@ax * \pt@ey - \pt@ay * \pt@ex)/\pt@len}%
        \pgfmathsetmacro{\pt@y}{\pt@h/(3 * \pt@t * (1 - \pt@t))}%
      }
      (\tikztostart) .. controls +(\pt@t * \pt@ex + \pt@y * \pt@ey, \pt@t * \pt@ey - \pt@y * \pt@ex) and +(-\pt@t * \pt@ex + \pt@y * \pt@ey, -\pt@t * \pt@ey - \pt@y * \pt@ex) .. (\tikztotarget)
    }
  }
}

\makeatother


\begin{document}
\begin{tikzpicture}
\fill (0,0) circle[radius=2pt];
\fill (2,1) circle[radius=2pt];
\fill (5,5) circle[radius=2pt];
  \draw
   (0,0) to[through point={(2,1)}] (5,5);
\end{tikzpicture}
\end{document}

and the result:

If we put that in your code, we get the following, where the green line is that added by my code:

Here's the code:

\documentclass{standalone}
%\url{http://tex.stackexchange.com/q/27899/86}
\usepackage{tikz}
\usetikzlibrary{calc}

\makeatletter
\tikzset{
  through point/.style={
    to path={%
      \pgfextra{%
        \tikz@scan@one@point\pgfutil@firstofone(\tikztostart)\relax
        \pgfmathsetmacro{\pt@sx}{\pgf@x * 0.03514598035}%
        \pgfmathsetmacro{\pt@sy}{\pgf@y * 0.03514598035}%
        \tikz@scan@one@point\pgfutil@firstofone#1\relax
        \pgfmathsetmacro{\pt@ax}{\pgf@x * 0.03514598035 - \pt@sx}%
        \pgfmathsetmacro{\pt@ay}{\pgf@y * 0.03514598035 - \pt@sy}%
        \tikz@scan@one@point\pgfutil@firstofone(\tikztotarget)\relax
        \pgfmathsetmacro{\pt@ex}{\pgf@x * 0.03514598035 - \pt@sx}%
        \pgfmathsetmacro{\pt@ey}{\pgf@y * 0.03514598035 - \pt@sy}%
        \pgfmathsetmacro{\pt@len}{\pt@ex * \pt@ex + \pt@ey * \pt@ey}%
        \pgfmathsetmacro{\pt@t}{(\pt@ax * \pt@ex + \pt@ay *           \pt@ey)/\pt@len}%
        \pgfmathsetmacro{\pt@t}{(\pt@t > .5 ? 1 - \pt@t : \pt@t)}%
        \pgfmathsetmacro{\pt@h}{(\pt@ax * \pt@ey - \pt@ay *           \pt@ex)/\pt@len}%
        \pgfmathsetmacro{\pt@y}{\pt@h/(3 * \pt@t * (1 - \pt@t))}%
      }
      (\tikztostart) .. controls +(\pt@t * \pt@ex + \pt@y * \pt@ey, \pt@t * \pt@ey - \pt@y * \pt@ex) and +(-\pt@t * \pt@ex + \pt@y * \pt@ey, -\pt@t * \pt@ey - \pt@y * \pt@ex) .. (\tikztotarget)
    }
  }
}

\makeatother


\begin{document}
\begin{tikzpicture}
\node(a) {\(A\)};
\node(b1) at ($(a)+(4,1)$){\(B_1\)};
\node(b2) at ($(b1)+(0,-1)$){\(B_2\)};
\node(c) at ($(b1)+(1,-0.9)$){\(C\)};
\node(d) at ($(c)+(2,0)$){\(D\)};
\node(e) at ($(d)+(1,0.5)$){\(E\)};
\draw[->] (a) to[out=20,in=180] (b1);
\draw[->] (a) to[out=0,in=180] (b2);
\draw[->] (b1) to[out=0,in=160] (d);
\draw[->,red] (b2) to[out=0,in=180] (e);
\draw[->,red,dashed] (b2) to[out=-40,in=240] (e);
\draw[->,green] (b2) to[through point={(d.south east)}] (e);
\end{tikzpicture}
\end{document}

As I said at the start, I think that the general problem will not be (easily) soluble (I'd be happy to be proved wrong ...). So to get around this, I require you, the user, to decide which paths have to move, and to decide which side to move it. The code then works out a nice (I hope!) path.

Explanation of the code: We want a bezier curve from the start to the finish through a particular point. In general, this would involve solving a cubic equation which, while possible, isn't pleasant. So we simplify the bezier. Let's take a bezier, a (1 - t)^3 + 3 b t (1 - t)^2 + 3 c t^2 (1 - t) + d t^3, and transform our coordinates so that a is at the origin and d is at (1,0). Then if we pick the x coordinates of b and c to be 1/3, the x-projection is linear. This means that it is easy to figure out the time at which the bezier goes through a particular vertical line.

So to make it go through a particular point, say (p,q) with p ∈ (0,1), we simply take t = p. Then we also assume that the y-coordinates of b and c are the same (say h), whence we get the formula h = q/(3 p (1 - p)).

The code above does this, only we have to work in a different coordinate system, so we have lots of orthogonal projections going on.