Javascript - move a star randomly if mean distance is reduced
(with an animation of the process)
This doesn't give such a busy animation as my first answer, having long periods with no movement as potential rearrangements are tested and rejected. However, the final result has a lower mean distance, so this method is an improvement.
The approach is still very simple:
- Choose a star at random
- Move it a random distance in a random direction
- If the mean distance is reduced, keep the new position
This process is repeated a large number of times, gradually decreasing the amount by which the stars are moved. The random choice of distance to move is biased towards smaller distances, so progress is in small alterations interspersed with the occasional larger jump. Each step takes longer than in my first answer, as measuring the mean distance is a slow process requiring sampling the entire canton.
As required by the question, this does not use the built in random function, instead using xorshift.
Much of the code covers set up and animation - the part that applies the algorithm is the function adjustStars.
Code
You can watch the process in progress in the Stack Snippet below.
stars = []; timeoutId = 0; resetRandomNumberGenerator(); function resetRandomNumberGenerator() { rng_x = 114; // Numbers for the random number generator. rng_y = 342; rng_z = 982; rng_w = 443; } $(document).ready(function() { c = document.getElementById('canton'); ctx = c.getContext('2d'); resizeCanvas(); }); function stop() { clearTimeout(timeoutId); } function arrange() { clearTimeout(timeoutId); resetStars(); resetRandomNumberGenerator(); maxStepSize = Math.min(cantonWidth, cantonHeight) / 16; adjustStars(maxStepSize, 7000, 15000); } function resizeCanvas() { cantonWidth = parseFloat($('#width').val()); cantonHeight = parseFloat($('#height').val()); starRadius = cantonHeight / 20; document.getElementById('canton').width = cantonWidth; document.getElementById('canton').height = cantonHeight; ctx.fillStyle = 'white'; resetStars(); } function resetStars() { stop(); stars = []; population = parseInt($('#stars').val(), 10); shortSide = Math.floor(Math.sqrt(population)); longSide = Math.ceil(population / shortSide); if (cantonWidth < cantonHeight) { horizontalStars = shortSide; verticalStars = longSide; } else { horizontalStars = longSide; verticalStars = shortSide; } horizontalSpacing = cantonWidth / horizontalStars; verticalSpacing = cantonHeight / verticalStars; for (var i = 0; i < population; i++) { x = (0.5 + (i % horizontalStars)) * horizontalSpacing; y = (0.5 + Math.floor(i / horizontalStars)) * verticalSpacing; stars.push([x, y]); } drawStars(); updateOutputText(); } function adjustStars(stepSize, maxSteps, numberOfPoints) { $('#stepsRemaining').text(maxSteps + ' steps remaining'); var points = randomPoints(numberOfPoints); currentMean = meanDistance(stars, points); potentialStars = shiftedStars(stepSize); potentialMean = meanDistance(potentialStars, points); if (potentialMean < currentMean) { stars = potentialStars; } drawStars(); updateOutputText(); if (maxSteps > 0) { timeoutId = setTimeout(adjustStars, 10, stepSize * 0.999, maxSteps - 1, numberOfPoints); } } function shiftedStars(stepSize) { shifted = []; chosenOne = Math.floor(xorshift() * stars.length); for (i = 0; i < stars.length; i++) { star = stars[i]; x = star[0]; y = star[1]; if (i === chosenOne) { for (n = 0; n < 10; n++) { x += xorshift() * stepSize; x -= xorshift() * stepSize; y += xorshift() * stepSize; y -= xorshift() * stepSize; } if (x < 0) x = 0; if (x > cantonWidth) x = cantonWidth; if (y < 0) y = 0; if (y > cantonHeight) y = cantonHeight; } shifted.push([x, y]); } return shifted; } function meanDistance(arrayOfStars, arrayOfPoints) { var totalDistance = 0; for (i = 0; i < arrayOfPoints.length; i++) { point = arrayOfPoints[i]; x = point[0]; y = point[1]; totalDistance += nearestStarDistance(x, y, arrayOfStars); } return totalDistance / arrayOfPoints.length; } function randomPoints(numberOfPoints) { var arrayOfPoints = []; for (i = 0; i < numberOfPoints; i++) { x = xorshift() * cantonWidth; y = xorshift() * cantonHeight; arrayOfPoints.push([x, y]); } return arrayOfPoints; } function updateOutputText() { starText = ''; for (var i = 0; i < stars.length; i++) { starText += stars[i][0] + ', ' + stars[i][1] + '\n'; } $('#coordinateList').text(starText); } function xorshift() { rng_t = rng_x ^ (rng_x << 11); rng_x = rng_y; rng_y = rng_z; rng_z = rng_w; rng_w = rng_w ^ (rng_w >> 19) ^ rng_t ^ (rng_t >> 8); result = rng_w / 2147483648 return result } function nearestStarDistance(x, y, starsToUse) { var distances = []; for (var i = 0; i < stars.length; i++) { star = starsToUse[i]; distances.push(distance(x, y, star[0], star[1])); } minimum = Infinity; for (i = 0; i < distances.length; i++) { if (distances[i] < minimum) { minimum = distances[i]; } } return minimum; } function distance(x1, y1, x2, y2) { var x = x2 - x1; var y = y2 - y1; return Math.sqrt(x * x + y * y); } function drawStars() { ctx.clearRect(0, 0, cantonWidth, cantonHeight); for (i = 0; i < stars.length; i++) { star = stars[i]; x = star[0]; y = star[1]; drawStar(x, y); } } function drawStar(x, y) { ctx.beginPath(); ctx.moveTo(x, y - starRadius); ctx.lineTo(x - 0.588 * starRadius, y + 0.809 * starRadius); ctx.lineTo(x + 0.951 * starRadius, y - 0.309 * starRadius); ctx.lineTo(x - 0.951 * starRadius, y - 0.309 * starRadius); ctx.lineTo(x + 0.588 * starRadius, y + 0.809 * starRadius); ctx.fill(); }
canvas { margin: 0; border: medium solid gray; background-color: blue; }
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script> <input id='stars' onchange='resetStars()' type='number' value='13' min='13' max='50' maxlength='2' step='1'>stars <br> <input id='width' onchange='resizeCanvas()' type='number' value='494' min='1' max='500' maxlength='3' step='any'>width <br> <input id='height' onchange='resizeCanvas()' type='number' value='350' min='1' max='500' maxlength='3' step='any'>height <br> <button type='button' onclick='resetStars()'>Reset Stars</button> <button type='button' onclick='arrange()'>Arrange Stars</button> <button type='button' onclick='stop()'>Stop</button> <textarea id='stepsRemaining' rows='1' readonly></textarea> <br> <canvas id='canton' width='494' height='350'></canvas> <br> <textarea id='coordinateList' rows='50' cols='40' readonly></textarea>
Output for 50 stars
(width = 1.4, height = 1.0)
Mean distance estimated at 0.06402754713808706.
Coordinates:
0.08147037630270487, 0.07571240182553095 0.24516777356538358, 0.0803538189052793 0.431021735247462, 0.07821284835132788 0.6001163609128221, 0.08278495286739646 0.7668077034213632, 0.0821321119375313 0.941333266969696, 0.08040530195264808 1.1229190363750599, 0.07255685332834291 1.3074771164489858, 0.07681674948141588 0.09227450444336446, 0.2257047798057907 0.33559513774978766, 0.20668611954667682 0.5182463448452704, 0.23841239342827816 0.6630614113293541, 0.26097114328053417 0.821886619004045, 0.23577904321258844 1.012597304977012, 0.23308200382761057 1.174938874706673, 0.22593017096601203 1.3285181935709358, 0.24024108928169902 0.0746772556909648, 0.3920030109869904 0.23006559905554042, 0.3204287339854068 0.4086004105498357, 0.3507788129168045 0.5669847710831315, 0.4371913211100495 0.7399474422203116, 0.41599441829489137 0.9099913571857917, 0.36933063808924294 1.1170137101288482, 0.3905679602615213 1.3037811235560612, 0.3979526346564911 0.09290206345982034, 0.5678420747594305 0.23463227399157258, 0.47552307265325633 0.4042403660145938, 0.5030345851947539 0.6611151741402685, 0.5918138006294138 0.8237963249937061, 0.5663224022272697 0.9812774216782155, 0.5032518469083094 1.146386501309064, 0.570255729516661 1.3185563715676663, 0.5571870810112576 0.07541940949872694, 0.7356649763259809 0.2877585652075202, 0.6321535875762999 0.4952646673275116, 0.6343336480073624 0.6965646728710738, 0.9178076185211137 0.7903485281657828, 0.7508031981325222 0.9774998621426763, 0.6683301268754337 1.1539480102558823, 0.7513836972857155 1.3177199931376755, 0.7245296168327016 0.22215183098388988, 0.7769843436963862 0.4048364942297627, 0.7779653803681718 0.5021290208205218, 0.9254525763987298 0.6058821167972933, 0.7683130432395833 0.8777330967719849, 0.9201076171801651 0.9894820530574747, 0.8172934111543102 1.1143371956097312, 0.9265012354173626 1.3045771339439551, 0.9069856484512913 0.0930066325438706, 0.9157592790749175 0.2959676633891297, 0.9251379492518523