Die Flagge der Vereinigten Staaten von Amerika enthält in ihrem Kanton 50 Sterne, die die 50 Staaten repräsentieren.

In der Vergangenheit, als es weniger Staaten gab, gab es natürlich weniger Sterne, und sie waren unterschiedlich angeordnet. Zum Beispiel gab es von 1912 bis 1959 (nach der Aufnahme von New Mexico und Arizona, aber vor Alaska) 48 Sterne in einer rechteckigen Anordnung von 6 × 8.

Die 37-Sterne-Flagge von 1867 bis 1877 (nach der Zulassung von Nebraska, aber vor Colorado) hatte ein asymmetrisches Sternchenmuster.

Für den Fall, dass in Zukunft ein 51. Staat hinzukommt, hat das Army Institute of Heraldry bereits einen vorläufigen Entwurf für eine neue Flagge entwickelt.

Aber es gibt keine General Algorithmus zum Anordnen der Sterne, also lasst uns einen erstellen!

Die Herausforderung

Schreiben Sie ein Programm, das für eine bestimmte Anzahl von Sternen, die im Kanton (blauer Teil) einer US-Flagge platziert werden sollen, optimale Koordinaten ausgibt, an denen diese Sterne platziert werden sollen. Das Koordinatensystem wird mit dem Kanton festgelegt [ nicht der Flagge als Ganzes] mit 0 ≤ x ≤ W und 0 ≤ y ≤ H definiert.

Für diese Herausforderung wird eine „optimale“ Anordnung definiert, die den mittleren (euklidischen) Abstand zwischen einem Punkt im Kanton und dem Zentrum des nächsten Sterns minimiert.

Ein einfacher (wenn auch nicht optimaler) Algorithmus zur Annäherung an diesen Wert lautet:

def mean_distance_to_nearest_star(stars, width, height, point_density=100):
   """
   Approximate the mean distance between a point in the rectangle
   0 < x < width and 0 < y < height, and the nearest point in stars.

   stars -- list of (x, y) points
   width, height -- dimensions of the canton
   """
   total = 0.0
   nx = round(width * point_density)
   ny = round(height * point_density)
   for ix in range(nx):
       x = (ix + 0.5) * width / nx
       for iy in range(ny):
          y = (iy + 0.5) * width / ny
          min_dist = float('inf')
          for sx, sy in stars:
              min_dist = min(min_dist, math.hypot(x - sx, y - sy))
          total += min_dist
   return total / (nx * ny)

Ihr Programm muss drei Befehlszeilenargumente annehmen (ohne den Programmnamen selbst zu zählen):

1. Die Anzahl der Sterne, die im Kanton platziert werden sollen.
2. Die Breite des Kantons. (Muss Gleitkommawerte akzeptieren.)
3. Die Höhe des Kantons. (Muss Gleitkommawerte akzeptieren.)

(Wenn Ihre bevorzugte Programmiersprache keine Befehlszeilenargumente unterstützt, tun Sie etwas ziemlich Äquivalentes und dokumentieren Sie es in Ihrer Antwort.)

Die Ausgabe sollte aus durch Kommas getrennten X- und Y-Werten bestehen, und zwar eins zu einer Zeile. (Reihenfolge der Punkte spielt keine Rolle.)

Beispielsweise:

~$ flagstar 5 1.4 1.0
0.20,0.20
0.20,0.80
0.70,0.50
1.20,0.20
1.20,0.80

Zusätzliche Regeln und Hinweise

• Ich habe jederzeit das Recht, Regelungslücken zu schließen.
• Die Antwortfrist endet am Freitag, den 4. Juli, um 24:00 Uhr (UTC-05: 00). Aufgrund fehlender Antworten wurde die Frist verlängert. TBA.
• Nehmen Sie in Ihre Antwort auf:
  • Der Code Ihres Programms
  • Eine Erklärung, wie es funktioniert
  • Seine Ausgabe mit den Befehlszeilenargumenten 50 1.4 1.0
• Ihr Programm muss innerhalb eines angemessenen Zeitraums ausgeführt werden: Höchstens 5 Minuten auf einem typischen PC. Ich werde nicht streng genug sein, aber dein Programm disqualifizieren, wenn es Stunden dauert .
• Ihr Programm muss deterministisch sein, dh für dieselben Argumente immer genau dieselbe Ausgabe liefern. Also, hängen Sie nicht von time()oder ab rand(). Monte-Carlo-Methoden sind in Ordnung, solange Sie Ihren eigenen PRNG rollen.
• Nur die Mittelpunkte der Sterne sind von Bedeutung. Machen Sie sich keine Sorgen, wenn Sie versuchen, Überschneidungen oder ähnliches zu vermeiden.

Wertung

• Minimieren Sie die mittlere Entfernung von einem Punkt im Kanton zum nächsten Stern. (Siehe oben.)
• Sie können anhand historischer US-Flaggen zwischen 13 und 50 Sternen bewertet werden. Der genaue Algorithmus zum Gewichten von Ergebnissen in einer einzelnen Rangfolge wird später veröffentlicht.
• Im Falle eines Gleichstands wird der Gewinner anhand der Anzahl der Nettostimmen ermittelt.
• Ich werde wahrscheinlich ein eigenes Programm veröffentlichen, mich jedoch von der Berechtigung für das Häkchen ausschließen.

Javascript - bewege Sterne in Richtung des isoliertesten Punktes

(mit einer Animation des Prozesses)

Der Ansatz ist sehr einfach:

• wähle eine große Anzahl zufälliger Punkte
• finde den nächsten Stern zu jedem
• Wählen Sie den Punkt, für den der nächste Stern am weitesten entfernt ist
• Bewegen Sie den Stern näher an diesen Punkt

Dieser Vorgang wird mehrmals wiederholt, wobei die Bewegung der Sterne allmählich verringert wird. Dies reduziert die maximale Entfernung von einem Punkt zum nächsten Stern und indirekt die mittlere Entfernung von einem Punkt zum nächsten Stern.

Wie in der Frage gefordert, wird hier nicht die eingebaute Zufallsfunktion verwendet, sondern Xorshift .

Ein Großteil des Codes deckt Setup und Animation ab - der Teil, der den Algorithmus anwendet, ist die Funktion adjustStars.

Code

Sie können den laufenden Prozess im folgenden Stapel-Snippet verfolgen.

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) / 4;
  adjustStars(maxStepSize, 8000, 10000);
}

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');
  points = randomPoints(numberOfPoints);
  mostIsolatedPoint = 0;
  distanceToNearestStar = 0;
  for (var i = 0; i < numberOfPoints; i++) {
    point = points[i];
    x = point[0];
    y = point[1];
    star = stars[nearestStar(x, y)];
    d = distance(x, y, star[0], star[1]);
    if (d > distanceToNearestStar) {
      distanceToNearestStar = d;
      mostIsolatedPoint = i;
    }
  }
  point = points[mostIsolatedPoint];
  x = point[0];
  y = point[1];

  starToMove = nearestStar(x, y);

  star = stars[starToMove];
  separationX = x - star[0];
  separationY = y - star[1];
  if (separationX || separationY) {
    hypotenuse = distance(x, y, star[0], star[1]);
    currentStep = Math.min(stepSize, hypotenuse / 2);
    deltaX = currentStep * separationX / hypotenuse;
    deltaY = currentStep * separationY / hypotenuse;
    star[0] += deltaX;
    star[1] += deltaY;
    if (star[0] < 0) star[0] = 0;
    if (star[0] > cantonWidth) star[0] = cantonWidth;
    if (star[1] < 0) star[1] = 0;
    if (star[1] > cantonHeight) star[1] = cantonHeight;

    drawStars();
    updateOutputText();
  }

  if (maxSteps > 0) {
    timeoutId = setTimeout(adjustStars, 10, stepSize * 0.9992, maxSteps - 1, numberOfPoints);
  }
}

function updateOutputText() {
  starText = '';
  for (var i = 0; i < stars.length; i++) {
    starText += stars[i][0] + ', ' + stars[i][1] + '\n';
  }
  $('#coordinateList').text(starText);
}

function randomPoints(n) {
  pointsToReturn = [];
  for (i = 0; i < n; i++) {
    x = xorshift() * cantonWidth;
    y = xorshift() * cantonHeight;
    pointsToReturn.push([x, y]);
  }
  return pointsToReturn;
}

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 nearestStar(x, y) {
  var distances = [];
  for (var i = 0; i < stars.length; i++) {
    star = stars[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];
      nearest = i;
    }
  }
  return nearest;
}

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>

Leistung für 50 Sterne

(Breite = 1,4, Höhe = 1,0)

Mittlere Entfernung auf 0,0655106697162357 geschätzt.

Koordinaten:

0.028377044205135808, 0.2128159150679491
0.10116766857540277, 0.05156676609341312
0.2903566419069437, 0.07216263690037035
0.49154061258041604, 0.004436102736309105
0.6930026352073071, 0.07060477929576484
1.0988644764108417, 0.022979778480838074
1.1735677936511582, 0.18600858289592742
1.3056806950504931, 0.062239869036660435
0.3967626880807638, 0.24483447327177033
0.27004118129346155, 0.40467589936498805
0.4996665039421278, 0.13023282430440133
0.5148978532656602, 0.6161298793146592
0.5907056537744844, 0.2614323599301046
0.8853042432872087, 0.048123917861564044
0.7753680330575412, 0.22938793622044834
1.365432954694329, 0.2355377720528128
0.1985172068244217, 0.23551298706793927
0.4477558465270544, 0.4170264112485973
0.6084424566752479, 0.7764909501169484
0.6099528761580699, 0.4395002434593519
0.9506038166406011, 0.34903243854585914
1.1898331497634231, 0.5756784243472182
1.0933574395540542, 0.46422120794648786
1.1516574254138159, 0.2930213338333888
0.07646053006349718, 0.40665000611360175
0.0634456093015551, 0.5853189455014883
0.3470036636019768, 0.5938838331082922
0.7591083341283029, 0.4005456925638841
0.9745306853981277, 0.184624209972443
1.3552011948311598, 0.549607060691302
1.3334000268566828, 0.7410204535471169
1.2990417572304487, 0.39571229988825735
0.05853941030364222, 0.7734808757471414
0.19396697551982484, 0.5678753467094985
0.7103231124251072, 0.5955041661956884
0.6168410756137566, 0.948561537739087
0.8967624790188228, 0.5368666961690878
0.9751229155529001, 0.8323724819557795
0.9987127931392165, 0.652902038374714
1.3231032600971289, 0.9164326184290812
0.20785221980162555, 0.7566700629874374
0.3987967842137651, 0.7678025218448816
0.44395949605458546, 0.9137553802571048
0.775611700149756, 0.9029717946067138
0.806442448003616, 0.7328147396477286
0.9481952441521928, 0.9872963855418118
1.1528689317425114, 0.9346775634274639
1.1651295140721658, 0.7591158327925681
0.09316709042512515, 0.934205211493484
0.2769325337580081, 0.9341145493466471

Hier ist ein einfaches Beispiel. Es ordnet die Sterne immer in einem rechteckigen Gitter an und optimiert es, indem es die Faktorisierung wählt, bei der die Gitterzellen so nahe wie möglich am Quadrat liegen. Es funktioniert gut, wenn die Anzahl der Sterne einen Divisor nahe der Quadratwurzel hat, und pessimal, wenn die Anzahl der Sterne Primzahl ist.

from __future__ import division
import math
import sys

def divisors(n):
    """
    Return all divisors of n (including n itself) as a set.
    """
    result = {1, n}
    # Use +2 instead of +1 to allow for floating-point error.
    for i in range(2, int(math.sqrt(n)) + 2):
        if n % i == 0:
            result.add(i)
            result.add(n // i)
    return result

def squareness(width, height):
    """
    Given the dimensions of a rectangle, return a value between 0 and 1
    (1 iff width == height) measuring how close it is to being a square.
    """
    if width and height:
        return min(width / height, height / width)
    else:
        return 0.0

def star_grid(num_stars, width, height):
    """
    Return the factors (x, y) of num_stars that optimize the mean
    distance to the nearest star.
    """
    best_squareness = 0.0
    best_dimensions = (None, None)
    for nx in divisors(num_stars):
        ny = num_stars // nx
        sq = squareness(width / nx, height / ny)
        if sq > best_squareness:
            best_squareness = sq
            best_dimensions = (nx, ny)
    return best_dimensions

def star_coords(num_stars, width, height):
    """
    Return a list of (x, y) coordinates for the stars.
    """
    nx, ny = star_grid(num_stars, width, height)
    for ix in range(nx):
        x = (ix + 0.5) * width / nx
        for iy in range(ny):
            y = (iy + 0.5) * height / ny
            yield (x, y)

def _main(argv=sys.argv):
    num_stars = int(argv[1])
    width = float(argv[2])
    height = float(argv[3])
    for coord in star_coords(num_stars, width, height):
        print('%g,%g' % coord)

if __name__ == '__main__':
    _main()

Leistung für 50 Sterne

(Breite = 1,4, Höhe = 1,0)

Ein 10 × 5 Rechteck.

0.07,0.1
0.07,0.3
0.07,0.5
0.07,0.7
0.07,0.9
0.21,0.1
0.21,0.3
0.21,0.5
0.21,0.7
0.21,0.9
0.35,0.1
0.35,0.3
0.35,0.5
0.35,0.7
0.35,0.9
0.49,0.1
0.49,0.3
0.49,0.5
0.49,0.7
0.49,0.9
0.63,0.1
0.63,0.3
0.63,0.5
0.63,0.7
0.63,0.9
0.77,0.1
0.77,0.3
0.77,0.5
0.77,0.7
0.77,0.9
0.91,0.1
0.91,0.3
0.91,0.5
0.91,0.7
0.91,0.9
1.05,0.1
1.05,0.3
1.05,0.5
1.05,0.7
1.05,0.9
1.19,0.1
1.19,0.3
1.19,0.5
1.19,0.7
1.19,0.9
1.33,0.1
1.33,0.3
1.33,0.5
1.33,0.7
1.33,0.9

Javascript - bewege einen Stern nach dem Zufallsprinzip, wenn sich die mittlere Entfernung verringert

(mit einer Animation des Prozesses)

Dies ist keine so belebte Animation wie meine erste Antwort. Lange Zeiträume ohne Bewegung, da mögliche Umlagerungen getestet und zurückgewiesen werden. Das Endergebnis weist jedoch einen geringeren mittleren Abstand auf, sodass diese Methode eine Verbesserung darstellt.

Der Ansatz ist immer noch sehr einfach:

• Wähle einen Stern nach dem Zufallsprinzip
• Bewegen Sie es eine zufällige Strecke in eine zufällige Richtung
• Wenn sich der mittlere Abstand verringert, behalten Sie die neue Position bei

Dieser Vorgang wird mehrmals wiederholt, wobei die Bewegung der Sterne allmählich verringert wird. Die zufällige Auswahl der zu bewegenden Distanz ist auf kleinere Distanzen ausgerichtet, sodass der Fortschritt in kleinen Änderungen mit gelegentlich größeren Sprüngen durchsetzt ist. Jeder Schritt dauert länger als bei meiner ersten Antwort, da die Messung der mittleren Distanz ein langsamer Prozess ist, bei dem der gesamte Kanton beprobt werden muss.

Wie in der Frage gefordert, wird hier nicht die eingebaute Zufallsfunktion verwendet, sondern Xorshift .

Ein Großteil des Codes deckt Setup und Animation ab - der Teil, der den Algorithmus anwendet, ist die Funktion adjustStars.

Code

Sie können den laufenden Prozess im folgenden Stapel-Snippet verfolgen.

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>

Leistung für 50 Sterne

(Breite = 1,4, Höhe = 1,0)

Mittlere Entfernung auf 0,06402754713808706 geschätzt.

Koordinaten:

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