Skip to content

Instantly share code, notes, and snippets.

@veltman

veltman/CA.json

Last active September 21, 2016 13:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save veltman/c582a31d347e04dd75d5331b0074558e to your computer and use it in GitHub Desktop.
Save veltman/c582a31d347e04dd75d5331b0074558e to your computer and use it in GitHub Desktop.
Download ZIP
Jigsaw morphing
Raw
README.md

Tweening between a single polygon (California) and multiple polygons (Hawaii). The basic steps:

  1. Draw a relaxed Voronoi diagram over the single polygon with a bunch of random points.
  2. Traverse the graph and assign cells to islands one at a time, keeping the groups contiguous and roughly proportional in area.
  3. Convert the cells to a topology using Mike Bostock's method and merge each group.
  4. Align the resulting puzzle piece polygon with the destination island for smoother animation using this method.

This isn't totally robust - bad Voronoi luck can result in a weird clipping result that leaves out a chunk. But it works... almost all the time? The breadth-first search of all the cells is also way slower than it needs to be. A hex grid would probably be a lot simpler.

See also: Smoother polygon transitions, Voronoi Topology

Raw
CA.json
{"type":"Polygon","coordinates":[[[290.4171278425778,20],[298.09656708502393,20.387349448552357],[310.9681435415374,20.667311665003865],[320.6062574983216,20.970676399367804],[327.6473722356476,20.697350850873207],[331.1875907590928,21.039589674259986],[342.4343217268238,21.185073521567602],[354.40573976043765,21.061401719799036],[369.68226264080016,21.376095058265577],[390.4280230547386,21.587251021371117],[396.57912885507614,21.452554765493716],[401.7906845014998,21.538097297657245],[425.93974495943326,20.94841911146615],[437.33598182957485,20.427933206805477],[438.24022362247086,43.696921177561265],[439.15514319935556,67.32477892245485],[440.10034770357447,87.71055732969664],[440.47760324061545,96.98998633038453],[441.14458607767864,115.84089558559864],[441.75136301480404,133.84334112231747],[442.18001864153973,149.9523329284102],[442.91074800015986,163.16662728783433],[457.62434830961126,175.09681015991754],[478.6966653118181,191.94859548728144],[494.2008845615861,204.25468442799712],[508.21509658684977,215.38253500707197],[528.8789822603146,231.4818278622084],[535.777019410297,236.95642697321446],[550.1756674642216,248.07527134040095],[566.203607110866,260.3325111489551],[577.0863431162187,268.6692507086922],[599.1484433989572,285.35673068863275],[614.0241705591734,296.528924611644],[626.3591589376306,305.7053922932383],[644.0788178621895,318.7904742870989],[656.3767179480084,327.8235549921059],[673.3332793070317,340.2050691424698],[674.6020761728555,347.11657718440546],[676.2564746091368,348.01897006053264],[678.4664206389796,351.5040467511732],[682.2376090750963,353.6987596304911],[683.9885403435569,356.9748385685805],[684.6618705766273,359.46642080435856],[687.4454100988793,362.3416980932209],[687.7721816164715,366.0031867064663],[689.7828698960515,366.020649465279],[693.3876984292602,368.089432657162],[695.2005290434013,369.5831479611014],[697.3869983618616,370.09086160767725],[699.3762298620993,372.156567458318],[699.8677174299513,374.42881737304316],[698.7059605450912,374.9404738498413],[695.5901249759504,379.48427577492293],[694.2504119515842,379.8606635064251],[692.9380424459271,381.83369497778745],[689.3390856164153,383.91598753107303],[688.7330097384548,385.063829938802],[689.0767764878453,388.3775193430378],[685.8084998778354,393.95709554773555],[687.5555209402524,396.7818261055267],[686.6088682678447,397.85095124751314],[688.1953338963986,401.783573045],[688.2399150030858,403.53636993399255],[689.208779689207,405.33384259249135],[688.1306853995499,406.07741876408716],[688.0343431603684,408.04836201709907],[688.8027441244699,409.87179048987014],[688.1715673863218,411.00866060221097],[689.1739332833316,412.8588579769512],[687.8964008292496,414.12887572737213],[685.7282217269969,418.444157308428],[685.6644794052083,419.9431652173379],[681.9573144094405,421.56959331707935],[683.3274622950437,425.07778992837996],[682.2987271525162,427.04832298565657],[684.874651726999,428.35027388181845],[685.6197118083301,433.89754032550627],[684.9001927487639,437.42661820033845],[686.9663031861605,440.2411777309586],[689.295768252023,440.45132873040325],[690.9779515270008,439.7607185156818],[694.2244219534252,440.2020856322771],[695.9776865868641,444.2054587242253],[696.9853201638921,445.54220038001426],[697.2336048192587,448.81906151728447],[694.9525681976166,452.02918469723],[695.4365207132778,453.75615677054304],[691.7948466350576,455.83535733995507],[688.5171244392131,455.82722802589456],[687.365241802998,457.0295371324264],[664.5055285268397,462.31176474280846],[640.7116542529584,467.681894047092],[610.5009136191386,474.2702634187242],[583.2551520903778,480],[582.3135964342976,475.7930643929194],[581.5893631934487,474.2561035491367],[580.7398024276996,473.11970667889796],[579.7042178334359,472.52935220207996],[578.1313634814328,472.57972731956727],[577.9694222863104,471.93790882750875],[578.7789636069853,471.00423768612154],[580.5116937707099,471.5990264186463],[580.7611259427356,472.36511770083905],[582.4846741244274,474.97269290290205],[582.9293940547534,476.20477979077793],[583.8136652004775,475.3920285495544],[582.8700031948445,473.7926547468238],[582.8129580320536,472.85116723148803],[582.0880594944686,471.91144407566003],[580.019201466906,470.79415831564245],[580.0764672341318,470.17229845687143],[578.539701995035,470.40261713067207],[577.4063968415257,471.4664365916735],[576.5729078589316,471.8384306303284],[576.4120607065836,468.60179541053617],[576.1441175443241,467.5380311850438],[574.7302669340323,464.8691361078752],[575.6835043547529,463.9126498742917],[575.7964314265002,462.2720094848013],[574.3190108138081,456.72813643485165],[573.6730410120718,455.19766475631707],[573.0879363165801,454.6241798942582],[571.6728908429076,450.9587146956919],[569.6581866970248,448.1470124989721],[562.4630000600658,439.98390941163257],[558.420515660448,437.474894369195],[555.6729466091729,435.0388390104297],[551.989686137062,433.1377810720744],[550.0080882097477,430.99051709514936],[547.7947916772486,429.5021835885809],[545.2618313369317,428.0969060883332],[543.047902394108,427.50291081073453],[540.851809425317,426.2290427074237],[535.6421600327183,421.7241219655524],[532.8683019691262,420.50526360887704],[531.4615755991601,420.68198467628395],[531.2521543533207,422.035527572497],[530.4860508036992,421.5480530145926],[529.8662030624678,420.1127369381495],[528.4725376574379,420.50633229827076],[527.5600426878443,421.9590188754519],[527.9153625209717,423.1490364586399],[526.7065517387698,423.52354931688046],[524.3283106430011,422.85258846622673],[523.9713267485771,422.3907814703066],[521.8144864457355,422.24123948841145],[521.0264947563304,420.63783392626203],[522.268831793988,418.8913212281725],[522.3377268770203,417.31723813076724],[519.6299254024359,411.64540753232075],[517.8231109197892,409.21321276349],[515.059993155867,407.35197377665077],[513.9206454241939,407.3182700959791],[512.2948193233416,407.71434439828863],[509.45809612048356,407.78334164599687],[509.29501612705633,408.1968317229123],[506.3817662739327,408.3138698903749],[504.9246071793161,408.9300766382821],[503.9960981327843,410.1501922124553],[501.9356464616626,408.51604627721804],[498.3164868117845,408.25518118358127],[496.5300737621121,407.52256009460746],[495.20697625517187,407.2664106374058],[493.8667161590739,406.4446786355634],[492.8967719346073,406.40619860453603],[491.6249064382228,405.71151092721027],[490.44270970076207,405.47616107301724],[489.9669169044816,405.80707795244496],[487.075973986825,403.8524378073362],[486.0705220823553,403.71634151614626],[484.03009908247213,400.142717430632],[483.53441495537305,398.2229718071146],[482.60406660748663,397.26559830774625],[481.9957176962107,397.41335730895685],[480.49597537458317,396.56398476918713],[479.0479057694531,395.14140010883875],[478.1780108616044,395.2515139603773],[476.4539763675444,393.54281669362433],[475.437296139152,392.8291336316278],[474.37874018488503,392.669659837355],[473.6268609749174,392.1219613200468],[471.82186654943825,391.6192139353559],[470.6592593859652,390.6910787931547],[470.12917950749136,390.8649585247385],[468.3637514788194,390.5105056234197],[465.4066977392656,391.14739767945446],[464.59116152223197,391.9799967356661],[463.52638626164327,391.9260169114432],[461.16745053576915,391.02076176837016],[459.2936599021912,391.15376146243625],[457.34555679150935,391.73516200622544],[455.47343174775756,390.4409101235817],[453.9662103791342,390.3769297259119],[451.6785917012765,389.18286748038],[450.54960681477144,389.11972102037817],[448.243336605804,389.433592077878],[446.44247622052274,388.78964211095183],[444.82395621579013,388.99157389360073],[439.7029382319067,389.2544883797216],[434.156729615888,390.32193662581045],[432.9491344166253,390.7971564268254],[432.152104478138,390.4395868155776],[430.4641872231348,386.84643774962944],[428.4156512770761,385.89433827585117],[427.54979170886344,385.2854092713908],[425.70970120568325,385.3859445368935],[425.0621926872453,384.87765604001993],[424.55749092304205,383.72504253198764],[426.1802139240962,378.88586597390133],[426.2690772557726,377.582920177126],[424.63053431379694,374.88233827853765],[425.4251109605642,371.7614241998235],[425.5213541647819,369.7786791315386],[424.4589388359532,368.7262283325716],[424.25403931951854,367.9212205730913],[423.0569565289903,367.3213568121986],[424.19769605846744,362.5327918900863],[424.5107620211339,360.7812008018244],[424.5792164674825,358.80568943637275],[423.89770286414296,355.49270914475426],[422.46069913375175,354.8370242428598],[421.2966898102238,353.7927826801117],[419.49524817700376,353.6782659309248],[418.85876129591236,354.5662108239949],[417.78424960812754,353.63868225070723],[415.3089022724647,352.484663998262],[414.1691086368521,351.4508449904048],[413.26988877886254,350.1524767818971],[413.3282027053,348.9457999526546],[414.41101386788444,346.03558059499323],[415.9103572893623,345.7115299997418],[415.0190244140562,344.1627858821789],[414.4081229001403,343.9772253631568],[414.1884882573528,342.2433308427079],[413.48719628513527,340.86025333082785],[412.60930867304944,340.1044284730027],[411.04435519891194,340.237874494803],[410.3210230760771,339.7284252366554],[408.58980972506157,339.5615073107316],[404.5316384696773,335.13614865809586],[403.2907642722133,332.57862668108635],[402.7773587650999,332.36825591983165],[401.6770082555258,330.7766920395759],[400.6289496895631,331.02566820755374],[399.7354592399831,330.2617083468448],[397.56280451100537,329.4638657115358],[395.66401872510255,326.9919422607074],[395.2813542470089,324.433121382947],[394.68694266799747,323.3331623154643],[392.62520456069274,321.6006539254837],[391.03377874907187,319.75635056776446],[389.48085141277915,318.3481571492469],[388.338722813528,313.5539303657339],[387.6486616973815,312.50424382551375],[385.1984879686808,311.67986481806884],[384.1319776269,310.15849846583154],[384.05072519001016,309.4726707325625],[383.0804681709999,308.46594835658425],[382.58529738408487,307.03210800272996],[380.6316689055871,304.5553313745231],[378.5470838077797,302.7885157958049],[375.71790791118207,300.98009489900085],[375.25292981395734,301.0863317405406],[374.2296671846984,300.2491073601543],[373.8292101215164,299.08632891952277],[372.68821069071,298.20649834674157],[371.79638724671986,297.011245598375],[371.44490539293827,293.47724114520963],[370.99197314940454,291.5441669653302],[369.7414487728761,288.11141562900866],[369.9025669454844,287.11142203917586],[370.49343311045595,286.513595685842],[370.2066086682782,284.6474925063289],[369.43366374770966,284.73124686563546],[368.4663125191629,283.9729201150783],[369.57381751834157,282.21667835240044],[370.0782505159612,280.7537277269315],[371.50263949205663,281.6742187075676],[372.0947475870317,282.60896467939824],[372.7918754732329,282.3468696984347],[374.072112340733,280.9261052713114],[375.0107110298354,278.54765893930335],[375.439306253857,275.195951368463],[375.9620787689483,272.4180565719459],[375.3808905748667,270.9362609373168],[373.15007450485894,266.395101912217],[371.3314926489789,264.32959759429514],[370.07490584615994,263.8754966282429],[368.60745952678985,265.0248943647266],[366.74231502402745,264.65387547304056],[366.58404894954504,265.234869580362],[365.1670314801904,265.3410208173792],[363.37519695597587,264.9930213065463],[361.48684369537773,263.9287944240757],[359.34177069061855,261.8251961029865],[357.53280778518,259.83857097749495],[356.4650366193838,257.97414676916435],[355.39011795429224,256.97117505095645],[354.16740025184936,256.8686193154491],[354.2297350492825,256.05972810585274],[353.37861469284917,255.28114732608782],[352.99907990971184,254.11180515687636],[351.94564435495164,253.7151398421971],[351.6212006120731,253.08488881602318],[351.09649786859035,250.2184344360051],[351.42693673035495,249.40253816116643],[351.8497603315699,244.9087301130699],[351.41457294741724,244.1540884119766],[350.15060798702393,241.04993293320516],[349.9831923826847,239.11540902552133],[349.4404289837749,238.12320732252056],[347.96121372680574,237.87783214008195],[347.21714599269967,236.38488590614466],[347.45574230509624,234.93321453990114],[347.30320179384086,233.51013125913641],[347.9266936655009,232.93717883759405],[348.22403006432035,231.6627395403948],[348.28968777495203,229.79787421640805],[347.59804002279895,225.50498652570352],[347.5519865872391,224.08404440957165],[349.57772615989546,222.91454755781274],[351.31334792881523,222.6426810769824],[352.50343490794575,223.64509584624648],[352.69030877739283,224.98152157172635],[353.77989486078917,226.65430557903943],[353.46627956860175,227.39511963088052],[352.2962003043542,227.61205163513856],[352.45802260602863,229.24564618103793],[352.959104578356,230.3346390365091],[352.6060987405237,231.50010043338727],[353.3855345907302,231.71343007213085],[352.97151339500715,232.84736057835445],[353.5763720217335,233.41304438137814],[354.67422832430674,233.5883107014505],[355.8944699134487,234.21286177124597],[357.50133006013823,234.48714891034723],[358.21274196323895,235.7058339300399],[359.7859387386751,236.30119810145402],[360.41591647522745,237.65629819074707],[362.3304087839611,238.14445556084652],[363.6568826606969,240.2573101894655],[364.4125994985052,240.57222452654494],[366.069013453985,240.44156454668422],[365.5371316775732,239.45435359499166],[365.141915785015,237.95718033587764],[363.92941205223036,237.86288353377498],[363.3158990574341,237.15064790133],[363.0247034957541,235.93647738102996],[361.8657422343699,234.13749147541222],[361.2358180553917,229.9226021280686],[360.1083147247428,228.15123251271746],[359.23145159428896,228.20894686240052],[357.77979292467916,227.0346704427407],[357.37285839572684,226.03686625835678],[357.8963882685871,225.77881671419416],[359.31515053516915,226.0224981520846],[359.12995503417955,225.28328979998577],[358.2715560263,225.4349392630994],[356.55488485419124,225.03201410902432],[354.6939424791366,224.08269733083188],[354.8211305713913,222.99771696130716],[356.10828111371325,221.68620702215793],[355.793068016536,220.13028332565506],[354.84161760200084,217.90530375340268],[353.44199940901257,218.1116452252424],[351.69575260142847,216.7097351798315],[350.9531496432995,215.11546151278748],[352.1874221937837,215.52559017818078],[352.29719224731355,214.8317778760304],[353.6758086749117,213.98901797667574],[353.4239894919636,212.77570425794733],[354.5923736218746,213.20223052731876],[356.02390923518976,212.84886830691278],[356.8807615497177,212.1790728712524],[356.93878228302617,211.48525093406548],[357.94042549197303,210.69283551153222],[358.8178598770798,210.5473713769108],[360.39401663800163,211.0659414044375],[361.07112994488,212.046099475085],[361.867070255731,212.2652618691149],[364.4236278966678,211.08072515810318],[367.43031708668127,210.67920383242986],[369.94023978201346,211.24627495906105],[371.9107118677006,211.4123096121965],[373.8791173087936,212.29108158768224],[376.121861721398,212.65545965671737],[377.20518828295394,212.45535118534693],[378.29395117644543,212.8568719762275],[379.56747909347627,212.9483156275211],[379.8973746718414,212.53730306057537],[378.98533474619666,211.67071409663595],[379.73071223710946,211.19953502200585],[380.274417966595,209.27655814620405],[382.071089521736,208.9992981885053],[382.7554344982968,208.50062722394753],[383.7082322787476,208.8532053474467],[383.6078253589536,210.28853080768425],[382.23159481679625,210.34447794664953],[381.78947336443656,211.21074755709162],[382.84934865228445,212.49395852961032],[383.6496595845591,211.95739289889627],[383.87357337617476,210.30418496202506],[384.21113524271516,210.13132028769496],[387.66759658096777,212.21695715337952],[387.41593508327236,211.13573241464798],[385.00952284444855,210.20459002151793],[384.12180472574835,208.59778644691963],[381.9621377650498,208.19958104900007],[381.298234452641,208.84665097296536],[379.9185920700462,208.84739733088526],[379.5809725490031,210.37431531947203],[379.1961172298888,210.90348091813516],[377.5512408934605,211.96236073963107],[376.56910420135307,211.9210997062476],[375.8806035026873,211.2859776174643],[376.08424534063244,210.40351471676524],[377.75573312605934,209.5388828941331],[377.34681962889965,209.10612691384225],[375.18704496703276,210.33329844177035],[373.5239770534049,209.86705901419893],[372.12045582221003,210.6363605001792],[370.8003001912386,210.84464840341874],[371.1227364106332,209.56250610309394],[368.6932763774189,209.75791647918368],[367.00750941571727,208.60156195196546],[368.12453968704335,208.003924190096],[367.57297134060804,206.70018296946225],[365.45841097479126,206.87430960405794],[364.9261508338883,207.45938131059722],[364.6726664870859,208.5015568092905],[362.9092568362531,210.4898184170991],[362.5514844886846,211.3589192194965],[361.46284476410347,211.2918576022593],[360.46923558635496,210.24170827702034],[358.9534204926405,210.18953790496573],[357.1070580939536,209.74974184036463],[355.98930894912877,208.09201471085572],[352.310954107824,205.85965816359655],[351.7596488352412,206.8048869522975],[348.7864691910456,208.20022130245258],[348.9634746509615,209.57190070899964],[348.02447363359653,212.4911512969161],[350.018245040381,213.46069079065842],[348.5235467990117,214.82139449575675],[348.982319246963,216.19939488422648],[348.0795669409127,217.02582125947453],[349.12949359614083,217.46943113605084],[349.1997040530881,217.99833979153897],[350.5653106960745,219.14863427847752],[349.3668926048058,219.87883472125748],[349.12274226762923,218.9039812786676],[348.2350884684468,218.561220869098],[348.21495412945865,219.59816707566222],[349.03239772613455,220.23556005398314],[349.31676515794743,221.60744931220864],[349.0350163088776,221.9355735794017],[347.05502583641083,222.34504067032196],[345.3186648983733,220.38178827153382],[344.2576021041146,219.51795804950035],[343.50665392545204,219.29893899981516],[342.5711793767281,218.23939610390406],[341.5221892320571,217.8443615973026],[340.57617079151066,218.19083852513958],[339.374575148409,217.9878203176196],[338.5862023846347,216.52393551877148],[337.37414646538053,215.74264414619955],[336.78567220735454,214.38857369423786],[335.81962714676274,213.28565062512746],[332.5477207094749,211.55201427917075],[331.9992572223101,211.3934408679715],[330.35763505169035,211.83126728812923],[329.00655516239766,213.3491936779293],[328.29997581332657,212.9985559026605],[329.3237786737474,210.66300348026584],[330.99882756585,206.02482518677414],[330.993410415368,205.0203091750837],[330.4461481798172,204.1228413610263],[330.4673343043825,203.33994083050013],[329.40340214866296,201.8053265579003],[329.71797372291667,201.40565487300282],[331.9545995933931,204.51685523294648],[333.22678222552724,206.71205229264183],[334.0857280180099,207.73426273674048],[334.7928713815566,207.72479070803547],[333.3667072743775,205.54826133528792],[331.60802413046434,202.53508562343433],[330.3489913966336,201.4531519822498],[330.1569744281669,200.0253952438857],[329.119721546402,198.60262920483956],[328.0924358561535,197.70963860827837],[327.44213050518647,197.72757169644473],[326.81248952038516,198.50389200766432],[326.3214387702177,197.1940148518769],[326.6369411322019,196.03640443812117],[325.9703852401417,193.82429082520346],[325.01751398111634,192.36930212604472],[324.4383836906446,190.95528026546606],[322.85997884287247,189.4604616275654],[319.77733449269596,187.849694112196],[319.0407979395161,186.93904538145767],[316.63392040314125,185.0079209314883],[316.4806216103487,184.05938184939816],[314.2943997222336,181.2605253591746],[313.83723776636407,180.08564455437568],[313.11954407863277,179.08600765607446],[310.9565562580002,176.60462057229452],[309.8021826732964,176.07078462887378],[309.29626879321216,174.80949298711954],[308.24762747844903,173.6668419910141],[307.20613048598466,173.11513498549218],[305.22653368646263,170.92572699043384],[304.7055965502046,169.7947825560659],[302.9378473543999,167.70105022920862],[301.8397340206958,165.6574883458401],[302.50247794630076,165.44988036309348],[303.3550055151447,164.03813776185515],[303.97633894931386,162.22309366337205],[303.7988095761466,160.7025881341357],[302.9249467776143,157.09118378569852],[302.33554237926717,156.58708927284943],[302.4466148803182,155.8144589610241],[301.29453234578784,154.0806327507072],[300.57455377646534,150.38954993374236],[300.1147394017315,149.92766569926997],[300.36355802956496,149.03111342269244],[300.09092502023805,147.7416309050252],[299.4245784924807,146.5982027225833],[299.90725017817704,141.94416948106988],[300.652888361175,139.72595974551615],[301.8183812657013,137.155712035615],[301.86272216423924,136.23712213509492],[301.27387072067665,134.62318248044016],[301.38654278888856,131.81208027277813],[301.0980251467443,130.03630827339825],[300.66598338388616,129.0614045885426],[300.11266394524125,128.75438296617526],[299.6815117120623,126.62914516337797],[299.72925083461405,125.6042575768252],[299.2005171827591,123.15331851502816],[298.2555140867556,122.60126169187659],[297.27966472262113,121.52672415511145],[296.51088246690983,119.47243634645088],[295.6270176337007,118.64648840596955],[294.8389811903903,116.77252682699879],[294.04890269143965,116.01239542852925],[292.93156817780016,114.33411191314735],[291.2554138935924,113.14161837373663],[291.080548290773,111.12236771938717],[290.10158743230915,109.66230245393723],[287.6039058642124,108.48106267578552],[286.41051650872373,106.72335096903723],[285.12081187250493,105.74356276733727],[282.91019415049334,103.71865198264979],[281.3828511771644,101.88322870318072],[282.0650430079623,99.16774928439165],[281.52239558963436,97.90990544433907],[281.54362748332414,96.34454043811131],[280.4713396254757,94.4598476371786],[280.1322825700487,93.107116687415],[280.6611326985342,92.10335908193927],[281.1273470547332,90.0176933085026],[282.576759711584,86.82858156501527],[283.67050642245704,84.9914433061466],[284.11068778806236,83.63667743783311],[285.587886007462,81.13973933460736],[286.941025733218,78.40736774346179],[287.24146994602347,78.83125141409211],[286.6043073978695,79.85831910684428],[286.10243094078413,81.2407063370822],[286.99409214725347,81.59028460567714],[287.75367553647806,81.17108016739547],[287.59009342535364,79.45781368703224],[288.23849206184855,79.10784404989248],[288.8349482684795,76.97394710926426],[289.34348221762576,76.3780505879453],[291.2786991397463,76.27828910457559],[292.55201687361375,75.48593391578866],[292.7027713644396,74.38824030666987],[292.1000869378684,73.88473360221082],[291.4709135866997,74.16738240427216],[290.8280244412657,73.5700324471645],[290.1987093699234,73.64889632177416],[289.57367851645256,75.28482175385084],[288.69069606397136,76.40660215312269],[288.4337344888212,77.22877968837513],[287.5294719517769,78.51004540565363],[287.20573576544814,78.04151797240239],[289.39491819497755,74.27881746906965],[291.10872441243464,70.1395058543394],[292.1001345150651,66.43755799890458],[292.11642927934383,65.18533821688949],[290.88672312045674,64.25602947249234],[290.4745535326861,62.38038071109206],[290.47411276328467,60.49723348016734],[291.1776072287031,60.24690255951944],[291.9347151321648,58.534459280534165],[293.33000741038967,53.496517119801],[293.74158558192175,51.03850127801209],[294.6312328851312,46.62802575554706],[294.09386761404505,42.56501654212221],[294.6101348918375,41.746995164742245],[293.43805430905945,40.410982602070405],[293.51955701677525,38.714165159550475],[292.33525472279484,35.75725990030098],[292.4143714790782,35.03204903268028],[291.79145347285,32.324945992320494],[290.8140149932817,31.797572627134187],[290.33610363115923,32.13887820702378],[289.2875307109238,31.00779041371095],[288.2467499681147,30.299867692439562],[289.33593686427577,28.617155137186884],[289.94046638340353,26.912467416502963],[290.7449054887129,21.758856191097493],[290.4171278425778,20]]]}
Raw
HI.json
{"type":"MultiPolygon","coordinates":[[[[743.5872675202813,307.48241759969096],[746.2895624940131,309.5353697793862],[749.3538912939046,308.71812747376134],[754.1084086839987,308.9335629871571],[758.9184126382213,310.70067034739304],[768.2836930616327,313.72677683554866],[780.0899518446363,319.5897565007285],[802.0901043198803,333.1490943733638],[809.132406316452,340.02119814048865],[813.0315924369006,345.0309868144195],[813.2355947525655,350.5313721333737],[813.1561942009623,357.8610079629034],[813.623487160469,363.6211954122182],[817.3140962014431,363.3931853851468],[822.4273447389664,360.87275995231175],[826.271507111516,363.4738819122663],[828.0848276529155,366.36958199153196],[827.7559892922247,372.38599512903875],[829.5617346669835,376.0664474302148],[831.8919998404308,379.4920034646593],[838.6814500212622,385.57531158374377],[845.7701731535783,388.5233423946006],[848.6454580281047,390.9077760236478],[850.1961491778911,393.803085865678],[849.8551592639888,397.5695242013662],[848.215764834717,399.79575954581924],[842.4131200776642,407.07671916578965],[836.5932511929359,409.3731803521723],[828.3455488683464,417.6666013803847],[822.6982599166813,419.4099493090662],[822.5212572455539,421.01129802566993],[817.7726430169873,422.27274233666185],[813.793490440185,425.37561222121394],[799.2828810316028,429.9405338219649],[793.6678197591202,428.6506547912345],[790.4507421455969,428.620362281461],[787.5679016860088,429.6060110359972],[784.508089166545,431.60386243990615],[780.4135478520991,434.59937556179466],[778.0179386727041,437.6163022069859],[775.300611281431,438.0918307531342],[773.2609070155443,439.08723212595487],[768.4485607728259,442.5096546985915],[761.7506780406247,446.4586163667859],[759.7684023626489,447.17180771686617],[754.1089416977909,452.7998030513518],[753.1382283140233,455.09330108610266],[753.4230392010472,460.1796742409997],[751.0268756839978,462.8619193562199],[746.9222329629035,467.05077934780365],[744.8348840674855,472.9485907653748],[742.9513855591936,475.1304207776002],[737.477475203197,479.99999999999955],[736.2971641337781,479.3137197885876],[736.3270617727671,476.26820824140304],[733.4661725094245,474.0465933500868],[728.0689957828079,471.29825766953127],[721.6577800670457,467.53259925570774],[718.2870731277751,465.31044000049224],[710.1613358189707,463.2229684995573],[708.3623043545131,458.12687069326057],[706.6454933559796,457.6214289291361],[705.4925625574178,453.89540118642844],[704.3619447075655,447.9724998565921],[705.7824514060828,440.8925994908809],[708.4904092247605,420.519594200307],[708.1885230172402,416.96650451485175],[706.3430215963074,413.7505365073357],[704.6708982789849,409.3582297790076],[701.3882724673499,400.0320926054155],[700.051844473111,398.3315233417861],[698.6878338263548,395.46625018729947],[698.9602955595983,392.4048387646294],[697.3678098253613,389.5535358849829],[696.5572538658726,386.33802170383615],[695.0596251121024,382.4464323465245],[692.7089680134368,379.05421791664867],[690.6618707904813,377.52232528965897],[687.7626210677718,374.128038286834],[684.4574679699449,365.32481014316863],[685.7218231871327,361.3480072748839],[687.1746260291493,358.01839044593],[689.9654218544181,355.46490418538133],[692.6742439705904,353.5557141348563],[693.8812718273962,352.1480466076223],[694.5617700051218,349.4851648665067],[696.4022826793735,347.9309404441483],[701.9255274981351,345.8059731923245],[704.5236964861899,341.11509249303253],[705.8179890945237,339.49530463000883],[708.7064689184069,334.15683162445566],[711.6307321308686,330.7582642527159],[713.6739198072687,330.6668366384142],[715.0781216578105,324.43732909124174],[714.1097386524832,321.75760668819976],[711.8732247017604,319.67632702566607],[707.1488375931453,312.7036163878315],[705.1421030445447,306.5990076447674],[704.7480496847343,301.6823802490426],[704.6871405874415,297.1241579476946],[707.0919878827792,292.14813926653414],[708.8174526736734,290.56757133122665],[713.5911657522756,290.44855262963847],[722.2264777071068,292.2989113770009],[725.9510519865635,292.9876068650037],[727.1421738850399,294.70775639634894],[727.32090343404,296.06384628528485],[729.5421999833559,299.58711161093606],[734.6439553483397,301.5248232067729],[738.0116678917223,303.37739551553796],[740.370399639648,306.1039583054144],[743.5872675202813,307.48241759969096]]],[[[620.1397311619189,254.3564545041986],[618.7977719240698,256.9679904839122],[615.0520574776315,257.0509580771827],[611.5316625485775,256.4807926447752],[605.3428535785985,257.86396948814763],[601.0216711424965,258.3911297468485],[598.1709388978411,255.53539463911602],[599.7429632607473,253.46540700980813],[602.5236795035455,250.96986180200065],[606.1904288429187,248.48897447853005],[610.1664934713037,246.2156646411604],[613.6082451969401,244.9256950113845],[616.3643550914451,245.16088560070148],[619.7432349962821,248.89434962954783],[618.0560910070028,253.03213051239345],[620.1397311619189,254.3564545041986]]],[[[569.6639150943172,226.6714655873534],[563.2622249019471,227.0742299891931],[560.5645338550455,223.33414848277152],[559.9068004175949,220.06791078755487],[559.6374678264589,214.2011320618717],[559.1353745241868,211.2205204287834],[556.8659516538708,209.9160324620093],[551.3561736719936,207.81378615878612],[549.7000997647606,205.1846016506356],[550.7111449479709,202.24535074994583],[553.8129684241813,200.62649215367992],[559.2292097040836,199.89481392934067],[572.1331431885194,201.6053109432637],[578.0441748259898,206.74033553612117],[582.3305425518233,211.58655090118464],[583.7498297459056,213.88468666591598],[584.0695854062997,215.63106418441248],[583.2824874548476,218.02508150030917],[580.4974992405075,222.47986194707073],[574.5251627848488,225.28075166264534],[569.6639150943172,226.6714655873534]]],[[[611.890733941601,185.25265737964992],[612.9911548632855,186.5753691597729],[614.308711513751,186.79396172577117],[618.1616108358633,188.5645806151383],[618.8240039777513,190.33234862541985],[620.3641505883284,190.77596056871198],[620.786342848707,194.27473563147169],[622.642279081883,195.90972147634693],[623.8467410802396,197.6666905501129],[624.8257239888329,199.8554787981452],[626.3518722429119,202.26221891741625],[628.6703718647435,202.05912584888347],[630.1167937586763,200.32388183031526],[632.6508983971328,200.31749734692448],[638.4538364821783,199.7024339550385],[639.9190420846594,199.34110711168478],[644.1030348340487,196.22758831052033],[646.1683510572618,195.44872881503352],[650.4300833634827,195.18294512805778],[652.5968686976144,195.4920834700365],[655.3729803145568,196.37117528974886],[656.0987663680185,197.2006763669583],[657.7591726847122,196.63136986706377],[659.8925848579593,197.939622015052],[660.5800584541048,199.5498971625534],[663.8748051008705,203.03525917840398],[666.2807232796878,204.60704879056493],[668.0337996187524,206.2554596246373],[668.2271492820757,207.465741117991],[670.4482741638519,207.5834816798838],[670.9001404361652,206.82114403282776],[672.6552609648817,208.14319609323275],[674.2816234895414,211.10221768886777],[678.814466034909,211.67778862545993],[683.3300464525819,213.78359461618538],[689.8680621038834,215.83410669021714],[692.8838825331454,221.79752151654202],[692.2925206043767,227.35972682045985],[689.9286296465266,231.8208869479181],[686.6952220020912,232.78306250537025],[684.0269509726415,236.80009394025183],[680.4660117805277,236.88515050271963],[673.3802304546996,240.65082878067642],[668.6349854587379,240.61579215151096],[665.9925837036387,240.3782760937488],[663.5650982304235,240.578792016237],[657.026686830281,243.69386900036852],[650.6176121785079,247.03252832284943],[644.0040037753276,245.5568329571165],[642.3008135039763,246.09165091484192],[636.7340074398726,246.3888784988594],[633.010588972677,242.98263382410732],[632.5822618688975,241.56145027791354],[630.8289648826958,239.6954756228215],[631.9405601512351,238.7217993602021],[631.9575258075415,236.2131627242402],[630.8094739821713,227.04250633339234],[629.7241158908091,224.52613078427294],[629.7440856752289,221.6900297696061],[628.8773040356657,219.39257430606267],[626.0237184692203,217.29972274038118],[623.9265293260196,217.39407466748344],[622.0583746811508,218.27144147165018],[621.3694990933715,220.21316826527254],[619.7114844665224,220.52909383843325],[615.87497222707,218.11092251600576],[612.9980335382816,217.64498190367385],[610.1386471095434,215.87937031889714],[608.2601069411648,216.08415803699017],[606.5117331930846,213.7838037808324],[603.3291336712095,210.4873544574939],[599.5934465768364,205.760325875523],[599.3920418474916,202.70268167991208],[598.0681565491733,201.04844917210494],[599.3162895423585,194.27560922248585],[600.4651207977918,190.94990345215228],[601.8038708296251,188.77505841183165],[603.464822069751,188.5696468986216],[604.5660594010767,187.35321742701672],[604.6214822252286,186.26283653592373],[605.804135900542,185.4190115744218],[608.4582986916156,185.65934142893138],[610.7838093893333,184.58197857358982],[611.890733941601,185.25265737964992]]],[[[524.7130123402292,159.25673206943884],[526.8130519250132,159.59561866774038],[529.9078194391489,159.39385575965662],[531.5610522683248,159.83693291932923],[532.6609416468607,161.4799684740883],[534.6510889013939,161.45750689446595],[553.8461931602353,164.10212486464934],[558.8994842079131,164.28927849736647],[559.9251807668315,162.71586337874578],[560.7127276309653,160.32248617217329],[562.0057737426357,160.00384013756366],[563.7926818753558,162.29914661780413],[564.4368603634491,164.92035419110107],[567.4147562137057,165.80550245353515],[571.1378559585926,166.60455909849907],[577.7695199521394,166.30900091651392],[580.6653024399842,165.8801767264731],[583.8579993531142,164.70709910184132],[587.3878731244124,164.72843346920445],[590.6267898966687,165.55725102458155],[591.9416780485485,165.29023036249282],[593.2611506731666,166.93200852792052],[595.3643209268041,166.83480415080203],[596.3545045613116,167.49480750705288],[593.8947787317295,172.10229009035902],[589.8919915089455,176.08533838532276],[584.9456950429609,178.88840016739277],[580.0169526152804,181.00969275435955],[574.9468790959415,182.15033597894035],[569.8036364514367,181.7022000974407],[564.6718757439077,180.71670361673887],[554.4263352844982,178.1549138935602],[548.1481233049967,176.0516744814695],[539.2036440529067,176.87677598955906],[533.0210330337117,177.28126442946223],[528.3770724380392,178.0211891945687],[524.6332111432266,177.83754518377964],[521.7234989489539,178.02190616077496],[519.1390450923539,177.02237353182454],[517.621360371995,174.96745110508664],[517.551015948913,172.3640033184547],[518.5571196495862,170.1634618652547],[519.9971918556214,168.45760149045236],[522.3585261039386,167.53061120459824],[524.4695468015411,165.03443827866113],[525.0369599972918,162.31363109952144],[523.3809323819048,160.2302840517168],[524.7130123402292,159.25673206943884]]],[[[439.3476058510271,107.5878433988778],[440.19098540231585,110.01777933819221],[441.6142577093245,110.76838085793679],[442.3639539875006,113.19811082544038],[444.69106077801575,113.39818859688557],[446.95982645174615,116.48351756239481],[446.99414642553546,119.65592562433358],[445.27355427850193,120.4902837932209],[446.2987708355376,126.65741812608167],[449.1507667872309,127.6965609501417],[451.4173982723584,131.06851876889095],[453.41637922998655,131.73196460186136],[453.6940511884438,132.76022146069636],[455.0268116562123,133.2339679305437],[457.13132772462336,130.4391217618795],[455.13711653933865,129.12216311265183],[455.33289536979305,127.5342008311909],[456.7622660035818,126.8857509231043],[459.9976227275444,127.27284255739596],[461.61822705422776,126.81213877278242],[461.9940602057617,127.84185677777077],[460.0772423008637,129.79250650790345],[459.7140498902679,132.31835956169516],[459.97423967565504,134.28489798198189],[462.16096716992797,135.60449256744278],[463.87046946913074,137.2964730269432],[464.34251441867974,138.5020779873862],[463.7638249082023,140.10185430069396],[464.236304057044,141.69529707210359],[465.6614408297942,143.85602126042568],[468.5300264314306,145.7048493457055],[471.2925736475649,147.1258837902551],[472.1470929570242,147.9729706480498],[470.6206681868386,149.7427370097439],[466.14031035357,154.11679371687342],[464.71376749777636,154.5772701203432],[464.3407111132702,152.42371988801187],[463.2020694562881,151.48153880219843],[459.68719082197293,152.4003259422252],[456.83119034350733,152.75521725264707],[454.46232545087224,153.96493016880095],[452.7517208536056,155.36095040470673],[450.6648334316559,155.44486812768992],[449.7177362370475,154.9728072123371],[448.01769849738093,152.25230230563966],[441.4864446256469,149.42148290588466],[439.5060057530822,146.04848653091813],[438.5618789997779,145.2052047577954],[436.85175730875034,146.88078656583184],[438.172864799674,148.38000710055576],[432.67768601442026,148.82711745288634],[433.53349299314056,147.7089344990145],[432.49462227908947,146.86493042638767],[430.4108995435904,146.95107921786803],[429.85527748706716,142.55857601028356],[434.0300690200314,140.4255620690401],[434.5956128493302,139.20763470811607],[430.74897208590045,136.84777370346183],[429.67745982054794,139.19699873956824],[426.83907240953164,138.44043778649348],[427.6849527689425,140.59119395910193],[427.0206036666598,141.05591980636746],[422.9576793901623,137.67639008644437],[423.8996941782568,139.9256379184444],[426.0697825444775,142.17259752916016],[428.90311244033126,144.51707188583896],[428.2336813224728,146.66365347713418],[425.8633948351357,147.6833635246794],[417.905166033862,149.34053164527995],[415.44278763431134,149.61360405041023],[413.2939100693295,150.2505551448644],[410.52265461637376,148.66623607851488],[409.307593912893,143.990294850189],[407.9003689072873,140.24998545605695],[404.88125432927836,136.23144442339026],[402.4224323391571,135.01233055943612],[401.77070437001385,131.27770318586545],[400.92545825579555,129.31538566691688],[397.1475363453794,126.41320306347643],[395.56196456080613,123.98306539039822],[395.28763966185664,117.0822432549844],[394.40710443856676,115.83954391111638],[388.72238858550656,111.1859420648534],[389.5759056629797,110.72142080353706],[394.3145506915053,109.80037288778294],[399.90393806113906,109.44159137505403],[405.7766872078133,109.5497046360033],[407.4275580808476,109.10018633003028],[409.4710453555782,109.55951641039974],[410.52110961276014,107.04368766020934],[412.8943254955243,105.65060040585149],[416.68891158200773,102.58799336963239],[416.4955477260156,101.77486033373089],[418.64643448104545,97.60023590399169],[423.36746719054815,93.35853501647716],[427.53788347351,92.1632242178539],[430.1998947389669,92.81560734778759],[431.8257376521317,94.80634606685726],[433.97892818354626,96.56011431950856],[434.067993139079,98.05366040935996],[435.2085236656652,98.61434278687011],[435.29644745514344,99.82928598997387],[436.43146027093263,101.04529995148414],[435.8409989950065,103.56873656941161],[437.5504024192514,105.90243783915639],[439.3476058510271,107.5878433988778]]],[[[136.34083774324534,82.89448801717754],[134.62642001098044,83.40449195336578],[132.90959787225052,82.14581032932028],[131.4506916125006,81.64646175464031],[129.80385082210887,76.74514380474466],[130.14500207612204,73.57146214321665],[131.59809444597076,70.28672504122505],[136.72992436362588,65.06115908881202],[140.8499176595349,61.94456184724777],[146.1572277117772,58.91105132922394],[147.58743859663932,55.37274121110113],[147.45467965877356,52.79482393899616],[149.80446666834254,51.75459116210004],[152.03218112111801,51.83599080153499],[154.51679793033745,52.75659961598649],[155.63574459370858,55.19272854543442],[152.9048388312652,58.474509515848695],[151.94434371467972,61.47338560082744],[152.90503375345878,65.23809369245691],[151.19281993240298,67.64426977712628],[146.95757916228936,69.74879455425298],[144.48075843527175,70.51007085978745],[141.54772375007562,72.36648668800308],[139.83714396241632,73.88420909919478],[138.81320748223047,75.98927607222868],[136.34083774324534,82.89448801717754]]],[[[242.6301239188358,20.928456517277937],[244.524835317996,21.855376138727024],[246.6086163941788,21.761013035977157],[249.12129206432147,23.10146816821816],[250.1117660430242,25.197631494994766],[251.76251507809565,26.88421878666668],[252.6631608942832,27.058905701170715],[254.04950445149436,31.70327047207047],[255.17233874299583,32.345092794198536],[254.9367696203331,37.7407614473218],[253.70304905956502,39.4145429917744],[251.80739785296336,44.7114156766952],[249.90968751849374,45.82769180800642],[249.72427274907935,49.724662359280046],[250.2664460742688,54.83944813011158],[249.8178817833537,58.55608165339845],[248.01038403767052,58.553854051773214],[246.5378587259051,59.28185538963862],[248.02208626423464,61.53030015680088],[247.26537556838704,62.45965023516237],[245.71993136577203,62.35374358450417],[243.4812267369355,64.225426133984],[242.53627454611478,65.89838053896256],[239.22662411901285,68.31475394301197],[239.0386087280138,69.33785945171076],[237.61846349405133,69.52209458596099],[236.29666729084443,71.01072123255062],[230.4334568523121,68.9669997892297],[226.84143015964509,68.59763892718593],[224.16856566813613,68.68631465158842],[219.1841982378101,67.66846130606882],[217.29344286226942,67.48768712871652],[216.15887134867586,66.46513384670334],[215.40333526267494,67.5815648175726],[214.26936087294837,67.86109792992875],[213.60692101484594,66.74672578934496],[211.9039802911199,66.00662760499381],[210.39006798669138,64.79974545667892],[208.3090049147986,61.17722459511424],[206.79516022169557,60.8078714318267],[206.2280101316071,59.69303088661218],[204.9031059053762,59.04454692812806],[202.288768478747,58.63241937203611],[198.65762098343723,57.008601142287716],[193.92516050737657,55.80687686920237],[192.40686891096516,52.09245834452577],[191.26996373694993,51.53637191748385],[190.32084187578704,50.14401487701298],[190.59796672407452,44.8479552497879],[190.40677524552552,43.64038902698394],[191.71286750020155,43.15376365445945],[195.22776508085818,39.17612603608313],[197.07131412657003,36.7911618224075],[197.46987715866888,33.241415436488296],[198.3503185037968,32.84447979842298],[199.57713709010568,30.911782057693472],[205.9174884290591,29.24087621122908],[209.69428929240772,27.00022291789446],[212.05580804562027,24.948888383579742],[215.0853986407193,23.474541488667],[216.21799341865486,22.070327972682662],[217.92045829808038,21.41320162463444],[219.3403319945726,21.412824825597],[220.2860813534474,20.389834261116903],[221.61142627081324,20.667674773922045],[223.0320967666261,22.433048166366916],[225.7773168900162,23.080634815925805],[226.9132041728082,23.823685939339157],[228.0484313536286,21.685001963548984],[230.41453602769184,20.75443225590334],[232.8736446959423,21.129521063308403],[235.81139665471585,21.12068953329026],[237.3249895720922,22.05105270953436],[238.5567023697979,21.862789488171074],[241.1150433373256,19.999999999999545],[242.6301239188358,20.928456517277937]]]]}
Raw
index.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<style>
path {
fill: #ddd;
}
.cell {
opacity: 0.4;
stroke-width: 1px;
stroke: #666;
fill: none;
}
</style>
</head>
<body>
<svg width="960" height="500"></svg>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/4.2.3/d3.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/topojson/1.6.20/topojson.min.js"></script>
<script src="polybool.min.js"></script>
<script>
var svg = d3.select("svg"),
colors;
d3.queue()
.defer(d3.json, "HI.json")
.defer(d3.json, "CA.json")
.await(ready);
function ready(err, hiGeo, caGeo) {
var diagram,
ca = caGeo.coordinates[0].slice(0, caGeo.coordinates[0].length - 1),
hi = hiGeo.coordinates.map(function(d){ return d[0].slice(0, d[0].length - 1); });
colors = hi.map(function(d, i){
return d3.interpolateRainbow(i / hi.length);
});
svg.append("path")
.attr("class", "ca")
.datum(ca)
.attr("d", join);
diagram = relaxedVoronoi(ca);
d3.queue(1)
.defer(wait, 1000)
.defer(drawCells, diagram.polygons)
.defer(removeOutsideCells)
.defer(getGroups, hi, diagram.polygons)
.defer(merge, hi, diagram)
.defer(clip, hi, ca)
.awaitAll(function(err){
d3.selectAll(".merged").each(morph);
});
}
function drawCells(polygons, cb) {
svg.selectAll(".cell")
.data(polygons)
.enter()
.append("path")
.attr("class", "cell")
.attr("d", join);
wait(1500, cb);
}
function removeOutsideCells(cb) {
svg.selectAll(".cell").filter(function(d){
return d.outside;
}).remove();
wait(1500, cb);
}
function getGroups(islands, polygons, cb) {
var areaAssigned = totalArea = 0;
var groups = islands.map(function(island, i){
var area = d3.polygonArea(island);
totalArea += area;
return {
index: i,
area: area,
centroid: d3.polygonCentroid(island),
targetArea: 0
};
});
assignCell();
function assignCell() {
if (areaAssigned) {
// Get the source polygon that's the most under-assigned
groups.sort(function(a,b){
return (a.targetArea / areaAssigned) / (a.area / totalArea) - (b.targetArea / areaAssigned) / (b.area / totalArea);
});
}
var found = groups.some(function(source){
var closest,
minDistance = Infinity;
if (!source.head) {
polygons.forEach(function(cell){
var distance;
if (!cell.outside && cell.assigned === undefined && (distance = distanceBetween(cell.centroid, source.centroid)) < minDistance) {
minDistance = distance;
closest = cell;
}
});
closest.assigned = source.index;
source.targetArea += closest.area;
areaAssigned += closest.area;
source.head = closest;
return true;
}
closest = findAvailableNeighbor(source.head, source.index);
if (closest) {
closest.assigned = source.index;
source.targetArea += closest.area;
areaAssigned += closest.area;
return true;
}
return false;
});
svg.selectAll(".cell")
.style("fill", function(d){
return colors[d.assigned];
});
if (found) {
requestAnimationFrame(assignCell);
} else {
cb(null);
}
}
}
function merge(hi, diagram, cb) {
var topology = createTopology(diagram.diagram, diagram.polygons);
var merged = d3.range(hi.length).map(function(i){
return topojson.merge(topology, topology.objects.voronoi.geometries.filter(function(g){return g.properties.assigned === i; })).coordinates[0][0];
});
svg.selectAll(".merged")
.data(merged)
.enter()
.append("path")
.attr("class", "merged")
.attr("d", join)
.style("fill", function(d, i){
return colors[i];
});
svg.selectAll(".cell").remove();
wait(1500, cb);
}
function clip(hi, ca, cb) {
var merged = svg.selectAll(".merged").data()
.map(function(d, i){
var island = hi[i],
clipped = clipPolygon(d, ca);
clipped = align(clipped, island);
return {
coordinates: [clipped, island],
color: colors[i],
split: false,
first: !i
};
});
svg.selectAll(".merged")
.data(merged)
.attr("d", function(d){
return join(d.coordinates[0]);
});
wait(1500, cb);
}
function morph(d) {
d.coordinates.reverse();
d.split = !d.split;
var t = d3.select(this).transition()
.delay(500)
.duration(3000)
.style("fill", d.split ? d.color : "#ddd")
.attr("d", join(d.coordinates[0]))
.on("end", morph);
if (d.first) {
t.on(d.split ? "start.bg" : "end.bg", function(){
d3.select(".ca").style("display", d.split ? "none" : "block");
});
}
}
function relaxedVoronoi(background) {
var bounds = d3.geoPath().bounds({ type: "Polygon", coordinates: [background] }),
voronoi = d3.voronoi().extent([[bounds[0][0] - 1, bounds[0][1] - 1],[bounds[1][0] + 1, bounds[1][1] + 1]]),
points = d3.range(300).map(function(){
return [
bounds[0][0] + Math.random() * (bounds[1][0] - bounds[0][0]),
bounds[0][1] + Math.random() * (bounds[1][1] - bounds[0][1])
];
});
diagram = voronoi(points);
for (var i = 0; i < 25; i++) {
polygons = diagram.polygons();
diagram = voronoi(polygons.map(d3.polygonCentroid));
}
polygons.forEach(function(poly, i){
poly.index = i;
poly.centroid = d3.polygonCentroid(poly);
poly.area = d3.polygonArea(poly);
poly.neighbors = [];
});
addNeighbors(polygons, diagram.edges, background);
return {
diagram: diagram,
polygons: polygons
};
}
function addNeighbors(polygons, edges, boundary) {
edges.forEach(function(edge){
if (!edge.left || !edge.right) {
return;
}
var left = polygons[edge.left.index],
right = polygons[edge.right.index];
if (left.outside === undefined) left.outside = isPolygonOutside(left, boundary);
if (right.outside === undefined) right.outside = isPolygonOutside(right, boundary);
if (!left.outside && !right.outside) {
left.neighbors.push(right);
right.neighbors.push(left);
}
});
}
// Lazy breadth-first search
function findAvailableNeighbor(head, index) {
var queue = [head],
visited = {},
current;
while (queue.length) {
current = queue.shift();
if (current.assigned === undefined) {
return current;
}
visited[current.index] = true;
current.neighbors.forEach(function(neighbor){
if (!visited[neighbor.index] && (neighbor.assigned === undefined || neighbor.assigned === index)) queue.push(neighbor);
});
}
return null;
}
function align(a, b) {
// Same number of points on each ring
if (a.length < b.length) {
addPoints(a, b.length - a.length);
} else if (b.length < a.length) {
addPoints(b, a.length - b.length);
}
return wind(a, b);
}
function addPoints(ring, numPoints) {
var desiredLength = ring.length + numPoints,
step = d3.polygonLength(ring) / numPoints;
var i = 0,
cursor = 0,
insertAt = step / 2;
while (ring.length < desiredLength) {
var a = ring[i],
b = ring[(i + 1) % ring.length];
var segment = distanceBetween(a, b);
if (insertAt <= cursor + segment) {
ring.splice(i + 1, 0, pointBetween(a, b, (insertAt - cursor) / segment));
insertAt += step;
continue;
}
cursor += segment;
i++;
}
}
function wind(ring, vs) {
var len = ring.length,
min = Infinity,
bestOffset,
backwards = false,
forwardSum,
backwardSum;
for (var offset = 0, len = ring.length; offset < len; offset++) {
forwardSum = backwardSum = 0;
// Probably a more efficient way to do this...
vs.forEach(function(p, i){
var forwardPos = (offset + i) % len,
backwardPos = len - offset - i - 1 + (len - offset - i < 1 ? len : 0);
forwardDistance = distanceBetween(ring[forwardPos], p),
backwardDistance = distanceBetween(ring[backwardPos], p);
forwardSum += forwardDistance * forwardDistance;
backwardSum += backwardDistance * backwardDistance;
});
if (forwardSum < min) {
min = forwardSum;
bestOffset = offset;
backwards = false;
}
if (backwardSum < min) {
min = backwardSum;
bestOffset = offset;
backwards = true;
}
}
if (backwards) {
return ring.slice(len - bestOffset).concat(ring.slice(0, len - bestOffset)).reverse();
} else {
return ring.slice(bestOffset).concat(ring.slice(0, bestOffset));
}
}
// Assumes a single polygon out, not robust...
function clipPolygon(polygon, boundary) {
var intersection = PolyBool.intersect({
regions: [
polygon
],
inverted: false
},{
regions: [
boundary
],
inverted: false
});
intersection.regions.sort(function(a,b){
return d3.polygonArea(b) - d3.polygonArea(a);
});
return intersection.regions[0];
}
function isPolygonOutside(polygon, boundary) {
// Closed rings
polygon = polygon.concat([polygon[0]]);
boundary = boundary.concat([boundary[0]]);
if (polygon.some(function(point){ return d3.polygonContains(boundary, point); })) {
return false;
}
for (var i = 0, l = polygon.length - 1; i < l; i++) {
for (var j = 0, m = boundary.length - 1; j < m; j++) {
if (segmentsIntersect([polygon[i], polygon[i + 1]], [boundary[j], boundary[j + 1]])) {
return false;
}
}
}
return true;
};
// TODO deal with points on segments?
function segmentsIntersect(a, b) {
if (orientation(a[0], a[1], b[0]) === orientation(a[0], a[1], b[1])) {
return false;
}
return orientation(b[0], b[1], a[0]) !== orientation(b[0], b[1], a[1]);
}
function orientation(p, q, r) {
var val = (q[1] - p[1]) * (r[0] - q[0]) -
(q[0] - p[0]) * (r[1] - q[1]);
return val > 0 ? 1 : val < 0 ? -1 : 0;
}
function distanceBetween(a, b) {
var dx = a[0] - b[0],
dy = a[1] - b[1];
return Math.sqrt(dx * dx + dy * dy);
}
function pointBetween(a, b, pct) {
var point = [
a[0] + (b[0] - a[0]) * pct,
a[1] + (b[1] - a[1]) * pct
];
return point;
}
function join(ring) {
return "M" + ring.join("L") + "Z";
}
function wait(ms, cb) {
d3.timeout(function(){
cb(null);
}, ms);
}
// Modified from https://bl.ocks.org/mbostock/cd52a201d7694eb9d890
function createTopology(diagram, polygons) {
var cells = diagram.cells,
arcs = [],
arcIndex = -1,
arcIndexByEdge = {};
return {
objects: {
voronoi: {
type: "GeometryCollection",
geometries: cells.map(function(cell, cellNumber) {
var cell,
site = cell.site,
halfedges = cell.halfedges,
cellArcs = [],
clipArc;
halfedges.forEach(function(halfedge) {
var edge = diagram.edges[halfedge];
if (edge.right) {
var l = edge.left.index,
r = edge.right.index,
k = l + "," + r,
i = arcIndexByEdge[k];
if (i == null) arcs[i = arcIndexByEdge[k] = ++arcIndex] = edge;
cellArcs.push(site === edge.left ? i : ~i);
clipArc = null;
} else if (clipArc) { // Coalesce border edges.
if (edge.left) edge = edge.slice(); // Copy-on-write.
clipArc.push(edge[1]);
} else {
arcs[++arcIndex] = clipArc = edge;
cellArcs.push(arcIndex);
}
});
// Ensure the last point in the polygon is identical to the first point.
var firstArcIndex = cellArcs[0],
lastArcIndex = cellArcs[cellArcs.length - 1],
firstArc = arcs[firstArcIndex < 0 ? ~firstArcIndex : firstArcIndex],
lastArc = arcs[lastArcIndex < 0 ? ~lastArcIndex : lastArcIndex];
lastArc[lastArcIndex < 0 ? 0 : lastArc.length - 1] = firstArc[firstArcIndex < 0 ? firstArc.length - 1 : 0].slice();
return {
type: "Polygon",
properties: {
assigned: polygons[cellNumber].assigned
},
arcs: [cellArcs]
};
}).filter(function(d){ return d.properties.assigned !== undefined; })
}
},
arcs: arcs
};
}
</script>
Raw
polybool.min.js
(function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){/*
* @copyright 2016 Sean Connelly (@voidqk), http://syntheti.cc
* @license MIT
* @preserve Project Home: https://github.com/voidqk/polybooljs
*/
var BuildLog=require("./lib/build-log");var Epsilon=require("./lib/epsilon");var Intersecter=require("./lib/intersecter");var SegmentChainer=require("./lib/segment-chainer");var SegmentSelector=require("./lib/segment-selector");var buildLog=false;var epsilon=Epsilon();var PolyBool={buildLog:function(bl){if(bl===true)buildLog=BuildLog();else if(bl===false)buildLog=false;return buildLog===false?false:buildLog.list},epsilon:function(v){return epsilon.epsilon(v)},segments:function(poly){var i=Intersecter(true,epsilon,buildLog);poly.regions.forEach(i.addRegion);return{segments:i.calculate(poly.inverted),inverted:poly.inverted}},combine:function(segments1,segments2){var i3=Intersecter(false,epsilon,buildLog);return{combined:i3.calculate(segments1.segments,segments1.inverted,segments2.segments,segments2.inverted),inverted1:segments1.inverted,inverted2:segments2.inverted}},selectUnion:function(combined){return{segments:SegmentSelector.union(combined.combined,buildLog),inverted:combined.inverted1||combined.inverted2}},selectIntersect:function(combined){return{segments:SegmentSelector.intersect(combined.combined,buildLog),inverted:combined.inverted1&&combined.inverted2}},selectDifference:function(combined){return{segments:SegmentSelector.difference(combined.combined,buildLog),inverted:combined.inverted1&&!combined.inverted2}},selectDifferenceRev:function(combined){return{segments:SegmentSelector.differenceRev(combined.combined,buildLog),inverted:!combined.inverted1&&combined.inverted2}},selectXor:function(combined){return{segments:SegmentSelector.xor(combined.combined,buildLog),inverted:combined.inverted1!==combined.inverted2}},polygon:function(segments){return{regions:SegmentChainer(segments.segments,epsilon,buildLog),inverted:segments.inverted}},union:function(poly1,poly2){return operate(poly1,poly2,PolyBool.selectUnion)},intersect:function(poly1,poly2){return operate(poly1,poly2,PolyBool.selectIntersect)},difference:function(poly1,poly2){return operate(poly1,poly2,PolyBool.selectDifference)},differenceRev:function(poly1,poly2){return operate(poly1,poly2,PolyBool.selectDifferenceRev)},xor:function(poly1,poly2){return operate(poly1,poly2,PolyBool.selectXor)}};function operate(poly1,poly2,selector){var seg1=PolyBool.segments(poly1);var seg2=PolyBool.segments(poly2);var comb=PolyBool.combine(seg1,seg2);var seg3=selector(comb);return PolyBool.polygon(seg3)}if(typeof window==="object")window.PolyBool=PolyBool;module.exports=PolyBool},{"./lib/build-log":2,"./lib/epsilon":3,"./lib/intersecter":4,"./lib/segment-chainer":6,"./lib/segment-selector":7}],2:[function(require,module,exports){function BuildLog(){var my;var nextSegmentId=0;var curVert=false;function push(type,data){my.list.push({type:type,data:data?JSON.parse(JSON.stringify(data)):void 0});return my}my={list:[],segmentId:function(){return nextSegmentId++},checkIntersection:function(seg1,seg2){return push("check",{seg1:seg1,seg2:seg2})},segmentChop:function(seg,end){push("div_seg",{seg:seg,pt:end});return push("chop",{seg:seg,pt:end})},statusRemove:function(seg){return push("pop_seg",{seg:seg})},segmentUpdate:function(seg){return push("seg_update",{seg:seg})},segmentNew:function(seg,primary){return push("new_seg",{seg:seg,primary:primary})},segmentRemove:function(seg){return push("rem_seg",{seg:seg})},tempStatus:function(seg,above,below){return push("temp_status",{seg:seg,above:above,below:below})},rewind:function(seg){return push("rewind",{seg:seg})},status:function(seg,above,below){return push("status",{seg:seg,above:above,below:below})},vert:function(x){if(x===curVert)return my;curVert=x;return push("vert",{x:x})},log:function(data){if(typeof data!=="string")data=JSON.stringify(data,false," ");return push("log",{txt:data})},reset:function(){return push("reset")},selected:function(segs){return push("selected",{segs:segs})},chainStart:function(seg){return push("chain_start",{seg:seg})},chainRemoveHead:function(index,pt){return push("chain_rem_head",{index:index,pt:pt})},chainRemoveTail:function(index,pt){return push("chain_rem_tail",{index:index,pt:pt})},chainNew:function(pt1,pt2){return push("chain_new",{pt1:pt1,pt2:pt2})},chainMatch:function(index){return push("chain_match",{index:index})},chainClose:function(index){return push("chain_close",{index:index})},chainAddHead:function(index,pt){return push("chain_add_head",{index:index,pt:pt})},chainAddTail:function(index,pt){return push("chain_add_tail",{index:index,pt:pt})},chainConnect:function(index1,index2){return push("chain_con",{index1:index1,index2:index2})},chainReverse:function(index){return push("chain_rev",{index:index})},chainJoin:function(index1,index2){return push("chain_join",{index1:index1,index2:index2})},done:function(){return push("done")}};return my}module.exports=BuildLog},{}],3:[function(require,module,exports){function Epsilon(eps){if(typeof eps!=="number")eps=1e-10;var my={epsilon:function(v){if(typeof v==="number")eps=v;return eps},pointAboveOrOnLine:function(pt,left,right){var Ax=left[0];var Ay=left[1];var Bx=right[0];var By=right[1];var Cx=pt[0];var Cy=pt[1];return(Bx-Ax)*(Cy-Ay)-(By-Ay)*(Cx-Ax)>=-eps},pointBetween:function(p,left,right){var d_py_ly=p[1]-left[1];var d_rx_lx=right[0]-left[0];var d_px_lx=p[0]-left[0];var d_ry_ly=right[1]-left[1];var dot=d_px_lx*d_rx_lx+d_py_ly*d_ry_ly;if(dot<eps)return false;var sqlen=d_rx_lx*d_rx_lx+d_ry_ly*d_ry_ly;if(dot-sqlen>-eps)return false;return true},pointsSameX:function(p1,p2){return Math.abs(p1[0]-p2[0])<eps},pointsSameY:function(p1,p2){return Math.abs(p1[1]-p2[1])<eps},pointsSame:function(p1,p2){return my.pointsSameX(p1,p2)&&my.pointsSameY(p1,p2)},pointsCompare:function(p1,p2){if(my.pointsSameX(p1,p2))return my.pointsSameY(p1,p2)?0:p1[1]<p2[1]?-1:1;return p1[0]<p2[0]?-1:1},pointsCollinear:function(pt1,pt2,pt3){var dx1=pt1[0]-pt2[0];var dy1=pt1[1]-pt2[1];var dx2=pt2[0]-pt3[0];var dy2=pt2[1]-pt3[1];return Math.abs(dx1*dy2-dx2*dy1)<eps},linesIntersect:function(a0,a1,b0,b1){var adx=a1[0]-a0[0];var ady=a1[1]-a0[1];var bdx=b1[0]-b0[0];var bdy=b1[1]-b0[1];var axb=adx*bdy-ady*bdx;if(Math.abs(axb)<eps)return false;var dx=a0[0]-b0[0];var dy=a0[1]-b0[1];var A=(bdx*dy-bdy*dx)/axb;var B=(adx*dy-ady*dx)/axb;var ret={alongA:0,alongB:0,pt:[a0[0]+A*adx,a0[1]+A*ady]};if(A<=-eps)ret.alongA=-2;else if(A<eps)ret.alongA=-1;else if(A-1<=-eps)ret.alongA=0;else if(A-1<eps)ret.alongA=1;else ret.alongA=2;if(B<=-eps)ret.alongB=-2;else if(B<eps)ret.alongB=-1;else if(B-1<=-eps)ret.alongB=0;else if(B-1<eps)ret.alongB=1;else ret.alongB=2;return ret}};return my}module.exports=Epsilon},{}],4:[function(require,module,exports){var LinkedList=require("./linked-list");function Intersecter(selfIntersection,eps,buildLog){function segmentNew(start,end){return{id:buildLog?buildLog.segmentId():-1,start:start,end:end,myFill:{above:null,below:null},otherFill:null}}function segmentCopy(start,end,seg){return{id:buildLog?buildLog.segmentId():-1,start:start,end:end,myFill:{above:seg.myFill.above,below:seg.myFill.below},otherFill:null}}var event_root=LinkedList.create();function eventCompare(p1_isStart,p1_1,p1_2,p2_isStart,p2_1,p2_2){var comp=eps.pointsCompare(p1_1,p2_1);if(comp!==0)return comp;if(eps.pointsSame(p1_2,p2_2))return 0;if(p1_isStart!==p2_isStart)return p1_isStart?1:-1;return eps.pointAboveOrOnLine(p1_2,p2_isStart?p2_1:p2_2,p2_isStart?p2_2:p2_1)?1:-1}function eventAdd(ev,other_pt){event_root.insertBefore(ev,function(here){var comp=eventCompare(ev.isStart,ev.pt,other_pt,here.isStart,here.pt,here.other.pt);return comp<0})}function eventAddSegmentStart(seg,primary){var ev_start=LinkedList.node({isStart:true,pt:seg.start,seg:seg,primary:primary,other:null,status:null});eventAdd(ev_start,seg.end);return ev_start}function eventAddSegmentEnd(ev_start,seg,primary){var ev_end=LinkedList.node({isStart:false,pt:seg.end,seg:seg,primary:primary,other:ev_start,status:null});ev_start.other=ev_end;eventAdd(ev_end,ev_start.pt)}function eventAddSegment(seg,primary){var ev_start=eventAddSegmentStart(seg,primary);eventAddSegmentEnd(ev_start,seg,primary);return ev_start}function eventUpdateEnd(ev,end){if(buildLog)buildLog.segmentChop(ev.seg,end);ev.other.remove();ev.seg.end=end;ev.other.pt=end;eventAdd(ev.other,ev.pt)}function eventDivide(ev,pt){var ns=segmentCopy(pt,ev.seg.end,ev.seg);eventUpdateEnd(ev,pt);return eventAddSegment(ns,ev.primary)}function calculate(primaryPolyInverted,secondaryPolyInverted){var status_root=LinkedList.create();function statusCompare(ev1,ev2){var a1=ev1.seg.start;var a2=ev1.seg.end;var b1=ev2.seg.start;var b2=ev2.seg.end;if(eps.pointsCollinear(a1,b1,b2)){if(eps.pointsCollinear(a2,b1,b2))return 1;return eps.pointAboveOrOnLine(a2,b1,b2)?1:-1}return eps.pointAboveOrOnLine(a1,b1,b2)?1:-1}function statusFindSurrounding(ev){return status_root.findTransition(function(here){var comp=statusCompare(ev,here.ev);return comp>0})}function checkIntersection(ev1,ev2){var seg1=ev1.seg;var seg2=ev2.seg;var a1=seg1.start;var a2=seg1.end;var b1=seg2.start;var b2=seg2.end;if(buildLog)buildLog.checkIntersection(seg1,seg2);var i=eps.linesIntersect(a1,a2,b1,b2);if(i===false){if(!eps.pointsCollinear(a1,a2,b1))return false;if(eps.pointsSame(a1,b2)||eps.pointsSame(a2,b1))return false;var a1_equ_b1=eps.pointsSame(a1,b1);var a2_equ_b2=eps.pointsSame(a2,b2);if(a1_equ_b1&&a2_equ_b2)return ev2;var a1_between=!a1_equ_b1&&eps.pointBetween(a1,b1,b2);var a2_between=!a2_equ_b2&&eps.pointBetween(a2,b1,b2);if(a1_equ_b1){if(a2_between){eventDivide(ev2,a2)}else{eventDivide(ev1,b2)}return ev2}else if(a1_between){if(!a2_equ_b2){if(a2_between){eventDivide(ev2,a2)}else{eventDivide(ev1,b2)}}eventDivide(ev2,a1)}}else{if(i.alongA===0){if(i.alongB===-1)eventDivide(ev1,b1);else if(i.alongB===0)eventDivide(ev1,i.pt);else if(i.alongB===1)eventDivide(ev1,b2)}if(i.alongB===0){if(i.alongA===-1)eventDivide(ev2,a1);else if(i.alongA===0)eventDivide(ev2,i.pt);else if(i.alongA===1)eventDivide(ev2,a2)}}return false}var segments=[];while(!event_root.isEmpty()){var ev=event_root.getHead();if(buildLog)buildLog.vert(ev.pt[0]);if(ev.isStart){if(buildLog)buildLog.segmentNew(ev.seg,ev.primary);var surrounding=statusFindSurrounding(ev);var above=surrounding.before?surrounding.before.ev:null;var below=surrounding.after?surrounding.after.ev:null;if(buildLog){buildLog.tempStatus(ev.seg,above?above.seg:false,below?below.seg:false)}function checkBothIntersections(){if(above){var eve=checkIntersection(ev,above);if(eve)return eve}if(below)return checkIntersection(ev,below);return false}var eve=checkBothIntersections();if(eve){if(selfIntersection){var toggle;if(ev.seg.myFill.below===null)toggle=true;else toggle=ev.seg.myFill.above!==ev.seg.myFill.below;if(toggle)eve.seg.myFill.above=!eve.seg.myFill.above}else{eve.seg.otherFill=ev.seg.myFill}if(buildLog)buildLog.segmentUpdate(eve.seg);ev.other.remove();ev.remove()}if(event_root.getHead()!==ev){if(buildLog)buildLog.rewind(ev.seg);continue}if(selfIntersection){var toggle;if(ev.seg.myFill.below===null)toggle=true;else toggle=ev.seg.myFill.above!==ev.seg.myFill.below;if(!below){ev.seg.myFill.below=primaryPolyInverted}else{ev.seg.myFill.below=below.seg.myFill.above}if(toggle)ev.seg.myFill.above=!ev.seg.myFill.below;else ev.seg.myFill.above=ev.seg.myFill.below}else{if(ev.seg.otherFill===null){var inside;if(!below){inside=ev.primary?secondaryPolyInverted:primaryPolyInverted}else{if(ev.primary===below.primary)inside=below.seg.otherFill.above;else inside=below.seg.myFill.above}ev.seg.otherFill={above:inside,below:inside}}}if(buildLog){buildLog.status(ev.seg,above?above.seg:false,below?below.seg:false)}ev.other.status=surrounding.insert(LinkedList.node({ev:ev}))}else{var st=ev.status;if(st===null){throw new Error("PolyBool: Zero-length segment detected; your epsilon is "+"probably too small or too large")}if(status_root.exists(st.prev)&&status_root.exists(st.next))checkIntersection(st.prev.ev,st.next.ev);if(buildLog)buildLog.statusRemove(st.ev.seg);st.remove();if(!ev.primary){var s=ev.seg.myFill;ev.seg.myFill=ev.seg.otherFill;ev.seg.otherFill=s}segments.push(ev.seg)}event_root.getHead().remove()}if(buildLog)buildLog.done();return segments}if(!selfIntersection){return{calculate:function(segments1,inverted1,segments2,inverted2){segments1.forEach(function(seg){eventAddSegment(seg,true)});segments2.forEach(function(seg){eventAddSegment(seg,false)});return calculate(inverted1,inverted2)}}}return{addRegion:function(region){var pt1;var pt2=region[region.length-1];for(var i=0;i<region.length;i++){pt1=pt2;pt2=region[i];var forward=eps.pointsCompare(pt1,pt2);if(forward===0)continue;eventAddSegment(segmentNew(forward<0?pt1:pt2,forward<0?pt2:pt1),true)}},calculate:function(inverted){return calculate(inverted,false)}}}module.exports=Intersecter},{"./linked-list":5}],5:[function(require,module,exports){var LinkedList={create:function(){var my={root:{root:true,next:null},exists:function(node){if(node===null||node===my.root)return false;return true},isEmpty:function(){return my.root.next===null},getHead:function(){return my.root.next},insertBefore:function(node,check){var last=my.root;var here=my.root.next;while(here!==null){if(check(here)){node.prev=here.prev;node.next=here;here.prev.next=node;here.prev=node;return}last=here;here=here.next}last.next=node;node.prev=last;node.next=null},findTransition:function(check){var prev=my.root;var here=my.root.next;while(here!==null){if(check(here))break;prev=here;here=here.next}return{before:prev===my.root?null:prev,after:here,insert:function(node){node.prev=prev;node.next=here;prev.next=node;if(here!==null)here.prev=node;return node}}}};return my},node:function(data){data.prev=null;data.next=null;data.remove=function(){data.prev.next=data.next;if(data.next)data.next.prev=data.prev;data.prev=null;data.next=null};return data}};module.exports=LinkedList},{}],6:[function(require,module,exports){function SegmentChainer(segments,eps,buildLog){var chains=[];var regions=[];segments.forEach(function(seg){var pt1=seg.start;var pt2=seg.end;if(buildLog)buildLog.chainStart(seg);var first_match={index:0,matches_head:false,matches_pt1:false};var second_match={index:0,matches_head:false,matches_pt1:false};var next_match=first_match;function setMatch(index,matches_head,matches_pt1){next_match.index=index;next_match.matches_head=matches_head;next_match.matches_pt1=matches_pt1;if(next_match===first_match){next_match=second_match;return false}next_match=null;return true}for(var i=0;i<chains.length;i++){var chain=chains[i];var head=chain[0];var head2=chain[1];var tail=chain[chain.length-1];var tail2=chain[chain.length-2];if(eps.pointsSame(head,pt1)){if(setMatch(i,true,true))break}else if(eps.pointsSame(head,pt2)){if(setMatch(i,true,false))break}else if(eps.pointsSame(tail,pt1)){if(setMatch(i,false,true))break}else if(eps.pointsSame(tail,pt2)){if(setMatch(i,false,false))break}}if(next_match===first_match){chains.push([pt1,pt2]);if(buildLog)buildLog.chainNew(pt1,pt2);return}if(next_match===second_match){if(buildLog)buildLog.chainMatch(first_match.index);var index=first_match.index;var pt=first_match.matches_pt1?pt2:pt1;var addToHead=first_match.matches_head;var chain=chains[index];var grow=addToHead?chain[0]:chain[chain.length-1];var grow2=addToHead?chain[1]:chain[chain.length-2];var oppo=addToHead?chain[chain.length-1]:chain[0];var oppo2=addToHead?chain[chain.length-2]:chain[1];if(eps.pointsCollinear(grow2,grow,pt)){if(addToHead){if(buildLog)buildLog.chainRemoveHead(first_match.index,pt);chain.shift()}else{if(buildLog)buildLog.chainRemoveTail(first_match.index,pt);chain.pop()}grow=grow2}if(eps.pointsSame(oppo,pt)){chains.splice(index,1);if(eps.pointsCollinear(oppo2,oppo,grow)){if(addToHead){if(buildLog)buildLog.chainRemoveTail(first_match.index,grow);chain.pop()}else{if(buildLog)buildLog.chainRemoveHead(first_match.index,grow);chain.shift()}}if(buildLog)buildLog.chainClose(first_match.index);regions.push(chain);return}if(addToHead){if(buildLog)buildLog.chainAddHead(first_match.index,pt);chain.unshift(pt)}else{if(buildLog)buildLog.chainAddTail(first_match.index,pt);chain.push(pt)}return}function reverseChain(index){if(buildLog)buildLog.chainReverse(index);chains[index].reverse()}function appendChain(index1,index2){var chain1=chains[index1];var chain2=chains[index2];var tail=chain1[chain1.length-1];var tail2=chain1[chain1.length-2];var head=chain2[0];var head2=chain2[1];if(eps.pointsCollinear(tail2,tail,head)){if(buildLog)buildLog.chainRemoveTail(index1,tail);chain1.pop();tail=tail2}if(eps.pointsCollinear(tail,head,head2)){if(buildLog)buildLog.chainRemoveHead(index2,head);chain2.shift()}if(buildLog)buildLog.chainJoin(index1,index2);chains[index1]=chain1.concat(chain2);chains.splice(index2,1)}var F=first_match.index;var S=second_match.index;if(buildLog)buildLog.chainConnect(F,S);var reverseF=chains[F].length<chains[S].length;if(first_match.matches_head){if(second_match.matches_head){if(reverseF){reverseChain(F);appendChain(F,S)}else{reverseChain(S);appendChain(S,F)}}else{appendChain(S,F)}}else{if(second_match.matches_head){appendChain(F,S)}else{if(reverseF){reverseChain(F);appendChain(S,F)}else{reverseChain(S);appendChain(F,S)}}}});return regions}module.exports=SegmentChainer},{}],7:[function(require,module,exports){function select(segments,selection,buildLog){var result=[];segments.forEach(function(seg){var index=(seg.myFill.above?8:0)+(seg.myFill.below?4:0)+(seg.otherFill&&seg.otherFill.above?2:0)+(seg.otherFill&&seg.otherFill.below?1:0);if(selection[index]!==0){result.push({id:buildLog?buildLog.segmentId():-1,start:seg.start,end:seg.end,myFill:{above:selection[index]===1,below:selection[index]===2},otherFill:null})}});if(buildLog)buildLog.selected(result);return result}var SegmentSelector={union:function(segments,buildLog){return select(segments,[0,2,1,0,2,2,0,0,1,0,1,0,0,0,0,0],buildLog)},intersect:function(segments,buildLog){return select(segments,[0,0,0,0,0,2,0,2,0,0,1,1,0,2,1,0],buildLog)},difference:function(segments,buildLog){return select(segments,[0,0,0,0,2,0,2,0,1,1,0,0,0,1,2,0],buildLog)},differenceRev:function(segments,buildLog){return select(segments,[0,2,1,0,0,0,1,1,0,2,0,2,0,0,0,0],buildLog)},xor:function(segments,buildLog){return select(segments,[0,2,1,0,2,0,0,1,1,0,0,2,0,1,2,0],buildLog)}};module.exports=SegmentSelector},{}]},{},[1]);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment