Algorithme de distribution de points 2D

Que diriez-vous:

1. Découvrez la somme des distances de chaque point de chaque point. Donc, le point A a une distance de somme de dist (A, B) + dist (a, c) + dist (a, d) + ...
2. Trier ces distances résumées.
3. Supprimer des points qui ont la moindre somme de distance jusqu'à ce que vous atteigniez le pourcentage souhaité.

   Ceci peut être suffisamment précis, mais sinon, vous pouvez toujours remplacer l'étape 3 avec:

   "Supprimez le point qui a la plus petite somme, et si vous devez supprimer plus de points pour atteindre votre pourcentage souhaité, revenez à l'étape 1."

   Attendez. Maintenant, je me demande. Essayez-vous de trouver les points qui sont les plus étendus d'un ensemble donné de points ... ou d'essayer, d'un tableau donné, de trouver les points qui seraient les plus étendus? C'est totalement différent ... et toujours vraiment dur.

Que diriez-vous de calculer une valeur "densité" pour chaque pixel pour commencer, en fonction de sa proximité de tous les autres pixels. Ensuite, supprimez à plusieurs reprises le pixel le plus "dense" jusqu'à ce que vous soyez inférieur à P% dans la liste.

Vous auriez besoin de calculer le calcul de la distance pour déterminer la densité entre deux points donnés au plus deux fois. La première fois serait lorsque vous construisez la liste d'origine - chaque pixel devra être comparé aux autres pixels. Deuxièmement, vous seriez lorsque vous supprimez un pixel de la liste - vous devez calculer le retiré celui-ci contre celui-ci restant dans la liste. Il s'agit de prendre en compte les valeurs de densité, la modification de chaque pixel est supprimée - par exemple, 2 pixels directement à côté de l'autre auraient une valeur très très élevée, mais une fois que l'une est retirée, le reste peut avoir une valeur très faible.

Quelques pseudocode rapides (notez que dans cet exemple, les zones de densité supérieure ont un nombre faible) xxx

si la mémoire est moins préoccupante que la période de calcul, vous Peut également stocker la distance entre deux points dans un tableau 2D simple. Aussi, au lieu d'une simple distance, il peut être utile de faire le calcul de la distance exponentielle - qui éviterait quelque chose comme avoir deux points presque les uns sur les autres, mais loin de tout le reste et de les faire passer à travers.

Une approche d'inondation d'inondation d'inondation de la mine itérative serait simple à visualiser.

1. Pour chaque cellule, trouvez les deux points les plus proches et enregistrez le produit de ces deux distances.
2. Ces cellules avec les produits les plus élevés sont celles qui sont attachées aux points les plus éloignés.

Vous voulez une distribution de disque de poisson, mais c'est délicat. Faire une recherche transforme beaucoup de papiers académiques sur la façon de le faire efficacement: http: // gens.csail.mit.edu/thouis/jonespoïissonpreprint.pdf

OOH! Qu'en est-il de cela!

(de manière très vague à la main, puisque je ne sais pas si votre matrice est carrée ou quoi que ce soit ... je suppose que c'est.) P>

dire que vous avez Un tableau 1000x1000 que vous souhaitez placer 47 point dans (je choisis 47 de sorte qu'il s'agisse d'un nombre inhabituel qui ne convient pas "bien"). P>

Vous prenez le CEIL (SQRT (47) ) ... cela vous donnera une valeur (7). Nous faisons donc un carré de 7x7, remplissez-le avec 47 pixels (certains sont blancs) et imaginez-la placer cela dans le coin de la matrice. P>

Maintenant, traduisez chacun de ces pixels vers un nouvel emplacement, en fonction de où ils sont dans le petit tableau (7x7) au grand tableau (1000x1000). Une équation simple devrait le faire pour vous ... Pour la coordonnée X, par exemple: P>

xBigArrayIndex = xSmallArrayIndex * 1000 / 7;

Vous pouvez utiliser un algorithme de coque convexe et exclure des points que cet algorithme le calculera et la répétera aussi longtemps que possible dans vos critères P%, ou

Exécution des étapes d'algorithme de coque convexe, vérifiez les points inclus dans la coque et à l'intérieur de celui-ci pour répondre aux critères 100% - P%

Certaines démos de Hull convexe sont ici http://www.cs.unc.edu/~snoeyink/demos/

Et ici vous avez eu une autre information http://softsurfer.com/archive/algorithm_0109/algorithm_0109.htm

Merci à tout le monde pour les réponses!

La meilleure solution semble utiliser "Blocs de construction précieux": des tableaux NXN avec des cellules déjà sélectionnées et couvrant le tableau de pixels avec ceux-ci.

pour Exemple, un tableau 4 x 4 avec une couverture de 12,5% serait la suivante: xxx

avec une couverture 6.3%: xxx

à Obtenez une couverture% en% entre ceux-ci, juste alterner entre ces blocs en fonction d'un décompte de la couverture en% réelle globale jusqu'à présent. Pour couvrir une largeur qui n'est pas un multiple de 4, utilisez quelque 3 x 3 blocs. Pour couvrir une zone plus grande plus efficacement, utilisez simplement des blocs plus importants.

Ceci couvre efficacement l'ensemble de la matrice sans aucun calcul de distance ni arithmétique de point flottant.

La sélection de pixels "la plus répandu" est l'ensemble dont la triangulation Delaunay est constituée de triangles équilatéraux. L'ensemble de points qui conduit à cette triangulation se trouve en divisant le tableau de pixels dans un ensemble de boîtes, où chaque boîte est sqrt (3) plus longue qu'il n'est large. Chaque boîte contribue à 5 pixels à l'ensemble de pixels final (un à chaque coin, plus un nœud central au centre de la boîte). L'astuce consiste à trouver le nombre de lignes et de colonnes de boîtes vous donnera ce rapport 1: SQRT (3). Sans traverser la dérivation, voici comment vous obtenez cela:

std::vector<PixelIndices> PickPixels(int width, int height, float percent)
{
  int total_pixels = width*height;
  int desired_pixel_count = (int)total_pixels*percent;

  // split the region up into "boxes" with 4 corner nodes and a center node.
  // each box is sqrt(3) times taller than it is wide.

  // calculate how many columns of boxes
  float a = 1.155*height/(float)width;
  float b = .577*height/(float)width + 1;
  float c = 1 - desired_pixel_count;
  int num_columns = (int)((-b + sqrt(b*b -4*a*c))/(2*a));

  // Now calculate how many rows
  int num_rows = .577*height*num_columns/(float)width;

  // total number of pixels
  int actual_pixel_count = 2*num_rows*num_columns + num_rows + num_columns + 1;

  std::cout << "  Total pixels: " << total_pixels << std::endl;
  std::cout << "       Percent: " << percent << std::endl;
  std::cout << "Desired pixels: " << desired_pixel_count << std::endl;
  std::cout << " Actual pixels: " << actual_pixel_count << std::endl;
  std::cout << "   Number Rows: " << num_rows << std::endl;
  std::cout << "Number Columns: " << num_columns << std::endl;

  // Pre-allocate space for the pixels
  std::vector<PixelIndices> results;
  results.reserve(actual_pixel_count);

  // Now get the pixels, my integer math is probably wrong here, didn't test
  //  (didn't even finish, ran out of time)
  for (int row = 0; row <= num_rows; row++)
  {
    int row_index = row*height/num_rows;

    // Top of box
    for (int col = 0; col <= num_columns; col++)
    {
      int col_index = col*width/num_columns;
      results.push_back(PixelIndices(row_index, col_index));
    }

    // Middle of box
    if (row != num_columns)
    {
      for (int col = 0; col < num_columns; col++)
      {
         // I'll leave it to you to get this, I gotta go!
      }
    }
  }

  return results;
}

Vous pourriez essayer WANG TILES:

http://fr.wikipedia.org/wiki/wang_tile
(Voir les pages qui y sont liées au papier de Cohen et le papier de KOPF. Je suis un nouvel utilisateur, alors ne pouvez pas publier tous les liens).

Celles-ci attachent à la fois l'idée de carreaux précuiteurs, ainsi que les exigences uniformément distribuées généralement résolues avec des modèles de disque de poisson. Les carreaux Wang peuvent éviter les effets de périodicité qui sont presque sûrement un problème avec une utilisation plus directe des carreaux prébondés.

Très vieux, mais la peine d'être creusée, car les réponses ont manqué une méthode importante et axée sur des solutions optimales, que vous n'êtes pas intéressé. Mais la méthode que je suggère peut ne pas répondre à vos besoins.

Vous pouvez utiliser Quasi séquences aléatoires , conçues pour de tels problèmes. Les plus largement répandus sont séquences SOBOL , pour lesquelles vous pouvez trouver des packages en conserve pour pratiquement n'importe quelle langue. Ils sont flammes rapides: seul l'arithmétique des bits.

Ils produiront probablement des grappes, mais cela peut être évité en sélectionnant la "graine" à utiliser pour les dimensions x et y à l'avance et en vérifiant avec les yeux nus.

Cela dépend de ce que vous voulez faire avec les points: Si "Étalité visuelle" est important, cela peut ne pas être ce que vous voulez. Si vous voulez des points qui "remplissent l'avion" presque uniformément, ils font parfaitement le travail. Ils sont particulièrement utiles à quelque chose en moyenne sur une image rapidement, car il nécessite moins de points avec une génération aléatoire "normale". Expérimentez avec différentes dimensions et voir.

Voir aussi Ce lien pour exemples expériments et images .