El desafío del código estrellado

21

La bandera de los Estados Unidos de América contiene, en su cantón, 50 estrellas, que representan los 50 estados.

Bandera estadounidense de 50 estrellas

En el pasado, cuando había menos estados, por supuesto, había menos estrellas, y se organizaban de manera diferente. Por ejemplo, de 1912 a 1959 (después de la admisión de Nuevo México y Arizona pero antes de Alaska), había 48 estrellas en un arreglo rectangular de 6 × 8.

Bandera estadounidense de 48 estrellas

La bandera de 37 estrellas utilizada desde 1867-1877 (después de la admisión de Nebraska pero antes de Colorado) tenía un patrón de estrellas asimétrico.

Bandera estadounidense de 37 estrellas

En caso de que se agregue un estado número 51 en el futuro, el Instituto de Heráldica del Ejército ya ha desarrollado un diseño preliminar para una nueva bandera.

Bandera estadounidense de 51 estrellas

Pero no hay un algoritmo general para organizar las estrellas, ¡así que hagamos uno!

El reto

Escriba un programa que, para un número determinado de estrellas para colocar en el cantón (parte azul) de una bandera de los Estados Unidos, produzca coordenadas óptimas en las que colocar esas estrellas. El sistema de coordenadas se define con el cantón [ no la bandera como un todo] con 0≤x≤W y 0≤y≤H.

Para el propósito de este desafío, una disposición "óptima" se define como aquella que minimiza la distancia media (euclidiana) entre un punto en el cantón y el centro de la estrella más cercana.

Un algoritmo sencillo (si tal vez subóptimo) para aproximar este valor es:

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)

Su programa tomará tres argumentos de línea de comandos (sin contar el nombre del programa en sí):

  1. El número de estrellas para poner en el cantón.
  2. El ancho del cantón. (Debe aceptar valores de punto flotante).
  3. La altura del cantón. (Debe aceptar valores de punto flotante).

(Si su lenguaje de programación preferido no admite argumentos de línea de comandos, haga algo razonablemente equivalente y documente en su respuesta).

La salida debe consistir en valores X e Y separados por comas, uno a una línea. (El orden de los puntos no importa).

Por ejemplo:

~$ 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

Reglas y notas adicionales

  • Tengo derecho a cerrar las lagunas en las reglas en cualquier momento.
  • La fecha límite para recibir respuestas es el viernes 4 de julio a las 24:00 CDT (UTC-05: 00). Debido a la falta de respuestas, el plazo se ha extendido. TBA
  • Incluye en tu respuesta:
    • El código de su programa
    • Una explicación de cómo funciona.
    • Su salida con los argumentos de la línea de comandos 50 1.4 1.0
  • Su programa debe ejecutarse dentro de un período de tiempo razonable: como máximo 5 minutos en una PC típica. No seré muy estricto con esto, pero descalificaré su programa si lleva horas .
  • Su programa debe ser determinista, es decir, siempre debe dar exactamente la misma salida para los mismos argumentos. Por lo tanto, no dependa de time()o rand(). Los métodos de Monte Carlo están bien siempre y cuando haga su propio PRNG.
  • Solo importan los puntos centrales de las estrellas. No te preocupes por tratar de evitar la superposición o algo así.

Tanteo

  • Minimice la distancia media desde un punto en el cantón hasta la estrella más cercana. (Véase más arriba.)
  • Puede obtener un puntaje basado en cualquier bandera histórica de los EE. UU., Entre 13 y 50 estrellas. El algoritmo exacto para ponderar los puntajes en una sola clasificación se publicará más adelante.
  • En caso de empate, el ganador será elegido por el número de votos a favor netos.
  • Probablemente publicaré un programa propio, pero me excluiré de ser elegible para la marca de verificación.
dan04
fuente
@primo: ¿Cómo te imaginas eso? Mi ejemplo tiene una distancia media a la estrella más cercana de 0.289, mientras que colocar los 5 puntos en el centro tiene un MDNS de 0.561.
dan04
Puedes ignorar mi comentario anterior. Leí mal la distancia media desde cada punto del cantón a la estrella más cercana, como la distancia media desde cada estrella a la estrella más cercana.
primo
3
Siéntase libre de incluir jsfiddle.net/nf2mk2gr como un fragmento de pila en la pregunta para verificar el resultado de las respuestas, si cumple con su aprobación. Muestra la distancia media basada en una cuadrícula N por N, con N aumentando progresivamente cuanto más espere. (Fue escrito específicamente para esta pregunta.)
trichoplax

Respuestas:

4

Javascript: mueve las estrellas hacia el punto más aislado

(con una animación del proceso)

El enfoque es muy simple:

  • elige una gran cantidad de puntos aleatorios
  • encuentra la estrella más cercana a cada
  • elige el punto por el cual la estrella más cercana está más distante
  • mover esa estrella más cerca de ese punto

Este proceso se repite una gran cantidad de veces, disminuyendo gradualmente la cantidad de movimiento de las estrellas. Esto reduce la distancia máxima desde un punto hasta la estrella más cercana, reduciendo indirectamente la distancia media desde un punto hasta la estrella más cercana.

Como lo requiere la pregunta, esto no usa la función aleatoria incorporada, sino que usa xorshift .

Gran parte del código cubre la configuración y la animación: la parte que aplica el algoritmo es la función adjustStars.

Código

Puede ver el proceso en curso en el Fragmento de pila a continuación.

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>

Salida para 50 estrellas

(ancho = 1.4, altura = 1.0)

Distancia media estimada en 0.0655106697162357.

Coordenadas

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
trichoplax
fuente
Después de ejecutar su animación con varios números de estrellas, parece que tiende a colocar estrellas cerca de los bordes de la caja. Sin embargo, sin conocer la verdadera disposición óptima, no puedo decir si esto es un error o una característica.
dan04
@ dan04 ni a mí, aunque tengo una idea de por qué sucede. Las estrellas cerca del borde están demasiado cerca para que haya una probabilidad significativa de que se muevan hacia él (las estrellas se mueven principalmente hacia los puntos más aislados, no hacia los puntos cercanos). Pero aún pueden moverse hacia el borde indirectamente, alternando entre moverse hacia dos puntos distantes cerca del borde, lo que resulta en un camino en zigzag. Sospecho que esto significa que se ofrecen necesario tener estrellas cerca de los bordes, pero estoy deseando ver otro enfoque para ver si que comparte el bug / función ...
Trichoplax
@ dan04 mi segunda respuesta parece mostrar que las estrellas no necesitan estar tan cerca de los bordes como pensaba, y da mejores resultados que mi primera respuesta. Trabajar directamente con la media en lugar de indirectamente a través del máximo resulta ser más efectivo.
trichoplax
3

Aquí hay un ejemplo simple. Siempre organiza las estrellas en una cuadrícula rectangular y la optimiza eligiendo la factorización en la que las celdas de la cuadrícula están lo más cerca posible del cuadrado. Funciona muy bien cuando el número de estrellas tiene un divisor cerca de su raíz cuadrada, y pesimalmente cuando el número de estrellas es primo.

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()

Salida para 50 estrellas

(ancho = 1.4, altura = 1.0)

Un rectángulo de 10 × 5.

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
dan04
fuente
0

Javascript: mueve una estrella al azar si se reduce la distancia media

(con una animación del proceso)

Esto no da una animación tan ocupada como mi primera respuesta, ya que tiene largos períodos sin movimiento ya que las posibles reorganizaciones se prueban y rechazan. Sin embargo, el resultado final tiene una distancia media menor, por lo que este método es una mejora.

El enfoque sigue siendo muy simple:

  • Elige una estrella al azar
  • Muévelo una distancia aleatoria en una dirección aleatoria
  • Si se reduce la distancia media, mantenga la nueva posición

Este proceso se repite una gran cantidad de veces, disminuyendo gradualmente la cantidad de movimiento de las estrellas. La elección aleatoria de la distancia para moverse está sesgada hacia distancias más pequeñas, por lo que el progreso está en pequeñas alteraciones intercaladas con el salto ocasional más grande. Cada paso lleva más tiempo que en mi primera respuesta, ya que medir la distancia media es un proceso lento que requiere muestrear todo el cantón.

Como lo requiere la pregunta, esto no usa la función aleatoria incorporada, sino que usa xorshift .

Gran parte del código cubre la configuración y la animación: la parte que aplica el algoritmo es la función adjustStars.

Código

Puede ver el proceso en curso en el Fragmento de pila a continuación.

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>

Salida para 50 estrellas

(ancho = 1.4, altura = 1.0)

Distancia media estimada en 0.06402754713808706.

Coordenadas

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
trichoplax
fuente