Connecting the dots. Spanning trees have a wide variety of applications in GIS... or did. I have been finishing writings on distance and geometry and I almost forgot this one. The principle is simple. Connect the dots, so that no line (edge) overlaps, but only connects at a point. In practice, you want the tree to produce a minimal length/distance output. There are a variety of names forms, each with their subtle nuance and application, but my favorite is Prim's... only because I sortof understand it. I am not sure if this his implementation exactly, but it is close enough. So I post it here for those that want to try it. Besides, Prim's can be used to produce mazes, a far more useful application of dot connection.
My favorite code header to cover imports and array printing and some bare-bones graphing
<SPAN class="keyword token">import</SPAN> sys
<SPAN class="keyword token">import</SPAN> numpy <SPAN class="keyword token">as</SPAN> np
<SPAN class="keyword token">import</SPAN> matplotlib<SPAN class="punctuation token">.</SPAN>pyplot <SPAN class="keyword token">as</SPAN> plt
<SPAN class="keyword token">from</SPAN> textwrap <SPAN class="keyword token">import</SPAN> dedent<SPAN class="punctuation token">,</SPAN> indent
ft <SPAN class="operator token">=</SPAN> <SPAN class="punctuation token">{</SPAN><SPAN class="string token">'bool'</SPAN><SPAN class="punctuation token">:</SPAN> <SPAN class="keyword token">lambda</SPAN> x<SPAN class="punctuation token">:</SPAN> repr<SPAN class="punctuation token">(</SPAN>x<SPAN class="punctuation token">.</SPAN>astype<SPAN class="punctuation token">(</SPAN><SPAN class="string token">'int32'</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN>
<SPAN class="string token">'float'</SPAN><SPAN class="punctuation token">:</SPAN> <SPAN class="string token">'{: 0.1f}'</SPAN><SPAN class="punctuation token">.</SPAN>format<SPAN class="punctuation token">}</SPAN>
np<SPAN class="punctuation token">.</SPAN>set_printoptions<SPAN class="punctuation token">(</SPAN>edgeitems<SPAN class="operator token">=</SPAN><SPAN class="number token">10</SPAN><SPAN class="punctuation token">,</SPAN> linewidth<SPAN class="operator token">=</SPAN><SPAN class="number token">100</SPAN><SPAN class="punctuation token">,</SPAN> precision<SPAN class="operator token">=</SPAN><SPAN class="number token">2</SPAN><SPAN class="punctuation token">,</SPAN>
suppress<SPAN class="operator token">=</SPAN><SPAN class="token boolean">True</SPAN><SPAN class="punctuation token">,</SPAN> threshold<SPAN class="operator token">=</SPAN><SPAN class="number token">120</SPAN><SPAN class="punctuation token">,</SPAN>
formatter<SPAN class="operator token">=</SPAN>ft<SPAN class="punctuation token">)</SPAN>
np<SPAN class="punctuation token">.</SPAN>ma<SPAN class="punctuation token">.</SPAN>masked_print_option<SPAN class="punctuation token">.</SPAN>set_display<SPAN class="punctuation token">(</SPAN><SPAN class="string token">'-'</SPAN><SPAN class="punctuation token">)</SPAN>
script <SPAN class="operator token">=</SPAN> sys<SPAN class="punctuation token">.</SPAN>argv<SPAN class="punctuation token">[</SPAN><SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="line-numbers-rows"><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN></SPAN>Now the ending of the script where the actual calls are performed and an explanation of what is happening occurs.
<SPAN class="comment token"># ---------------------------------------------------------------------</SPAN>
<SPAN class="keyword token">if</SPAN> __name__ <SPAN class="operator token">==</SPAN> <SPAN class="string token">"__main__"</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="string token">"""Main section... """</SPAN>
<SPAN class="comment token">#print("Script... {}".format(script))</SPAN>
<SPAN class="comment token"># ---- Take a few points to get you started ----</SPAN>
a <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>array<SPAN class="punctuation token">(</SPAN><SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">[</SPAN><SPAN class="number token">0</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">[</SPAN><SPAN class="number token">0</SPAN><SPAN class="punctuation token">,</SPAN><SPAN class="number token">8</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">[</SPAN><SPAN class="number token">10</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="number token">8</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">[</SPAN><SPAN class="number token">10</SPAN><SPAN class="punctuation token">,</SPAN><SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">[</SPAN><SPAN class="number token">3</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="number token">4</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">[</SPAN><SPAN class="number token">7</SPAN><SPAN class="punctuation token">,</SPAN><SPAN class="number token">4</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">)</SPAN>
<SPAN class="comment token">#</SPAN>
idx<SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>lexsort<SPAN class="punctuation token">(</SPAN><SPAN class="punctuation token">(</SPAN>a<SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">:</SPAN><SPAN class="punctuation token">,</SPAN><SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> a<SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">:</SPAN><SPAN class="punctuation token">,</SPAN><SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">)</SPAN> <SPAN class="comment token"># sort X, then Y</SPAN>
a_srt <SPAN class="operator token">=</SPAN> a<SPAN class="punctuation token">[</SPAN>idx<SPAN class="punctuation token">,</SPAN><SPAN class="punctuation token">:</SPAN><SPAN class="punctuation token">]</SPAN> <SPAN class="comment token"># slice the sorted array</SPAN>
d <SPAN class="operator token">=</SPAN> _e_dist<SPAN class="punctuation token">(</SPAN>a_srt<SPAN class="punctuation token">)</SPAN> <SPAN class="comment token"># determine the square form distances</SPAN>
pairs <SPAN class="operator token">=</SPAN> mst<SPAN class="punctuation token">(</SPAN>d<SPAN class="punctuation token">)</SPAN> <SPAN class="comment token"># get the orig-dest pairs for the mst</SPAN>
plot_mst<SPAN class="punctuation token">(</SPAN>a_srt<SPAN class="punctuation token">,</SPAN> pairs<SPAN class="punctuation token">)</SPAN> <SPAN class="comment token"># a little plot</SPAN>
o_d <SPAN class="operator token">=</SPAN> connect<SPAN class="punctuation token">(</SPAN>a_srt<SPAN class="punctuation token">,</SPAN> d<SPAN class="punctuation token">,</SPAN> pairs<SPAN class="punctuation token">)</SPAN> <SPAN class="comment token"># produce an o-d structured array</SPAN><SPAN class="line-numbers-rows"><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN></SPAN>Now the rest is just filler. The code defs are given below.
<SPAN class="keyword token">def</SPAN> <SPAN class="token function">_e_dist</SPAN><SPAN class="punctuation token">(</SPAN>a<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="string token">"""Return a 2D square-form euclidean distance matrix. For other
: dimensions, use e_dist in ein_geom.py"""</SPAN>
b <SPAN class="operator token">=</SPAN> a<SPAN class="punctuation token">.</SPAN>reshape<SPAN class="punctuation token">(</SPAN>np<SPAN class="punctuation token">.</SPAN>prod<SPAN class="punctuation token">(</SPAN>a<SPAN class="punctuation token">.</SPAN>shape<SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">:</SPAN><SPAN class="operator token">-</SPAN><SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">,</SPAN> a<SPAN class="punctuation token">.</SPAN>shape<SPAN class="punctuation token">[</SPAN><SPAN class="operator token">-</SPAN><SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">)</SPAN>
diff <SPAN class="operator token">=</SPAN> a <SPAN class="operator token">-</SPAN> b
d <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>sqrt<SPAN class="punctuation token">(</SPAN>np<SPAN class="punctuation token">.</SPAN>einsum<SPAN class="punctuation token">(</SPAN><SPAN class="string token">'ijk,ijk->ij'</SPAN><SPAN class="punctuation token">,</SPAN> diff<SPAN class="punctuation token">,</SPAN> diff<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">.</SPAN>squeeze<SPAN class="punctuation token">(</SPAN><SPAN class="punctuation token">)</SPAN>
<SPAN class="comment token">#d = np.triu(d)</SPAN>
<SPAN class="keyword token">return</SPAN> d
<SPAN class="keyword token">def</SPAN> <SPAN class="token function">mst</SPAN><SPAN class="punctuation token">(</SPAN>W<SPAN class="punctuation token">,</SPAN> copy_W<SPAN class="operator token">=</SPAN><SPAN class="token boolean">True</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="string token">"""Determine the minimum spanning tree for a set of points represented
: by their inter-point distances... ie their 'W'eights
:Requires:
:--------
: W - edge weights (distance, time) for a set of points. W needs to be
: a square array or a np.triu perhaps
:Returns:
:-------
: pairs - the pair of nodes that form the edges
"""</SPAN>
<SPAN class="keyword token">if</SPAN> copy_W<SPAN class="punctuation token">:</SPAN>
W <SPAN class="operator token">=</SPAN> W<SPAN class="punctuation token">.</SPAN>copy<SPAN class="punctuation token">(</SPAN><SPAN class="punctuation token">)</SPAN>
<SPAN class="keyword token">if</SPAN> W<SPAN class="punctuation token">.</SPAN>shape<SPAN class="punctuation token">[</SPAN><SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN> <SPAN class="operator token">!=</SPAN> W<SPAN class="punctuation token">.</SPAN>shape<SPAN class="punctuation token">[</SPAN><SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="keyword token">raise</SPAN> ValueError<SPAN class="punctuation token">(</SPAN><SPAN class="string token">"W needs to be square matrix of edge weights"</SPAN><SPAN class="punctuation token">)</SPAN>
Np <SPAN class="operator token">=</SPAN> W<SPAN class="punctuation token">.</SPAN>shape<SPAN class="punctuation token">[</SPAN><SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN>
pairs <SPAN class="operator token">=</SPAN> <SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">]</SPAN>
pnts_seen <SPAN class="operator token">=</SPAN> <SPAN class="punctuation token">[</SPAN><SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN> <SPAN class="comment token"># Add the first point </SPAN>
n_seen <SPAN class="operator token">=</SPAN> <SPAN class="number token">1</SPAN>
<SPAN class="comment token"># exclude self connections by assigning inf to the diagonal</SPAN>
diag <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>arange<SPAN class="punctuation token">(</SPAN>Np<SPAN class="punctuation token">)</SPAN>
W<SPAN class="punctuation token">[</SPAN>diag<SPAN class="punctuation token">,</SPAN> diag<SPAN class="punctuation token">]</SPAN> <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>inf
<SPAN class="comment token"># </SPAN>
<SPAN class="keyword token">while</SPAN> n_seen <SPAN class="operator token">!=</SPAN> Np<SPAN class="punctuation token">:</SPAN>
new_edge <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>argmin<SPAN class="punctuation token">(</SPAN>W<SPAN class="punctuation token">[</SPAN>pnts_seen<SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> axis<SPAN class="operator token">=</SPAN>None<SPAN class="punctuation token">)</SPAN>
new_edge <SPAN class="operator token">=</SPAN> divmod<SPAN class="punctuation token">(</SPAN>new_edge<SPAN class="punctuation token">,</SPAN> Np<SPAN class="punctuation token">)</SPAN>
new_edge <SPAN class="operator token">=</SPAN> <SPAN class="punctuation token">[</SPAN>pnts_seen<SPAN class="punctuation token">[</SPAN>new_edge<SPAN class="punctuation token">[</SPAN><SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> new_edge<SPAN class="punctuation token">[</SPAN><SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">]</SPAN>
pairs<SPAN class="punctuation token">.</SPAN>append<SPAN class="punctuation token">(</SPAN>new_edge<SPAN class="punctuation token">)</SPAN>
pnts_seen<SPAN class="punctuation token">.</SPAN>append<SPAN class="punctuation token">(</SPAN>new_edge<SPAN class="punctuation token">[</SPAN><SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">)</SPAN>
W<SPAN class="punctuation token">[</SPAN>pnts_seen<SPAN class="punctuation token">,</SPAN> new_edge<SPAN class="punctuation token">[</SPAN><SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">]</SPAN> <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>inf
W<SPAN class="punctuation token">[</SPAN>new_edge<SPAN class="punctuation token">[</SPAN><SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> pnts_seen<SPAN class="punctuation token">]</SPAN> <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>inf
n_seen <SPAN class="operator token">+=</SPAN> <SPAN class="number token">1</SPAN>
<SPAN class="keyword token">return</SPAN> np<SPAN class="punctuation token">.</SPAN>vstack<SPAN class="punctuation token">(</SPAN>pairs<SPAN class="punctuation token">)</SPAN>
<SPAN class="keyword token">def</SPAN> <SPAN class="token function">plot_mst</SPAN><SPAN class="punctuation token">(</SPAN>a<SPAN class="punctuation token">,</SPAN> pairs<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="string token">"""plot minimum spanning tree test """</SPAN>
plt<SPAN class="punctuation token">.</SPAN>scatter<SPAN class="punctuation token">(</SPAN>a<SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">:</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> a<SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">:</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">)</SPAN>
ax <SPAN class="operator token">=</SPAN> plt<SPAN class="punctuation token">.</SPAN>axes<SPAN class="punctuation token">(</SPAN><SPAN class="punctuation token">)</SPAN>
ax<SPAN class="punctuation token">.</SPAN>set_aspect<SPAN class="punctuation token">(</SPAN><SPAN class="string token">'equal'</SPAN><SPAN class="punctuation token">)</SPAN>
<SPAN class="keyword token">for</SPAN> pair <SPAN class="keyword token">in</SPAN> pairs<SPAN class="punctuation token">:</SPAN>
i<SPAN class="punctuation token">,</SPAN> j <SPAN class="operator token">=</SPAN> pair
plt<SPAN class="punctuation token">.</SPAN>plot<SPAN class="punctuation token">(</SPAN><SPAN class="punctuation token">[</SPAN>a<SPAN class="punctuation token">[</SPAN>i<SPAN class="punctuation token">,</SPAN> <SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> a<SPAN class="punctuation token">[</SPAN>j<SPAN class="punctuation token">,</SPAN> <SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">[</SPAN>a<SPAN class="punctuation token">[</SPAN>i<SPAN class="punctuation token">,</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> a<SPAN class="punctuation token">[</SPAN>j<SPAN class="punctuation token">,</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> c<SPAN class="operator token">=</SPAN><SPAN class="string token">'r'</SPAN><SPAN class="punctuation token">)</SPAN>
lbl <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>arange<SPAN class="punctuation token">(</SPAN>len<SPAN class="punctuation token">(</SPAN>a<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">)</SPAN>
<SPAN class="keyword token">for</SPAN> label<SPAN class="punctuation token">,</SPAN> xpt<SPAN class="punctuation token">,</SPAN> ypt <SPAN class="keyword token">in</SPAN> zip<SPAN class="punctuation token">(</SPAN>lbl<SPAN class="punctuation token">,</SPAN> a<SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">:</SPAN><SPAN class="punctuation token">,</SPAN><SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">,</SPAN> a<SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">:</SPAN><SPAN class="punctuation token">,</SPAN><SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">:</SPAN>
plt<SPAN class="punctuation token">.</SPAN>annotate<SPAN class="punctuation token">(</SPAN>label<SPAN class="punctuation token">,</SPAN> xy<SPAN class="operator token">=</SPAN><SPAN class="punctuation token">(</SPAN>xpt<SPAN class="punctuation token">,</SPAN> ypt<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> xytext<SPAN class="operator token">=</SPAN><SPAN class="punctuation token">(</SPAN><SPAN class="number token">2</SPAN><SPAN class="punctuation token">,</SPAN><SPAN class="number token">2</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> size<SPAN class="operator token">=</SPAN><SPAN class="number token">8</SPAN><SPAN class="punctuation token">,</SPAN>
textcoords<SPAN class="operator token">=</SPAN><SPAN class="string token">'offset points'</SPAN><SPAN class="punctuation token">,</SPAN>
ha<SPAN class="operator token">=</SPAN><SPAN class="string token">'left'</SPAN><SPAN class="punctuation token">,</SPAN> va<SPAN class="operator token">=</SPAN><SPAN class="string token">'bottom'</SPAN><SPAN class="punctuation token">)</SPAN>
plt<SPAN class="punctuation token">.</SPAN>show<SPAN class="punctuation token">(</SPAN><SPAN class="punctuation token">)</SPAN>
plt<SPAN class="punctuation token">.</SPAN>close<SPAN class="punctuation token">(</SPAN><SPAN class="punctuation token">)</SPAN>
<SPAN class="keyword token">def</SPAN> <SPAN class="token function">connect</SPAN><SPAN class="punctuation token">(</SPAN>a<SPAN class="punctuation token">,</SPAN> dist_arr<SPAN class="punctuation token">,</SPAN> edges<SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">:</SPAN>
<SPAN class="string token">"""Return the full spanning tree, with points, connections and distance
: a - point array
: dist - distance array, from _e_dist
: edge - edges, from mst
"""</SPAN>
p_f <SPAN class="operator token">=</SPAN> edges<SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">:</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN>
p_t <SPAN class="operator token">=</SPAN> edges<SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">:</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="number token">1</SPAN><SPAN class="punctuation token">]</SPAN>
d <SPAN class="operator token">=</SPAN> dist_arr<SPAN class="punctuation token">[</SPAN>p_f<SPAN class="punctuation token">,</SPAN> p_t<SPAN class="punctuation token">]</SPAN>
n <SPAN class="operator token">=</SPAN> p_f<SPAN class="punctuation token">.</SPAN>shape<SPAN class="punctuation token">[</SPAN><SPAN class="number token">0</SPAN><SPAN class="punctuation token">]</SPAN>
dt <SPAN class="operator token">=</SPAN> <SPAN class="punctuation token">[</SPAN><SPAN class="punctuation token">(</SPAN><SPAN class="string token">'Orig'</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="string token">'<i4'</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">(</SPAN><SPAN class="string token">'Dest'</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="string token">'i4'</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="punctuation token">(</SPAN><SPAN class="string token">'Dist'</SPAN><SPAN class="punctuation token">,</SPAN> <SPAN class="string token">'<f8'</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">]</SPAN>
out <SPAN class="operator token">=</SPAN> np<SPAN class="punctuation token">.</SPAN>zeros<SPAN class="punctuation token">(</SPAN><SPAN class="punctuation token">(</SPAN>n<SPAN class="punctuation token">,</SPAN><SPAN class="punctuation token">)</SPAN><SPAN class="punctuation token">,</SPAN> dtype<SPAN class="operator token">=</SPAN>dt<SPAN class="punctuation token">)</SPAN>
out<SPAN class="punctuation token">[</SPAN><SPAN class="string token">'Orig'</SPAN><SPAN class="punctuation token">]</SPAN> <SPAN class="operator token">=</SPAN> p_f
out<SPAN class="punctuation token">[</SPAN><SPAN class="string token">'Dest'</SPAN><SPAN class="punctuation token">]</SPAN> <SPAN class="operator token">=</SPAN> p_t
out<SPAN class="punctuation token">[</SPAN><SPAN class="string token">'Dist'</SPAN><SPAN class="punctuation token">]</SPAN> <SPAN class="operator token">=</SPAN> d
<SPAN class="keyword token">return</SPAN> out<SPAN class="line-numbers-rows"><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN><SPAN></SPAN></SPAN>
The output from the sample points is hardly exciting. But you can see the possibilities for the other set.
This one is for a 100 points, with a minimum spacing of 3 within a 100x100 unit square. Sprightly solution even on an iThingy using python 3.5
Now on to maze creation .....
