Arranging connector lines

Question

Heike gave an absolutely wonderful answer to my question about arranging subplots around a main plot and including connector lines. This is the result:

Starting from Heike's answer, what is the best order to arrange the subplots in so the connector lines are as easy to follow / as aesthetically arranged as possible?

To have something concrete to test with, let's say we have 12 points in the unit square. These are the starting points of the lines.

start = RandomReal[1, {12, 2}];

The set of endpoints is fixed (due to the subplot positions):

end = With[{dx = 0.1, dy = 0.1}, 
       {{-dx, 1 + dy}, {.25 - dx/4, 1 + dy}, {.75 + dx/4, 1 + dy}, 
        {1 + dx, 1 + dy}, {1 + dx, .75 + dy/4}, {1 + dx, .25 - dx/4}, 
        {1 + dx, -dy}, {.75 + dx/4, -dy}, {.25 - dx/4, -dy}, 
        {-dx, -dy}, {-dx, .25 - dy/4}, {-dx, .75 + dy/4}}];

Then the plot will look similar to this:

Graphics[{
  FaceForm[Lighter@Orange], Polygon[{{0, 0}, {1, 0}, {1, 1}, {0, 1}}],
  Line@Transpose[{start, end}],
  AbsolutePointSize[18], Lighter@Orange, Point[end], 
  Black, MapThread[Text, {Range[12], end}]}, 
  Frame -> True, FrameTicks -> None, PlotRange -> {{-.2, 1.2}, {-.2, 1.2}}]

Given the starting points in the orange square, how can we automatically reorder the labelled endpoints so the lines cross as little as possible (or generally: the figure looks as good as possible)?

Please try to make your answers complete, with a sample output figure using the code above. When it is not possible to avoid that the lines cross, what the "best" arrangement is is admittedly somewhat subjective.

---

Note: This is a question that I thought others would be interested in too. It is not a practical problem I am facing (I ordered the subplots manually in my figure), but of course if there are any good solutions, I will use them. I will be working on solutions as well.

Note 2: Given two lists, l1 and l2, containing the same elements in different orders, the permutation that re-orders l1 to l2 is Part[Ordering[l1], Ordering@Ordering[l2]]. This may be useful for reordering points.

Answer 1

This method tries to find a minimum of the total length of all connecting lines by repeatedly swapping the endpoints of pairs of connecting lines if that reduces the total length of those two connecting lines until the list of edges doesn't change anymore. From the triangle inequality this then also guarantees that no two connecting lines will intersect each other.

start = RandomReal[1, {12, 2}];
end = With[{dx = 0.1, dy = 0.1}, 
       {{-dx, 1 + dy}, {.25 - dx/4, 1 + dy}, {.75 + dx/4, 1 + dy}, 
        {1 + dx, 1 + dy}, {1 + dx, .75 + dy/4}, {1 + dx, .25 - dx/4}, 
        {1 + dx, -dy}, {.75 + dx/4, -dy}, {.25 - dx/4, -dy}, 
        {-dx, -dy}, {-dx, .25 - dy/4}, {-dx, .75 + dy/4}}];

combis = Subsets[Range[12], {2}];
length[{b_, e_}] := EuclideanDistance[start[[b]], end[[e]]]

newedges = Transpose[{Range[12], Range[12]}];
FixedPoint[
 Do[p = {#[[{1, 4}]], #[[{3, 2}]]} &@Flatten[newedges[[c]]];
   If[Total[length /@ p] < Total[length /@ newedges[[c]]],
    newedges[[c]] = p],
   {c, combis}] &, newedges, 10]

Then the before picture is this:

and the after picture is:

Graphics[{FaceForm[Lighter@Orange], 
  Polygon[{{0, 0}, {1, 0}, {1, 1}, {0, 1}}], 
  Line@Transpose[{start[[newedges[[All, 1]]]],
     end[[newedges[[All, 2]]]]}], AbsolutePointSize[18], 
  Lighter@Orange, Point[end[[newedges[[All, 2]]]]], Black, 
  MapThread[Text, {Range[12], end[[newedges[[All, 2]]]]}]}, 
 Frame -> True, FrameTicks -> None, 
 PlotRange -> {{-.2, 1.2}, {-.2, 1.2}}]

Answer 2

Here is my proposition. Active code in the middle block; the rest for completeness.

Update: now numbers points correctly.

Update: explicit method for FindShortestTour to avoid problems in version 8.

base = RandomReal[1, {12, 2}];
end = With[{dx = 0.1, dy = 0.1},
 {{-dx, 1 + dy}, {.25 - dx/4, 1 + dy}, {.75 + dx/4, 1 + dy}, {1 + dx, 1 + dy},
 {1 + dx, .75 + dy/4}, {1 + dx, .25 - dx/4}, {1 + dx, -dy}, {.75 + dx/4, -dy},
 {.25 - dx/4, -dy}, {-dx, -dy}, {-dx, .25 - dy/4}, {-dx, .75 + dy/4}}];    


tour   = Reverse @ FindShortestTour[base, Method -> "CCA"][[2]];
rots   = NestList[RotateLeft, base[[tour]], 11];
metric = Tr @ MapThread[EuclideanDistance, {#, end}] &;
best   = First @ Ordering[metric /@ rots, {1}];
start  = rots[[best]];
nums   = RotateLeft[Range[12][[tour]], best - 1];


Graphics[{
  Lighter @ Orange, 
  Polygon[{{0, 0}, {1, 0}, {1, 1}, {0, 1}}], 
  {Black, Line @ Transpose[{start, end}]},
  {AbsolutePointSize[18], Point[end]},
  {Black, MapThread[Text, {nums, end}]}},
 Frame -> True,
 FrameTicks -> None,
 PlotRange -> {{-.2, 1.2}, {-.2, 1.2}}
]

I also used total line length (Tr). You can experiment with other quality tests such as Mean, Median, Max, etc. Sometimes one of these others, especially Max, seems to give a more aesthetic layout.

This should now work as I intended on version 8. Note that some crossings remain:

Answer 3

Here is an implementation using the angle of the point. Using FJRA's random points generation method:

In[67]:= start = RandomReal[{0, 1}, {12, 2}]

Out[67]= {{0.957578, 0.49789}, {0.984345, 0.872682}, {0.250315, 
  0.542327}, {0.811817, 0.60049}, {0.65166, 0.79753}, {0.891558, 
  0.125237}, {0.42729, 0.602176}, {0.297289, 0.440565}, {0.673284, 
  0.503713}, {0.587548, 0.249505}, {0.135377, 0.138527}, {0.0435007, 
  0.827718}}

We first need to normalize the data. Note that it matters where the center of your main graphic is. Because of the points I've chosen, I have normalised on {0.5,0.5}

In[68]:= step1 = Normalize /@ ( # - {0.5, 0.5} & /@ start)

Out[68]= {{0.999989, -0.00461163}, {0.792538, 0.609822}, {-0.985933, 
  0.167139}, {0.951795, 0.306736}, {0.454136, 
  0.890933}, {0.722431, -0.691443}, {-0.579794, 
  0.814763}, {-0.959603, -0.281357}, {0.999771, 
  0.0214221}, {0.32993, -0.944006}, {-0.710168, -0.704032}, \
{-0.812345, 0.583178}}

Verifying the normalisation

In[69]:= Norm /@ step1

Out[69]= {1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.}

Now, work out the angle of the points relative to the center of the graphic and re-order the points accordingly:

   In[70]:= step2 = start[[Ordering[ArcTan @@@ step1] ]]

Out[70]= {{0.297289, 0.440565}, {0.135377, 0.138527}, {0.587548, 
  0.249505}, {0.891558, 0.125237}, {0.957578, 0.49789}, {0.673284, 
  0.503713}, {0.811817, 0.60049}, {0.984345, 0.872682}, {0.65166, 
  0.79753}, {0.42729, 0.602176}, {0.0435007, 0.827718}, {0.250315, 
  0.542327}}

Re-order the positions of the end-points the same way

In[73]:= end2 = end[[Ordering[ArcTan @@@ end] ]]

Out[73]= {{-0.1, -0.1}, {0.225, -0.1}, {0.775, -0.1}, {1.1, -0.1}, \
{1.1, 0.225}, {1.1, 0.775}, {1.1, 1.1}, {0.775, 1.1}, {0.225, 
  1.1}, {-0.1, 1.1}, {-0.1, 0.775}, {-0.1, 0.225}}

And here is the graphic:

Graphics[{FaceForm[Lighter@Orange], 
  Polygon[{{0, 0}, {1, 0}, {1, 1}, {0, 1}}], 
  Line@Transpose[{step2, end2}], AbsolutePointSize[18], 
  Lighter@Orange, Point[end2], Black, 
  MapThread[Text, {Range[12], end2}]}, Frame -> True, 
 FrameTicks -> None, PlotRange -> {{-.2, 1.2}, {-.2, 1.2}}]

It's not perfect, particularly if the arrangement of points is quite bunched, but it avoids most crossings. There might be a way to refine it based on the distance between the angles, butjust ordering the angles works pretty well.

Answer 4

This is a nice problem.

I get this solution:

Initialization:

start = RandomReal[1, {12, 2}];
end = With[{dx = 0.1, 
    dy = 0.1}, {{-dx, 1 + dy}, {.25 - dx/4, 1 + dy}, {.75 + dx/4, 
     1 + dy}, {1 + dx, 
     1 + dy}, {1 + dx, .75 + dy/4}, {1 + dx, .25 - dx/4}, {1 + 
      dx, -dy}, {.75 + dx/4, -dy}, {.25 - 
      dx/4, -dy}, {-dx, -dy}, {-dx, .25 - dy/4}, {-dx, .75 + dy/4}}];
labels = Range[12];

Then build a matrix of distances between starts and ends, and take the min values of distances to choose the new order:

matrixDistances = Table[Norm[a - b], {a, start}, {b, end}];
tempmatrix = matrixDistances;
neworder = Table[
  With[{pos = First[Position[tempmatrix, Min[tempmatrix]]]},
   tempmatrix[[pos[[1]], All]] = \[Infinity];
   tempmatrix[[All, pos[[2]]]] = \[Infinity];
   pos
   ],
  {i, 12}
  ]

Then the graphic is ready to be done:

Graphics[{FaceForm[Lighter@Orange], 
  Polygon[{{0, 0}, {1, 0}, {1, 1}, {0, 1}}], 
  Line@Transpose[{start[[neworder[[All, 1]]]], 
     end[[neworder[[All, 2]]]]}], AbsolutePointSize[18], 
  Lighter@Orange, Point[end], Black, 
  MapThread[
   Text, {labels[[neworder[[All, 1]]]], end[[neworder[[All, 2]]]]}]}, 
 Frame -> True, FrameTicks -> None, 
 PlotRange -> {{-.2, 1.2}, {-.2, 1.2}}]

By the way, without sorting the points you would have get this: