# How to sort lines into continous paths efficiently

As part of my work I get a bunch of lines from my co-worker. (Background: I do electromagnetic designs, my co-worker does the mechanical design). These lines are in random order, but I need them in continous paths, with all line segments running in the same direction.

I've created a small example, real work consists of several thousand lines.

Create some test data:

(* create some test data *)
spiral1 = N@Table[{p Cos[p], p Sin[p]}, {p, Pi, 4 Pi, Pi/16}];
spiral2 =
N@Table[{p Cos[p + Pi], p Sin[p + Pi]}, {p, Pi, 5 Pi, Pi/16}];
lines = Join[Partition[spiral1, 2, 1], Partition[spiral2, 2, 1]];
(* scramble *)
randomLines =
MapAt[Reverse, RandomSample@lines,
List /@ RandomChoice[Range[Length[lines]],
Floor[Length[lines]/2]]];


And see what we've got:

Graphics[Table[{Hue[i/Length[randomLines]],
Arrow@randomLines[[i]]}, {i, Length[randomLines]}] ]


These lines are now sorted (code below):

sorted = mySort[randomLines];


The random lines were sorted into seperate paths with a continous direction of the lines. (The total direction of each path is still random, but that's OK for me).

Looks as expected:

Graphics[Table[{PointSize[0.05], Hue[i/Length[sorted]],
Point[sorted[[i, 1, 1]]], Arrow@sorted[[i]], GrayLevel[0],
Text[i, sorted[[i, 1, 1]], {0, 0}]}, {i, Length[sorted]}] ]


My question now is, how can I make my prodedural code more Mathematica-like? And hopefully more efficient? For real work, my code is too slow.

Code:

mySort[in : {{{_?NumberQ ..}, {_?NumberQ ..}} ..}] := Module[
{sorted, pool, this, found,
tol = 10.0*^-9},

(* start *)
sorted = {{First[in]}};
pool = Rest[in];

While[Length[pool] > 0,

found = False;
(* use the last of all sorted paths that were found so far,
the other paths are already complete *)

For[i = 1, i <= Length[pool] && Not[found], i++,
this = pool[[i]];
(* check if this fits onto the sorted line path *)
found = Which[
(* this fits on end *)
Norm[sorted[[-1, -1, -1]] - this[[1]]] < tol,
sorted[[-1]] = Append[sorted[[-1]], this];
True,
(* reversed this fits on end *)
Norm[sorted[[-1, -1, -1]] - this[[-1]]] < tol,
sorted[[-1]] = Append[sorted[[-1]], Reverse@this];
True,
(* this fits on beginning *)
Norm[sorted[[-1, 1, 1]] - this[[-1]]] < tol,
sorted[[-1]] = Prepend[sorted[[-1]], this];
True,
(* reversed this fits on beginning *)
Norm[sorted[[-1, 1, 1]] - this[[1]]] < tol,
sorted[[-1]] = Prepend[sorted[[-1]], Reverse@this];
True,
(* nothing found *)
True,
False
](* end of which *);
](* end of for *);

(* remove from unsorted list *)
pool = DeleteCases[pool, this];

If[Not[found],
(* need to start a new path *)
sorted = Append[sorted, {this}];
];
](* end of while *);

(* return result *)
sorted
]


Edit:

Real world data:

randomLines = {{{-0.1732811503690476,
0.3235849266204875}, {-0.17359189280402723,
0.3225643511484479}}, {{-0.003790604496207962,
0.330308955004866}, {-0.004423377968477279,
0.331138019882757}}, {{-0.1609083437046747,
0.32692061568805486}, {-0.16038815001632004,
0.3272754550920334}}, {{-0.15872690806364326,
0.3281712493076333}, {-0.1592959532338122,
0.3279016198019645}}, {{-0.0274412108919291,
0.29769071153521204}, {-0.02718659256118707,
0.29769509804809235}}, {{-0.005814165101646035,
0.33269164676889584}, {-0.0050985101499539795,
0.3319329710614432}}, {{-0.13803406459546397,
0.3404086542534827}, {-0.145936615236459,
0.339332441377564}}, {{-0.022642808371541714,
0.32717602179538546}, {-0.022729514890690448,
0.32742192097588857}}, {{-0.16278418842931225,
0.3252461150235488}, {-0.16319556509908598,
0.3247693743061922}}, {{-0.17411145452597812,
0.31410618140280167}, {-0.17392795919535808,
0.3130552462865045}}, {{-0.132713447337878,
0.30208331443021597}, {-0.100026515355456,
0.299751289764415}}, {{-0.16899889159931059,
0.33089743916120096}, {-0.16826085579381164,
0.33166778863048574}}, {{-0.1643853934095711,
0.3111863043989262}, {-0.16406316733242707,
0.31064530270648133}}, {{-0.0006761538014226468,
0.32374979504491025}, {-0.0009712334861680851,
0.32475013439663575}}, {{-0.025224324645915733,
0.2981887157630561}, {-0.02499793734353272,
0.29830532847747804}}, {{-0.002163040134773521,
0.32764005039517213}, {-0.002658896809373818,
0.3285575889487024}}, {{-0.02242717528344411,
0.3261574150385962}, {-0.022461075109788706,
0.3264159401422299}}, {{-0.1635815832005517,
0.32427187807368313}, {-0.16394119730653092,
0.3237549736620164}}, {{-0.1633365381686077,
0.30961720440672075}, {-0.16371323301748703,
0.3101217967836426}}, {{-0.023674627537488186,
0.3289717309615873}, {-0.0238535412754112,
0.32916139988845045}}, {{-0.1654951793842912,
0.3203275606355335}, {-0.16564700675086885,
0.31971644613989636}}, {{-0.155936889548458,
0.305189994603436}, {-0.151503418460591,
0.304406838304457}}, {{-0.0727958373952835,
0.26461098116609705}, {-0.0428039479687876,
0.263913436451513}}, {{-0.022458263874178742,
0.3019294608469123}, {-0.022503423487267513,
0.30167884092513675}}, {{-0.026932527807086413,
0.2977124426890192}, {-0.02667967567091477,
0.2977427004661773}}, {{-0.09969648248885901,
0.34301571998361696}, {-0.11556475510930601,
0.342302617147025}}, {{-0.024358427676212165,
0.2987220611582121}, {-0.02456442659753365,
0.2985723474973141}}, {{-0.16748374342973676,
0.33239870006741085}, {-0.16826085579381164,
0.33166778863048574}}, {{-0.00010870113377766444,
0.32067570736947887}, {-0.0002443004391560457,
0.3217098077840136}}, {{-0.16493948767647237,
0.3343355772937574}, {-0.16402808627327933,
0.3348900884634228}}, {{-0.15844348057804805,
0.29713091408852776}, {-0.15947637636786122,
0.29739786247756983}}, {{-0.152964624886857,
0.29613490529095693}, {-0.143169407399232,
0.29466514291458284}}, {{-0.16517748475198532,
0.31289941951686434}, {-0.16494330760031867,
0.31231489104223104}}, {{-0.16371323301748703,
0.3101217967836426}, {-0.16406316733242707,
0.31064530270648133}}, {{-0.023305316984615142,
0.29982112172172065}, {-0.02345672343999681,
0.29961636376433226}}, {{-0.0009712334861680851,
0.32475013439663575}, {-0.0013180595627630184,
0.32573373111864834}}, {{-0.16590929240988667,
0.3178473879987169}, {-0.16593153282153464,
0.3172180885150769}}, {{-0.026848640006224257,
0.33060633189857275}, {-0.026590329679737904,
0.3305708325652618}}, {{-0.026334221152176908,
0.3305219158038651}, {-0.026081010879205578,
0.33045971463750307}}, {{-0.17034984968281547,
0.3292468724279576}, {-0.1696958520728942,
0.3300897379458447}}, {{-0.0002443004391560457,
0.3217098077840136}, {-0.00043362294146330525,
0.3227354333633945}}, {{-0.17171167689644382,
0.3070770988467576}, {-0.17116575668310063,
0.30616052573145847}}, {{-0.027441210891929108,
0.29769071153521137}, {-0.02809403765865751,
0.29769725829732896}}, {{-0.147200993609053,
0.330628833209078}, {-0.15633408725220094,
0.3289440070126807}}, {{-0.14462682853728007,
0.3310351852767413}, {-0.13707737058449998,
0.33206331204543804}}, {{-0.15949588000939435,
0.30641294482771697}, {-0.15893195007983538,
0.30613277432504504}}, {{-0.02710844968845011,
0.33062831726772385}, {-0.026848640006224257,
0.33060633189857275}}, {{-0.16666965910887294,
0.3330881939930908}, {-0.16748374342973676,
0.33239870006741085}}, {{-0.02545635562717863,
0.29808378073754377}, {-0.025224324645915733,
0.2981887157630561}}, {{-0.024882153503301283,
0.3299565988498384}, {-0.02511076646419278,
0.3300819804336035}}, {{-0.16696481100080182,
0.3013644638663228}, {-0.16776592565280904,
0.30206898531338117}}, {{-0.1692528790331332,
0.3035981772336514}, {-0.16993469074439835,
0.30441870629797974}}, {{-0.128043266825506,
0.341430487537209}, {-0.12177581745677402,
0.341920407137907}}, {{-0.01472404351682356,
0.33788490576510627}, {-0.015736884608708875,
0.3381337104305543}}, {{-0.026334221152176908,
0.3305219158038651}, {-0.026590329679737904,
0.3305708325652618}}, {{-0.16013211147715362,
0.3366134464966566}, {-0.1611384428627671,
0.33625928227294805}}, {{-0.1630890716399921,
0.33539643486016946}, {-0.16212498684755708,
0.335853245179691}}, {{-0.023347651124051683,
0.32856572694744296}, {-0.02350584449211901,
0.3287729931669158}}, {{-0.02291625928387132,
0.3004778353939403}, {-0.022809415381982865,
0.30070899360053127}}, {{-0.17424002851016965,
0.3151652394208606}, {-0.17411145452597812,
0.31410618140280167}}, {{-0.015736884608708875,
0.3381337104305543}, {-0.01676131871895284,
0.3383293774761414}}, {{-0.16899889159931059,
0.33089743916120096}, {-0.1696958520728942,
0.3300897379458447}}, {{-0.1738491209870721,
0.3215289918789799}, {-0.17405213828418334,
0.3204816528068072}}, {{-0.16494330760031867,
0.31231489104223104}, {-0.16467903858544197,
0.31174333670203586}}, {{-0.16569354052258883,
0.3147148694731183}, {-0.1655531098533738,
0.31410103586116495}}, {{-0.16509726199592512,
0.32152198007933014}, {-0.16485224962736336,
0.3221020502606631}}, {{-0.1624723720816022,
0.2985153330191076}, {-0.16149355361319787,
0.2980910105462918}}, {{-0.16612812978222688,
0.3007025728681141}, {-0.1652581479252421,
0.30008510487417167}}, {{-0.01676131871895284,
0.3383293774761414}, {-0.017794560024898265,
0.3384713748093851}}, {{-0.02316453209371017,
0.30003332292421014}, {-0.02303473396180133,
0.30025241692412363}}, {{-0.0050985101499539795,
0.3319329710614432}, {-0.004423377968477279,
0.331138019882757}}, {{-0.022940760033693074,
0.32789850079501953}, {-0.022828922220079186,
0.3276629658063637}}, {{-0.0783810716952149,
0.298695519500128}, {-0.0639031537148027,
0.298252896713245}}, {{-0.02718659256118707,
0.29769509804809235}, {-0.026932527807086413,
0.2977124426890192}}, {{-0.17171167689644382,
0.3070770988467576}, {-0.17220917492167956,
0.3080208312611169}}, {{-0.17095911325079685,
0.3283711252842246}, {-0.17034984968281547,
0.3292468724279576}}, {{-0.16485224962736336,
0.3221020502606631}, {-0.16457739200185012,
0.3226685886633482}}, {{-0.017794560024898265,
0.3384713748093851}, {-0.018833798753801673,
0.3385593162859895}}, {{-0.17057289276109477,
0.30527359420929356}, {-0.16993469074439835,
0.30441870629797974}}, {{-0.0961177437851361,
0.291104503068724}, {-0.0818949634250089,
0.290426822082235}}, {{-0.0957179577176685,
0.299494984050185}, {-0.0814951773575412,
0.29881730306369597}}, {{-0.16593153282153464,
0.3172180885150769}, {-0.16592100502526022,
0.31658848416191104}}, {{-0.02303473396180133,
0.30025241692412363}, {-0.02291625928387132,
0.3004778353939403}}, {{-0.16576683647257845,
0.3190982606387603}, {-0.16585434402254567,
0.318474678322848}}, {{-0.115187648877698,
0.333911086244378}, {-0.099319376257251,
0.334624189080969}}, {{-0.02250840573536552,
0.3266723465370751}, {-0.022461075109788706,
0.3264159401422299}}, {{-0.09711594348365293,
0.3430650032516095}, {-0.09969648248885887,
0.34301571998361635}}, {{-0.024660387516507672,
0.3298194701710857}, {-0.024446071569157422,
0.32967096730193374}}, {{-0.15947637636786122,
0.29739786247756983}, {-0.16049398602111695,
0.2977181837984753}}, {{-0.022729514890690448,
0.32742192097588857}, {-0.022828922220079186,
0.3276629658063637}}, {{-0.16319556509908598,
0.3247693743061922}, {-0.1635815832005517,
0.32427187807368313}}, {{-0.17095911325079685,
0.3283711252842246}, {-0.1715219927487946,
0.32746486824245347}}, {{-0.17424002851016965,
0.3151652394208606}, {-0.1743133329395534,
0.3162295521642113}}, {{-0.17420039487710307,
0.3194251703707574}, {-0.17429348925235025,
0.31836240577202296}}, {{-0.1565539214362742,
0.3053156294928492}, {-0.1571635818780663,
0.3054731941517472}}, {{-0.16612812978222688,
0.3007025728681141}, {-0.16696481100080182,
0.3013644638663228}}, {{-0.16467903858544197,
0.31174333670203586}, {-0.1643853934095711,
0.3111863043989262}}, {{-0.13480393096839502,
0.34077895057190805}, {-0.12804326682550607,
0.34143048753720934}}, {{-0.164273433498032,
0.3232200609690685}, {-0.16457739200185012,
0.3226685886633482}}, {{-0.022809415381982865,
0.30070899360053127}, {-0.022714479408088534,
0.30094529192195113}}, {{-0.16057623728510573,
0.30705932259071705}, {-0.16004447098197933,
0.30672207331365464}}, {{-0.09717236780491953,
0.33466519275993967}, {-0.09931937625725092,
0.3346241890809694}}, {{-0.0223999999999996,
0.325636824663719}, {-0.0223999999999996,
0.302690541698566}}, {{-0.00992861401320636,
0.33587244261444776}, {-0.009041550066031922,
0.335323927899437}}, {{-0.15949588000939435,
0.30641294482771697}, {-0.16004447098197933,
0.30672207331365464}}, {{-0.16590929240988667,
0.3178473879987169}, {-0.16585434402254567,
0.318474678322848}}, {{-0.006568396687868179,
0.3334119838797717}, {-0.007359153868518696,
0.334092023525829}}, {{-0.00002719377097363207,
0.3196359442287738}, {-0.00010870113377766444,
0.32067570736947887}}, {{-0.02583138743504106,
0.3303843982146031}, {-0.026081010879205578,
0.33045971463750307}}, {{3.5213168757718605*^-16,
0.30059334586997}, {3.73217884139672*^-16,
0.31859334586997}}, {{-0.133311219642531,
0.293704611173041}, {-0.100624287660109,
0.29137258650724}}, {{-0.023789803523763194,
0.2992312814592999}, {-0.02397061314593002,
0.2990519560110863}}, {{-0.09571795771766846,
0.29949498405018493}, {-0.10002651535545698,
0.299751289764415}}, {{-0.1633365381686077,
0.30961720440672075}, {-0.16293410296342192,
0.30913289212972694}}, {{-0.0238535412754112,
0.32916139988845045}, {-0.024042099171966737,
0.3293414841661694}}, {{-0.02583138743504106,
0.3303843982146031}, {-0.02558602963996038,
0.33029617134892064}}, {{-0.02558602963996038,
0.33029617134892064}, {-0.025345604714332153,
0.33019527396257353}}, {{-0.0449731659616852,
0.29789667279542403}, {-0.0280940376586573,
0.29769725829732896}}, {{-0.1725026316455957,
0.32557071786870867}, {-0.17203696376766003,
0.32653055565838185}}, {{-0.17405213828418334,
0.3204816528068072}, {-0.17420039487710307,
0.3194251703707574}}, {{-0.17305364983193894,
0.3099794839639255}, {-0.17265690341795825,
0.3089891671267368}}, {{-0.15872690806364326,
0.3281712493076333}, {-0.1581446064921331,
0.3284109102260923}}, {{-0.16564700675086885,
0.31971644613989636}, {-0.16576683647257845,
0.3190982606387603}}, {{-0.024777780966299914,
0.29843331638866044}, {-0.02456442659753365,
0.2985723474973141}}, {{-0.16852930413265976,
0.3028142292006602}, {-0.16776592565280904,
0.30206898531338117}}, {{-0.09453629942331661,
0.342981057317432}, {-0.0188337987538017,
0.338559316285989}}, {{-0.02618022798853192,
0.29784160818282895}, {-0.025934928004331545,
0.2979100015567508}}, {{-0.02416031856136073,
0.2988820690157}, {-0.024358427676212165,
0.2987220611582121}}, {{-0.02397061314593002,
0.2990519560110863}, {-0.02416031856136073,
0.2988820690157}}, {{-0.1592959532338122,
0.3279016198019645}, {-0.15985020089541102,
0.3276027519287627}}, {{-0.143169407399232,
0.29466514291458284}, {-0.133311219642531,
0.293704611173041}}, {{-0.16580184752261332,
0.31533517751737167}, {-0.16569354052258883,
0.3147148694731183}}, {{-0.006568396687868179,
0.3334119838797717}, {-0.005814165101646035,
0.33269164676889584}}, {{-0.02499793734353272,
0.29830532847747804}, {-0.024777780966299914,
0.29843331638866044}}, {{-0.16342779055730133,
0.29899000205256}, {-0.16435722154391225,
0.2995137321320412}}, {{-0.023200477620708284,
0.32835049593817933}, {-0.023347651124051683,
0.32856572694744296}}, {{-0.023064724202343147,
0.3281278854334021}, {-0.023200477620708284,
0.32835049593817933}}, {{-0.16057623728510573,
0.30705932259071705}, {-0.16108973877142355,
0.30742377930909276}}, {{-0.024660387516507672,
0.3298194701710857}, {-0.024882153503301283,
0.3299565988498384}}, {{-0.012744118559842758,
0.3372307326107764}, {-0.011782418857329856,
0.3368271430653881}}, {{-0.0017156888803179662,
0.326697910440549}, {-0.002163040134773521,
0.32764005039517213}}, {{-0.0223999999999996,
0.325636824663719}, {-0.022406798442743105,
0.32589747425341997}}, {{-0.16538093583401997,
0.31349533908630195}, {-0.16517748475198532,
0.31289941951686434}}, {{-0.16342779055730133,
0.29899000205256}, {-0.1624723720816022,
0.2985153330191076}}, {{-0.159108718071151,
0.3369147786913791}, {-0.15807103423313,
0.33716246277915196}}, {{-0.02545635562717863,
0.29808378073754377}, {-0.025693428401407696,
0.2979907956012883}}, {{-0.16234856729533484,
0.3257008091005413}, {-0.16278418842931225,
0.3252461150235488}}, {{-0.003790604496207962,
0.330308955004866}, {-0.0032019104828343607,
0.32944803096781144}}, {{-0.0017156888803179662,
0.326697910440549}, {-0.0013180595627630184,
0.32573373111864834}}, {{-0.09611774378513621,
0.291104503068723}, {-0.10062428766010907,
0.2913725865072393}}, {{-0.1733983396816671,
0.310989099763386}, {-0.17369003946652273,
0.3120152802497241}}, {{-0.17265690341795825,
0.3089891671267368}, {-0.17220917492167956,
0.3080208312611169}}, {{-0.1655531098533738,
0.31410103586116495}, {-0.16538093583401997,
0.31349533908630195}}, {{-0.1609083437046747,
0.32692061568805486}, {-0.16140937315446863,
0.32653919470481063}}, {{-0.16250701729045952,
0.30867017158342486}, {-0.16293410296342192,
0.30913289212972694}}, {{-0.1569465738102524,
0.3287978129901419}, {-0.156334087252201,
0.32894400701268106}}, {{-0.02361835871310968,
0.2994195801920229}, {-0.02345672343999681,
0.29961636376433226}}, {{-0.1725026316455957,
0.32557071786870867}, {-0.17291773524522516,
0.3245879543383512}}, {{-0.1611384428627671,
0.33625928227294805}, {-0.16212498684755708,
0.335853245179691}}, {{-0.16049398602111695,
0.2977181837984753}, {-0.16149355361319787,
0.2980910105462918}}, {{-0.022503423487267513,
0.30167884092513675}, {-0.022561284768092122,
0.3014308453444776}}, {{-0.011782418857329856,
0.3368271430653881}, {-0.010843065856772359,
0.336373968949508}}, {{-0.007359153868518696,
0.334092023525829}, {-0.008184286276630927,
0.334729916422829}}, {{-0.17291773524522516,
0.3245879543383512}, {-0.1732811503690476,
0.3235849266204875}}, {{-0.17369003946652273,
0.3120152802497241}, {-0.17392795919535808,
0.3130552462865045}}, {{-0.17116575668310063,
0.30616052573145847}, {-0.17057289276109477,
0.30527359420929356}}, {{-0.08149517735754128,
0.298817303063696}, {-0.07838107169521498,
0.2986955195001285}}, {{-0.151503418460592,
0.304406838304457}, {-0.14213853479564478,
0.30300164707850935}}, {{-0.16402808627327933,
0.3348900884634228}, {-0.1630890716399921,
0.33539643486016946}}, {{-0.013725549740165472,
0.33758364007350633}, {-0.012744118559842758,
0.3372307326107764}}, {{-0.022458263874178742,
0.3019294608469123}, {-0.022425923072385,
0.3021820550043753}}, {{-0.14851078030823212,
0.33892608930990176}, {-0.15807103423313001,
0.337162462779152}}, {{-0.17433116928861334,
0.31729623722536016}, {-0.1743133329395534,
0.3162295521642113}}, {{-0.0950261039467197,
0.334595349742704}, {-0.09717236780491953,
0.33466519275993967}}, {{-0.1715219927487946,
0.32746486824245347}, {-0.17203696376766003,
0.32653055565838185}}, {{-0.024042099171966737,
0.3293414841661694}, {-0.024239788467129365,
0.3295114940776837}}, {{-0.115187648877698,
0.333911086244378}, {-0.12112119567347102,
0.3335459537037523}}, {{-0.02263169762510149,
0.3011861174028509}, {-0.022714479408088534,
0.30094529192195113}}, {{-0.12738864504220201,
0.333056034103054}, {-0.13384723695743,
0.33243360836386193}}, {{-0.026428692048441692,
0.2977857928912122}, {-0.02618022798853192,
0.29784160818282895}}, {{-0.1569465738102524,
0.3287978129901419}, {-0.15755062552794172,
0.3286199534995984}}, {{-0.16531176555681543,
0.32092994908488376}, {-0.16509726199592512,
0.32152198007933014}}, {{-0.159108718071151,
0.3369147786913791}, {-0.16013211147715362,
0.3366134464966566}}, {{-0.023789803523763194,
0.2992312814592999}, {-0.02361835871310968,
0.2994195801920229}}, {{-0.02316453209371017,
0.30003332292421014}, {-0.023305316984615142,
0.29982112172172065}}, {{-0.16234856729533484,
0.3257008091005413}, {-0.1618898814609297,
0.32613222511940926}}, {{-0.022406798442743105,
0.32589747425341997}, {-0.02242717528344411,
0.3261574150385962}}, {{-0.02667967567091477,
0.2977427004661773}, {-0.026428692048441692,
0.2977857928912122}}, {{-0.16140937315446863,
0.32653919470481063}, {-0.1618898814609297,
0.32613222511940926}}, {{-0.1692528790331332,
0.3035981772336514}, {-0.16852930413265976,
0.3028142292006602}}, {{-0.02263169762510149,
0.3011861174028509}, {-0.022561284768092122,
0.3014308453444776}}, {{-0.12177581745677403,
0.341920407137907}, {-0.115564755109306,
0.3423026171470251}}, {{-0.16531176555681543,
0.32092994908488376}, {-0.1654951793842912,
0.3203275606355335}}, {{-0.008184286276630927,
0.334729916422829}, {-0.009041550066031922,
0.335323927899437}}, {{-0.13480393096839502,
0.34077895057190805}, {-0.138034064595464,
0.340408654253483}}, {{-0.02350584449211901,
0.3287729931669158}, {-0.023674627537488186,
0.3289717309615873}}, {{-0.013725549740165472,
0.33758364007350633}, {-0.01472404351682356,
0.33788490576510627}}, {{-0.0639031537148028,
0.29825289671324495}, {-0.061660627893130995,
0.29819810751174}}, {{-0.04497316596168523,
0.29789667279542326}, {-0.046157143827387906,
0.297914496015335}}, {{-0.022406484973584426,
0.3024359681709503}, {-0.022399999999999913,
0.302690541698566}}, {{-0.158354208447265,
0.30588232057279774}, {-0.15776421977096358,
0.30566226185823286}}, {{-0.13384723695743,
0.332433608363862}, {-0.13707737058449998,
0.33206331204543804}}, {{-0.15739809597472298,
0.296918061589936}, {-0.152964624886857,
0.29613490529095704}}, {{-0.1658208075617013,
0.33373440309693436}, {-0.16666965910887294,
0.3330881939930908}}, {{-0.022940760033693074,
0.32789850079501953}, {-0.023064724202343147,
0.3281278854334021}}, {{-0.1738491209870721,
0.3215289918789799}, {-0.17359189280402723,
0.3225643511484479}}, {{-0.0950261039467197,
0.334595349742704}, {-0.027108449688450102,
0.330628317267724}}, {{-0.0616606278931308,
0.29819810751174}, {-0.0461571438273879,
0.297914496015335}}, {{-0.14462682853728,
0.33103518527674103}, {-0.147200993609053,
0.330628833209078}}, {{-0.1615835847589727,
0.30781445643486477}, {-0.16205643779747447,
0.3082302959231285}}, {{-0.17429348925235025,
0.31836240577202296}, {-0.17433116928861334,
0.31729623722536016}}, {{-0.16592100502526022,
0.31658848416191104}, {-0.1658777375327947,
0.3159602800548601}}, {{-0.1658208075617013,
0.33373440309693436}, {-0.16493948767647237,
0.3343355772937574}}, {{-0.00002719377097363207,
0.3196359442287738}, {3.6948222259525213*^-16,
0.31859334586997}}, {{-0.16205643779747447,
0.3082302959231285}, {-0.16250701729045952,
0.30867017158342486}}, {{-0.16435722154391225,
0.2995137321320412}, {-0.1652581479252421,
0.30008510487417167}}, {{-0.024446071569157422,
0.32967096730193374}, {-0.024239788467129365,
0.3295114940776837}}, {{-0.16580184752261332,
0.31533517751737167}, {-0.1658777375327947,
0.3159602800548601}}, {{-0.0032019104828343607,
0.32944803096781144}, {-0.002658896809373818,
0.3285575889487024}}, {{-0.121121195673471,
0.333545953703752}, {-0.12738864504220201,
0.333056034103054}}, {{-0.15893195007983538,
0.30613277432504504}, {-0.158354208447265,
0.30588232057279774}}, {{-0.16394119730653092,
0.3237549736620164}, {-0.164273433498032,
0.3232200609690685}}, {{-0.16038815001632004,
0.3272754550920334}, {-0.15985020089541102,
0.3276027519287627}}, {{-0.15739809597472298,
0.296918061589936}, {-0.15844348057804805,
0.29713091408852776}}, {{-0.022569038450355353,
0.32692593695745403}, {-0.02250840573536552,
0.3266723465370751}}, {{-0.14213853479564478,
0.30300164707850935}, {-0.13271344733787804,
0.3020833144302151}}, {{-0.1559368895484579,
0.30518999460343643}, {-0.1565539214362742,
0.3053156294928492}}, {{-0.025934928004331545,
0.2979100015567508}, {-0.025693428401407696,
0.2979907956012883}}, {{-0.022642808371541714,
0.32717602179538546}, {-0.022569038450355353,
0.32692593695745403}}, {{-0.15776421977096358,
0.30566226185823286}, {-0.1571635818780663,
0.3054731941517472}}, {{-0.09453629942331661,
0.342981057317432}, {-0.09711594348365293,
0.3430650032516095}}, {{-0.15755062552794172,
0.3286199534995984}, {-0.1581446064921331,
0.3284109102260923}}, {{-0.145936615236459,
0.339332441377564}, {-0.148510780308232,
0.338926089309901}}, {{-0.17305364983193894,
0.3099794839639255}, {-0.1733983396816671,
0.310989099763386}}, {{-0.022425923072385,
0.3021820550043753}, {-0.022406484973584426,
0.3024359681709503}}, {{-0.02511076646419278,
0.3300819804336035}, {-0.025345604714332153,
0.33019527396257353}}, {{-0.00992861401320636,
0.33587244261444776}, {-0.010843065856772359,
0.336373968949508}}, {{-0.00043362294146330525,
0.3227354333633945}, {-0.0006761538014226468,
0.32374979504491025}}, {{-0.1615835847589727,
0.30781445643486477}, {-0.16108973877142355,
0.30742377930909276}}};


Looks random:

Graphics[Table[{Hue[i/Length[randomLines]],
Arrow@randomLines[[i]]}, {i, Length[randomLines]}] ]


Sort into paths:

sorted = mySort[randomLines];


This is what I expect:

Graphics[{
Arrowheads[.02],
Table[{PointSize[0.015], Hue[i/Length[sorted]],
Point[sorted[[i, 1, 1]]], Arrow@sorted[[i]], GrayLevel[0],
Text[i, sorted[[i, 1, 1]], {0, 0}]}, {i, Length[sorted]}]
}]


• I think you can get this working MUCH better using Nearest[randomLines] to get a NearestFunction. Then use DataStructure with a "DynamicArray", "LinkedList", or "DoublyLinkedList" to collect the segments of each spiral. I can't write it for you because my version is too old (Doesn't have DataStructure). Commented Nov 18, 2021 at 20:09
• Other potentially useful resources are FindShortestTour and this very similar question. Commented Nov 18, 2021 at 20:50
• Also, define randomLines using: randomLines=CreateDataStructure["HashSet"'] and "Insert" each segment to randomLines. Then each time you "Append" a segment to a spiral, you "Remove" the segment from randomLines. In some cases it could be tricky make the spirals correctly. Commented Nov 18, 2021 at 23:34

## 1 Answer

I think this should do the trick and also should have decent performance:

TOL = 0.5 Sqrt[Min[Total[(randomLines[[All, 1]] - randomLines[[All, 2]])^2, {2}]]];
(*pts=DeleteDuplicates[Flatten[randomLines,1],Norm[#1-#2] <TOL&];*)

pts = Flatten[randomLines, 1];
clusters = DeleteDuplicates[Sort /@ Nearest[pts -> "Index", pts, {\[Infinity], TOL}]];
pts = pts[[clusters[[All, 1]]]];

edges = Partition[Flatten[Nearest[pts -> "Index", Flatten[randomLines, 1], {\[Infinity], TOL}]], 2];
A = KirchhoffMatrix[edges];
chains = Table[
Module[{L, cycles, perm},
L = A[[c, c]];
cycles = SparseArrayHamiltonianCycle[L];
If[Length[cycles] == 0,
perm = SparseArrayMinimumBandwidthOrdering[L][[2, 1]];
,
perm = cycles[[1]];
];
pts[[c[[perm]]]]
],
{c, SparseArrayStronglyConnectedComponents[A]}];

Graphics[Table[{RandomColor[], Arrow[c]}, {c, chains}]]


For the synthetic example, we obtain the following:

For the real world example, we get:

This is how this works:

• First we determine the smallest edge length in order to determine a reasonable tolerance parameter TOL. We assume from here on that the distance between points that are to be identified with each other aare considerably smaller than this minimal edge length.

• We use DeleteDuplicates Nearest to perform the actual identification with respect to this tolerance parameter.

• We determine the edges edges of the underlying graph (again using the tolerance TOL).

• We build the graph Laplacian A of the underlying graph (omitting the creation of  Graph data structure for performance reasons - as usual).

• Then we go through the connected compontents and consider each component's graph Laplacian L separately. If we find a Hamiltonian cycle, we use it as reordering of that component. Otherwise, the connected component c is a linear chain. In that case, we use the minimum bandwidth reordering. This works because a linear chain must have a reordering of vertices that brings the Laplacian into tridiagonal form. And the graph Laplacian can be tridiagonal only if the indices of neighboring vertices differ by $$\pm 1$$. So any one of the two possible minimal bandwidth reorderings for c` will do.

• Henrik, this is awesome! Your algorithm sorts my ~10000 lines in 0.11 seconds, compared to my clumsy approach using 369 seconds. More than 3000 times faster! The algorithmic complexity is also excellent, I haven't checked in detail, but it seems to be O[n] or even better. Commented Nov 22, 2021 at 7:23
• I am glad to see you happy! =D Commented Nov 22, 2021 at 7:26
• The complexity of the ordering operations is probably indeed O(n). However, we use ˋNearestˋ to identify end points. It involves a space partition tree and thus have complexity O(n log(n)). Commented Nov 22, 2021 at 7:37