Connect the dots

Given a cryptographically random set of points in 2 dimensional space, connect them all such that they form a polygon without any lines crossing using less than brute force. C/C++ only. Inline assembly accepted as long as it compiles under VS2005 for an x86 chip.

2 winners, The fastest correct solution over a series of runs. and the most elegant (IMO) solution.

the points are in 2 arrays double X[] and double Y[] of size Z

Your function should put them into a second set of arrays NewX[] and NewY[] in the order in which you would draw them if you were playing connect the dots.

You gonna provide any examples of the arrays?

Sorry, Ill have to break it into 2 arrays later, but here is a sample fo teh data.

Code:

---

static double xy[] = {
  +0.24717813445522, +0.02082172948434, -0.54598955097501,
  +0.21429966044207, +0.30628276008585, -0.08937024523937,
  +0.00608976924388, +0.15525969818008, +0.19699708788227,
  -0.18292105651463, -0.07866442525449, -0.08077552252864,
  -0.38841903653091, -0.32108917225941, -0.23791744660622,
  -0.54155435503457, +0.15025775325269, +0.20213827294554,
  +0.13792705310687, -0.34229749552826, -0.30180704637825,
  -0.61689548091133, +0.19350272948203, -0.49550381384977,
  +0.207556223053, -0.36155069247693, +0.09251075966135,
  -0.21360951722592, -0.60683966613443, -0.19388219851182,
  -0.57318156421493, -0.37295514377154, -0.49254217610763,
  -0.52311606870951, -0.81598679194384, -0.60770289532909,
  -0.57169624861062, -0.77289423234198, -0.8579634987407,
  -0.28073441533004, -0.24758467281003, -0.2781341329129,
  +0.02503460909893, -0.37360503368646, +0.02405134391243,
  +0.01404207203429, -0.42144247849547, -0.04678314664725,
  -0.34112882662998, +0.20633487426881, -0.21586462541067,
  -0.24002422131989, +0.27192785777131, +0.00710887592135,
  +0.46008307039401, -0.31692665508853, +0.17972718200465,
  -0.39131685692196, -0.33626406027955, -0.27646678673399,
  -0.51095045537915, +0.01606252472785, +0.02533744122294,
  -0.14699268622176, +0.32496419347125, +0.21586210564083,
  +0.09140678877623, -0.58732708921714, -0.52255691412251,
  -0.22782761317037, +0.45273769885837, +0.20270327548011,
  -0.24859032788031, +1.07970611654407, -0.27367208628886,
  +0.47492459174975, +0.38628433190159, +0.19867763249625,
  -0.34071117057043, +0.34457849792056, -0.47391897036373,
  +0.14701541543267, +0.46403607492228, +0.36077176426776,
  -0.08426243877225, -0.52106322744545, -0.54269882941978,
  +0.11778537118401, -0.32471237733391, +0.45677487056787,
  -0.26930585140633, +0.21489487235916, -0.21467402103422,
  -0.24176978569218, +0.03826613894507, -0.03134189142814,
  -0.2864204783175, -0.27472276700468, -0.21435261127852,
  -0.61136467314114, -0.65031857737459, -0.71099873013951,
  -0.33722253869694, -0.44406636679324, +0.23760182247812,
  +0.0963230048725, +0.41787588395407, +0.07903822388725,
  -0.18087312122648, -0.16792274990047, -0.13431583361987,
  +0.39221948176618, -0.27955427306907, +0.56270066523121,
  -0.03684777528722, +0.25616163368586, -0.2635834107904,
  +0.4634633222287, +0.55732093023052, +0.14474594265893,
  +0.58553703320029, -0.10556896024389, +0.21747631650481,
  +0.20626247006429, -0.39445052717604, -0.14025988584292,
  -0.3891941746288, -0.37421038059905, +0.16229643043424,
  +0.08650551867501, +0.35315502450535, -0.00865458242511,
  -0.24926082127775, +0.30021865520101, -0.20628243179578,
  -0.0732672321639, -0.1119006553633, -0.32093614581027,
  -0.45357374415143, -0.54802220932955, -0.83453378642397,
  -0.91519202455177, -0.88620073885738, -1.03070387501332,
  -0.35870138156255, -0.60401400094734, -0.48760347140126,
  -0.27710802470545, +0.15251851429287, -0.3070129204625,
  +0.15244694510828, +0.30005340183598, -0.05812453392597,
  -0.04542326769311, +0.21326326438777, -0.30645346855461,
  -0.0177260913241, -0.39619617015147, -0.55575108986352,
  +0.14187876218073, -0.28171564511138, +0.1121788101384,
  -0.09327239461615, +0.10859292756902, +0.00645798447239,
  -0.27531376295251, +0.0309768135588, +0.19208570909143,
  +0.57716016799867, -0.18223325464688, -0.1031702073652,
  +0.43093313760417, +0.18954789343182, -0.28353395468339,
  +0.3711092206467, -0.07616111007023, +0.02220969853131,
  -0.27608872291755, -0.22219880026313, -0.6521441851107,
  +0.09085400005858, -0.64343482733462, +0.27505542543339,
  +0.43667471099702, +0.6880973012419, +0.5894286713711,
  +0.07645701600106, +0.55545131622823, +0.17130666823399,
  +0.28839659840887, +0.6563101003953, +0.18264896697978,
  +0.67577157187598, -0.06233213750559, +0.44053449416648,
  +0.13579926807137, +0.55955832417793, +0.6182508373005,
  +0.13490657045522, +0.24597354402292, +0.9289644590846,
  +0.54278056605309, +0.50417430692439, +0.71215898688773,
  -0.04638958089758, +0.41779642789049, +0.49134728744022,
  +0.77134730893516, +0.17199251137721, -0.05430198990225,
  +0.14051563217802, +0.07856282258119, -0.17170570944387,
  -0.19017131093673, -0.09437745586266, -0.48554682963749,
  -0.49683399247901, -0.06140395560941, -0.32482274246911,
  +0.02147027101269, +0.24395216951875, +0.03728982738655,
  -0.03410034895808, -0.71884799867434, +0.36965266055343,
  +0.3847032096535, +0.43894096588645, -0.28156547586326,
  -0.06803796000201, -0.31132688657093, +0.45140159225924,
  -0.31124668787608, -0.40359291783776, -0.11691222105678,
  -0.22428848961892, -0.21483742332547, +0.24107223068967,
  -0.12007028149619, +0.06631569284303, +0.26407084091728,
  +0.27676093475321, +0.54548148971922, -0.29305218356286,
  +0.07230294370932, +0.26327546804702, +0.16404758267897,
  +0.06047079195426, +0.00479953696208, -0.58263263349151,
  -0.27987826593289, -0.08857430766358, -0.21891464802644,
  -0.26264398797116, -0.10609181326971, -0.39911287000453,
  -0.50567191908136, -0.13534390541748, +0.15499522167941,
  +0.41409649914409, -0.37209625894587, +0.28164318312995,
  -0.18516892043422, +0.34795522128945, -0.12025217787796,
  +0.36945939235635, -0.08246440953477, -0.2801396375675,
  -0.01828732449772, +0.36138243994445, +0.65333569003108,
  -0.41351746834431, +0.01377213093012, -0.28363394356594,
  +0.53112670988098, +0.25489429494858, -0.15678167592089,
  -0.51152896694162, +0.62435362275827, -0.27536161631934,
  -0.23249655898041, +0.04906321956975, -0.08998792649869,
  +0.37837508049211, -0.45269134955392, +0.55045850641383,
  +0.21261404247632, +0.44003559149431, +0.82340518955305,
  +0.445262323546, +0.34142894323607, +0.5301258537868,
  -0.17854763686075, -0.11132690601401, -0.22582155275813,
  -0.42196646285147, -0.38988687731059, +0.27848174768624,
  +0.16038315333751, -0.45407946279175, -0.07254547126624,
  -0.41362235484692, -0.1753403590346, -0.01003805818281,
  -0.61801459675762, -0.0513087300121, -0.07283077224535,
  -0.25469994675442, -0.61716879017861, +0.13178897133861,
  -0.26137843888292, +0.1788214054918, +0.13388112392904,
  -0.29816932844218, -0.06318035190265, +0.13273882453647,
  +0.37349438071434, -0.47474373654238, -0.3727647740325,
  +0.46221631307764, -0.27419847853254, +0.08029803109226,
  -0.77381327709314, -0.28864256358114, +0.25602910186291,
  -0.34155778245681, -0.70577254877508, -0.87396135026355,
  -0.3024586434298, -0.83153225965922, -0.53828456732631,
  -0.11843172107656, -0.1512169534813, -0.78358757004409,
  -0.52012479322719, -0.4843392922301, +0.07660732819818,
  -0.25006762696488, +0.37177565325414, +0.56878656028561,
  +0.06210288136675, +0.13872849943233, -0.23710447446717,
  -0.15273659748541, +0.03118333731328, +0.49848376350023,
  +0.00255779602306, +0.32870565652773, +0.09737386887084,
  +0.1033981293991, +0.13471874126302, -0.44192887400514,
  -0.35613024456411, -0.15540486370719, -0.20370421376982,
  -0.38183235585371, +0.22487676038257, -0.02172277109433,
  +0.13211826747742, -0.45748213520045, +0.41032512336937,
  +0.45315049455325, -0.06962693955764, -0.40381437663747,
  +0.21185602390423, -0.17924374560256, +0.07908325358075,
  +0.2143729324832, +0.47832952688827, +0.74184516637295,
  +0.56073576119816, +0.40082821630104, +0.36379859928824,
  +0.3741528228697, +0.75695274134917, +0.3568173443541,
  +0.54895869517295, +0.94157020495172, +0.96261085532786,
  +0.78275255405231, +0.73128472437915, +0.59117146965788,
  +0.54869408743618, +0.26074980345217, +0.13364184630403,
  -0.13181476931815, -0.17566527148839, -0.02903515263051,
  -0.04830550987904, +0.04830322462284, -0.25567048687926,
  +0.41951379030808, +0.29995783386149, +0.23060064460384,
  +0.29492262740618, -0.23695278936672, +0.00893408669023,
  +0.11055193041802, -0.1101093754899, -0.48876040364852,
  -0.34909968477838, -0.08484418619829, -0.39506722711688,
  -0.22171981471354, -0.17484636081612, -0.24365574109129,
  -0.14797864817286, -0.18015512584086, -0.31829549379751,
  +0.2715885112246, -0.09827391774293, +0.36666838712237,
  +0.27342471236828, +0.00731673626888, -0.16573741710145,
  +0.06365516608851, -0.10154901056011, +0.258663330538,
  +0.38804082637325, +0.27828270056447, +0.39549550787056,
  +0.46837588165068, +0.13498875413482, +0.21056087112191,
  +0.6372409664444, +0.65179607256995, -0.02094733104483,
  +0.0281089142353, -0.45352398933301, -0.1451520375231,
  +0.04705315361112, -0.51272074209728, +0.06574137092399,
  -0.71405006409231, -0.40775219981645, +0.24614372006916,
  +0.00021716563305, -0.81623275083742, -0.44295810447182,
  -0.93231604950805, -0.12955417086516, -0.59814920705686,
  -0.44745107221363, -0.47042226789777, -0.16121808595697,
  +0.14043148212865, +0.20356937394121, +0.4520932223466,
  +0.16838611472425, -0.14098876733741, -0.27477880171968,
  +0.73693575414045, -0.30114491772498, -0.23398482563516,
  -0.68804949290063, -0.31083364230049, -0.31801925020273,
  +0.47517576352541, +0.09502283990559, +0.03349266929168,
  +0.29917443953063, +0.27564786157589, +0.15251035460234,
  +0.30880443926367, +0.62376618498518, +0.29371333911853,
  +0.03097135399755, +0.47104642131927, +0.68922353968835,
  +0.26229972882497, +0.77355412216623, +0.10672006857848,
  +0.32124290109518, -0.03552319936568, +0.60131994404343,
  +0.39749814148842, +0.69925872999253, +0.53597236562032,
  +0.28364114960587, +0.22670414560981, +0.72775466010079,
  +0.40659567705574, +0.63849208528651, -0.02350545475222,
  +0.43400530083249, +0.5096032520493, +0.59727596923298,
  +0.37588581957901, +0.14528554188695, -0.67742348987121,
  -0.73688060976142, -0.43824687855863, -0.02659370511276,
  -0.39276605061041, -0.32030205437976, -0.16076255754077,
  -0.03498552720317, -0.63267172380935, -0.43713079887437,
  -0.08105412041736, -0.10638232140572, -0.60343081984965,
  +0.26678290363759, +0.34689380219464, +0.07205782339109,
  +0.1022700230876, +0.12005758854685, -0.34494691043823,
  +0.15180200526256, -0.28431132397002, -0.03079313000266,
  -0.35866010323657, +0.16870146213096, -0.0167051353687,
  -0.50045734800919, -0.00959207207573, -0.30783910679595,
  -0.35930551319901, -0.08710903915749, +0.04415356764208,
  -0.32647411059994, -0.54380776212866, -0.60172721235905,
  +0.32258830312054, -0.35477665994805, +0.19909561097679,
  -0.17159234030403, -0.1912557917602, -0.26771037048307,
  -0.64756088078322, -0.41662234864945, -0.16658793727788,
  -0.81039955933168, -0.17544503056435, -0.45405414531284,
  -0.61145398471869, -0.62260305268276, -0.43921492794061,
  -0.57637422672521, -0.19775013669941, -0.06254300495423,
  -0.66717308968757, -0.75344237571453, -0.58707804883087,
  -0.34017371833862, -0.76417626624569, -0.78679745786137,
  -0.33154356395582, -0.18765662903972, -0.08243469352266,
  +0.04095411122805, -0.18442929034129, -0.46925832262058,
  +0.99309056289628, -0.42854237766121, -0.06890299793973,
  -0.36372441830823, +0.02658618640926, +0.49244486213541,
  -0.00488360449389, -0.04753754553324, -0.74943536680959,
  -0.05179212345699, +0.36890662928701, -0.61904832250656,
  -0.66860653041965, +0.18709868549472, -0.27233045852707,
  -0.1895491565614, -0.43024118301136, +0.03234130552323,
  -0.53600902815796, -0.53165056236188, -0.06744507650621,
  +0.2508515338959, +0.06476688625386, +0.63507644058091,
  +0.11916430370518, +0.06977620641202, +0.13700962103091,
  +0.48187738468404, +0.56274015994983, +0.14678658939236,
  +0.13660815434147, +0.67200758480022, -0.02140418645972,
  -0.33205124573157, -0.31945594171182, +0.07494978923881,
  -0.47728010705365, +0.06262693842314, -0.20457345228184,
  -0.24062218437443, -0.02920088159364, +0.20821586368845,
  +0.11440146158148, -0.12628163044382, +0.16303624704608,
  -0.21882578379283, -0.4556100170044, -0.25121176785771,
  -0.27044506019903, -0.06123614301889, +0.13942185784638,
  +0.04843325140809, -0.13820373496115, -0.30916050927882,
  -0.35223069337949, +0.46774736257423, +0.22816353033561,
  -0.15232286703076, +0.1735138059338, +0.49436725344162,
  +0.38919951219323, +0.26035175465216, +0.48022063903414,
  -0.09955097599644, +0.33412063283879, -0.23757707373341,
  -0.25659179089524, -0.07402417091149, -0.37995213801703,
  -0.31049044298883, +0.49409899481662, -0.65287134049169,
  +0.35507465654789, +0.51236853445572, +0.16624767509004,
  -0.26358115164262, +0.43624817516605, -0.42842277121181,
  -0.21596437260428, +0.22531751153034, -0.6355053130978,
  -0.16620093576937, -0.56918779501097, +0.1966715086057,
  -0.56642861558854, -0.0140927684336, -0.24084016769953,
  -0.22126404583799, -0.48555969464858, +0.11236719938865,
  -0.49288037335806, -0.40173152452396, -0.93250797496344,
  -0.03229531637376, +0.21825382233448, +0.03739946238256,
  +0.1374879444022, +0.22430396458675, +0.46943036662254,
  -0.00170643021403, +0.06426158163167, +0.32519908773197,
  +0.32918607829416, +0.27128806039715, +0.82572462486339,
  +0.16609563652185, +0.38564117524834, +0.20756513974825,
  +0.02414029170375, +0.08513435007418, -0.03574052073515,
  -0.02278333566773, -0.07433240554836, -0.24203279644458,
  -0.4394490905554, -0.26684341584396, -0.31489850590264,
  +0.32882496746405, -0.71284220464409, -0.75785459564167,
  -0.40302302458281, +0.03400102003326, -0.38931809315641,
  +0.26412596898052, +0.36753502092261, -0.22452481764354,
  -0.38919330769825, +0.04915262733739, +0.30387696857521,
  -0.05161303783791, +0.34640818733018, +0.13929037426145,
  +0.18654194480554, -0.30557093546576, -0.02448137177135,
  -0.21996314723917, +0.50370841582545, +0.484193097316,
  +0.46441069774369, +0.45647980585031, +0.30169496837048,
  +0.27814426416762, -0.32971000433315, +0.0901473627562,
  -0.24099805353957, -0.17982235168321, +0.10781712829013,
  -0.17583862467418, +0.39292147651521, +0.25976653502951,
  +0.26449196179133, -0.37618073271006, -0.13925794934975,
  +0.01518800891801, +0.56678143701349, -0.00347873082085,
  +0.33643814749093, +0.42718868962352, +0.0 };

---

Shucks.. I was hoping there would only be 3! lol.

The minimum there will be is 4, but there may be many many more.

Do we lose points for destroying precision? Ie slightly moving the dots :)

Why 2 one-dimensional array? Why not 1 two-dimensional array?

And how will our program get the coordinates for the dots? Are you going to just change the array in each of our solutions?

Can you more clearly define "brute force?"

In my mind, brute force would be stepping through all possible paths until you find one that has no crossings. Is that similar to your definition?

You may not modify the data. The data given is an example. Two one dimension arrays properly encode a series of 2d points. How exactly do you expect to represent a series of points in a single 2 dimensional array of double's?

If it takes more than half a second per data point I willterminate it.

Quote:

---

Originally Posted by abachler

You may not modify the data. The data given is an example. Two one dimension arrays properly encode a series of 2d points. How exactly do you expect to represent a series of points in a single 2 dimensional array of double's?

---

Like this maybe?

double[NUM_POINTS][2];

Where double[i][0] is the x coordinate of point i, and double[i][1] is the y coordinate?

Not how I would do it, but certainly possible.

Well, I suppose to be fair I could pass a pointer to the data in that format as well. I have a particular reference method that would benefit from that order anyway. A friend of mine and I came up with it. I don't know how fast it will be compared to the other entries, but it will be faster than brute force.

Quote:

---

Originally Posted by abachler

Well, I suppose to be fair I could pass a pointer to the data in that format as well. I have a particular reference method that would benefit from that order anyway. A friend of mine and I came up with it. I don't know how fast it will be compared to the other entries, but it will be faster than brute force.

---

Why not just specify that the input points are read from stdin and let the programmer deal with the representation? In other words, why are you requiring that input come from an array, and output go to an array? So you can drop it into some project you're doing?

Because if you're going to take this code and use it for something I would like to know.

Do we worry that you gave us an odd number of points?

Code:

---

There are 355.5 pairs of points.

---

Here's what it looks like, sans the last point. Rotsa Ruck forming a polygon. ;)

Todd

BTW, here's the code in Ruby to plot these points in SketchUp. Took about 6 minutes to write - dumb syntax error. Should have taken 2 minutes.

Code:

---

# "dots" is an array of all the points...

puts "There are #{dots.length/2.0} pairs of points."

ame = Sketchup.active_model.entities ;
Sketchup.active_model.start_operation "add dots" ;

0.upto(dots.length/2) {|index|
        ame.add_cpoint( [ dots[index*2].to_f, dots[(index*2)+1].to_f, 0.0]) ;
}
Sketchup.active_model.commit_operation ;

---

Quote:

---

Originally Posted by brewbuck

Why not just specify that the input points are read from stdin and let the programmer deal with the representation?

---

I agree.

As for the machine, how many CPUs does it have? :)

Is the domain and range restricted from -1.0 to 1.0?

Meh. I got a little different shape of points. Weird. :D

Btw it took only 2 minutes to create a WinAPI prog to plot them. :rolleyes:

Quote:

---

Originally Posted by zacs7

Is the domain and range restricted from -1.0 to 1.0?

---

A few of them seem to be out of that range...

Quote:

---

Originally Posted by brewbuck

Why not just specify that the input points are read from stdin and let the programmer deal with the representation? In other words, why are you requiring that input come from an array, and output go to an array? So you can drop it into some project you're doing?

Because if you're going to take this code and use it for something I would like to know.

---

No this will not be used in a project or for any purpose other than this contest, I just wanted it that way to facilitate timing the execution. I also need to check the results to make sure none of your lines cross one another, much easier if the data in in an array which I can then pass to a verification function.

Quote:

---

Originally Posted by zacs7

I agree.

As for the machine, how many CPUs does it have? :)

Is the domain and range restricted from -1.0 to 1.0?

---

Don't assume that, even if the provided sample did fit into that domain. I just copied and pasted a big array of doubles. I added a 0.0 to the end.

The machine I will probably run it on has a single P4 with hyperthreading.

This polygon looks ugly but I think I solved it. ;)

I will post code later, it's kinda ugly. If you'd zoom this thing in enough, it would look like a nice polygon.

Quote:

---

Originally Posted by maxorator

This polygon looks ugly but I think I solved it. ;)

I will post code later, it's kinda ugly. If you'd zoom this thing in enough, it would look like a nice polygon.

---

"I see what you did there..."

After seeing that it hardly looks like a challenge anymore. Unless abachler changes the rules to disallow this sort of solution.

That solution is perfectly valid. I took a different route, but that one works just as well.

Since there is a valid solution now, Ill go ahead and explain the method I used.

1. Find the geometric center of all the points. This is the origin.
2. Start at theta 0.0 and go clockwise (or CCW). The first point you find is the start of the polygon, now contuinue to increment theta and add each point to the polygon until you get back to the first point.

Well the code has very confusing variable names, that's usually something I never think about when coding. My code is not usually readable to other people. :D

That happens when I try to code quickly. :rolleyes:

Attention! Only look at the code if you want to get a headache!

Quote:

---

Originally Posted by abachler

That solution is perfectly valid. I took a different route, but that one works just as well.

Since there is a valid solution now, Ill go ahead and explain the method I used.

1. Find the geometric center of all the points. This is the origin.
2. Start at theta 0.0 and go clockwise (or CCW). The first point you find is the start of the polygon, now contuinue to increment theta and add each point to the polygon until you get back to the first point.

---

Could you post a screenshot what your solution looks like? :)

Sure, soon as I write it :D, we just worked out the algorithm so far, I'll implement it tonight though. I'd post a pic of the whiteboard solution, but theres other stuff on it atm too. Let me ge that stuff written down adn cleared off then Ill post it.

My dots are the same as yours, our coordinates systems were just different. I flipped mine around and drew a couple lines (manually) to show the image.

Good idea to just progress through the values from one end of the range to the other.

How about a twist on this competition?

You have to draw a circle using the points. Who ever draws the shape closest to a circle wins (efficiency taken into consideration also).

Quote:

---

Originally Posted by zacs7

How about a twist on this competition?

You have to draw a circle using the points. Who ever draws the shape closest to a circle wins (efficiency taken into consideration also).

---

It would work something like:
1) Find the area with the highest density of dots.
2) Make a dummy circle there.
3) Find points that are close enough to the circle.
4) Put those dots in the right order.
5) Connect them.

I may be too lazy to try this though. :D

Sorry, had to work on something else this weekend. I will post the code a soon as I get it finished.

My solution might be what abachler was suggesting, not sure.

This looks pretty trivial.

Code:

---

#include <cstddef>
#include <cmath>
#include <algorithm>

const std::size_t NUM_POINTS = (sizeof(xy) / sizeof(xy[0]) - 1) / 2;
struct point_with_theta
{
  double x, y, theta;

  void set(double ax, double ay) {
    x = ax;
    y = ay;
    theta = (x == 0 && y == 0) ? M_PI : std::atan2(y, x);
  }
  bool operator <(const point_with_theta &o) const {
    return theta < o.theta;
  }
};
point_with_theta points[NUM_POINTS];

int main()
{
  for(std::size_t i = 0; i < NUM_POINTS; ++i) {
    points[i].set(xy[i*2], xy[i*2+1]);
  }
  std::sort(points, points+NUM_POINTS);
  // Points are now in the correct order. Feel free to split them into two arrays or plot them.
}

---

You may have to define M_PI yourself - I always forget if it's predefined.

May not be the fastest solution, but it's probably one of the shortest. Complexity is O(N*log(N)). Cache coherency during sorting depends on the std::sort implementation, but should generally be quite nice, since quicksort is pretty good at that stuff. Cache coherency during the copying should be excellent, unless atan2 needs all the cache for itself.
It may be possible to speed up the copying with some SIMD, but copying the values out is tricky with the interleaved format, so it may not be worth it. (Also, the three doubles are inappropriately aligned for SIMD.) In addition, the x87 FPU directly supports atan, while the SSE engine doesn't. An interesting variation would be to split the three components into separate arrays, but this requires you to write your own sort algorithm or a writable zip_iterator (Boost's zip_iterator isn't writable). If you have the parallel arrays, you can SIMD-walk over them to calculate theta, assuming you can write a proper atan2 with SIMD instructions. The case distinction necessary may make this difficult.
If you use the FPATAN x87 instruction, you can omit the zero-check, as the result of that operation is defined for all-zero arguments.

Quote:

---

Originally Posted by Cactus_Hugger

My solution might be what abachler was suggesting, not sure.

---

That looks a lot like the results we got on the whiteboard.