Connect the dots

[abachler]

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.

[Dino]

You gonna provide any examples of the arrays?

[abachler]

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

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

[Dino]

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

[abachler]

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

[zacs7]

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?

[brewbuck]

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?

[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?

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

[brewbuck]

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.

[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.

[brewbuck]

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.

[Dino]

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

There are 355.5 pairs of points.

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

Todd

[Dino]

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.

# "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 ;

[zacs7]

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?

[maxorator]

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

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

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...