Thread: Connect the dots

  1. #1
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195

    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.

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    You gonna provide any examples of the arrays?
    Mainframe assembler programmer by trade. C coder when I can.

  3. #3
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    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 };

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Shucks.. I was hoping there would only be 3! lol.
    Mainframe assembler programmer by trade. C coder when I can.

  5. #5
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    The minimum there will be is 4, but there may be many many more.

  6. #6
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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?
    Last edited by zacs7; 04-03-2008 at 03:22 PM.

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    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?

  8. #8
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    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.
    Last edited by abachler; 04-03-2008 at 03:37 PM.

  9. #9
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by abachler View Post
    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.

  10. #10
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    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.
    Last edited by abachler; 04-03-2008 at 04:20 PM.

  11. #11
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by abachler View Post
    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.

  12. #12
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    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
    Mainframe assembler programmer by trade. C coder when I can.

  13. #13
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    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 ;
    Mainframe assembler programmer by trade. C coder when I can.

  14. #14
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Quote Originally Posted by brewbuck View Post
    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?
    Last edited by zacs7; 04-03-2008 at 05:10 PM.

  15. #15
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    Meh. I got a little different shape of points. Weird.

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

    Quote Originally Posted by zacs7 View Post
    Is the domain and range restricted from -1.0 to 1.0?
    A few of them seem to be out of that range...
    Last edited by maxorator; 04-04-2008 at 06:22 AM.
    "The Internet treats censorship as damage and routes around it." - John Gilmore

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Non-blocking connect()?
    By pobri19 in forum Networking/Device Communication
    Replies: 9
    Last Post: 04-22-2009, 03:40 PM
  2. connect timeout
    By X PaYnE X in forum Networking/Device Communication
    Replies: 8
    Last Post: 05-14-2005, 09:30 PM
  3. Client timed-out once on connect(), can never connect() again
    By registering in forum Networking/Device Communication
    Replies: 6
    Last Post: 10-28-2003, 03:46 PM
  4. MySQL Connect from Outside Computer
    By juschillin in forum Windows Programming
    Replies: 0
    Last Post: 09-27-2002, 08:02 AM
  5. Advanced connect four game
    By Ion Blade in forum C++ Programming
    Replies: 10
    Last Post: 07-28-2002, 07:52 AM