9
$\begingroup$

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]}] ]

Random lines as input

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]}] ]

Sorted lines

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]}] ]

Unsorted real world data

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]}]
  }]

Sorted real world data

$\endgroup$
3
  • 2
    $\begingroup$ 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). $\endgroup$
    – Ted Ersek
    Nov 18 '21 at 20:09
  • 1
    $\begingroup$ Other potentially useful resources are FindShortestTour and this very similar question. $\endgroup$ Nov 18 '21 at 20:50
  • $\begingroup$ 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. $\endgroup$
    – Ted Ersek
    Nov 18 '21 at 23:34
6
$\begingroup$

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 = SparseArray`HamiltonianCycle[L];
   If[Length[cycles] == 0,
    perm = SparseArray`MinimumBandwidthOrdering[L][[2, 1]];
    ,
    perm = cycles[[1]];
    ];
   pts[[c[[perm]]]]
   ],
  {c, SparseArray`StronglyConnectedComponents[A]}];

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

For the synthetic example, we obtain the following:

enter image description here

For the real world example, we get:

enter image description here

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – AxelF
    Nov 22 '21 at 7:23
  • $\begingroup$ I am glad to see you happy! =D $\endgroup$ Nov 22 '21 at 7:26
  • $\begingroup$ 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)). $\endgroup$ Nov 22 '21 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.