Algorithme permettant de couvrir un nombre maximal de points avec un cercle de rayon donné

Question

Imaginons que nous ayons un plan avec certains points dessus. Nous avons également un cercle de rayon donné.

J'ai besoin d'un algorithme qui détermine la position du cercle de manière à ce qu'il couvre le plus grand nombre possible de points. Bien sûr, il existe de nombreuses positions de ce type, et l'algorithme doit donc renvoyer l'une d'entre elles.
La précision n'est pas importante et l'algorithme peut faire de petites erreurs.

Voici un exemple d'image :

Entrée :
  int n (n<=50) - nombre de points ;
  float x[n] et float y[n] - avec les coordonnées X et Y des points ;
  float r - le rayon du cercle.

Sortie :
  float cx et float cy - coordonnées du centre du cercle

La vitesse fulgurante de l'algorithme n'est pas requise, mais il ne doit pas être trop lent (car je connais quelques solutions lentes pour cette situation).

Le code C++ est préférable, mais pas obligatoire.

Answer 1

Modifié pour une meilleure formulation, comme suggéré :

Observations de base :

• Je suppose que le rayon est de un, puisque cela ne change rien.
• pour deux points quelconques, il existe au plus deux cercles unitaires sur lesquels ils se trouvent.
• Étant donné un cercle de solution à votre problème, vous pouvez le déplacer jusqu'à ce qu'il contienne deux points de votre ensemble tout en gardant le même nombre de points de votre ensemble à l'intérieur.

L'algorithme est alors :

• Pour chaque paire de points, si leur distance est < 2, calculez les deux cercles unitaires C1 et C2 qui les traversent.
• Calculer le nombre de points de votre ensemble à l'intérieur de C1 et C2
• Prenez le maximum.

Answer 2

Il s'agit du "problème du recouvrement partiel du disque" dans la littérature - cela devrait vous donner un bon point de départ pour la recherche sur Google. Voici un article qui traite d'une solution possible, mais qui est un peu complexe sur le plan mathématique : Conception d'algorithmes d'approximation pour le problème de la couverture partielle d'un disque

En fait, il s'agit d'un domaine appelé géométrie computationnelle, qui est fascinant mais dans lequel il peut être difficile de se faire la main. Il y a un bon aperçu par deBerg sur les différents algorithmes liés au sujet.

Answer 3

Si vous voulez quelque chose de simple, prenez une position aléatoire (x,y), calculez le nombre de points à l'intérieur du cercle et comparez avec la position précédente. Prenez le maximum. Répétez l'opération autant de fois que vous le souhaitez.

Pourquoi le downvote ? Tu as déjà entendu parler des méthodes de Monte Carlo ? En fait, pour une quantité énorme de points, l'algorithme déterministe peut ne pas finir en un temps raisonnable.

Answer 4

Le problème revient à trouver le mondial optimum d'une fonction f :R x R -> N . L'entrée pour f est le point central du cercle, et la valeur, bien sûr, est le nombre de points inclus dans l'ensemble. Le graphique de la fonction sera discontinu, en forme d'escalier.

Vous pourriez commencer par tester la fonction en chaque point correspondant à un point de l'ensemble, ordonner les points par valeurs décroissantes de f puis intensifier la recherche autour de ces points (par exemple en se déplaçant le long d'une spirale).

Une autre option consiste à envisager tous les points d'intersection des segments reliant n'importe quelle paire de points dans l'ensemble. Votre site optimal point se trouvera à l'une de ces intersections je pense, mais leur nombre est probablement trop important pour être pris en compte.

Vous pouvez également combiner les options 1 et 2, et considérer les intersections des segments générés à partir de points autour des "bons points de réglage".

Quoi qu'il en soit, à moins que le nombre de points de consigne ne soit faible (ce qui vous permet de vérifier toutes les intersections), je ne pense pas qu'il soit possible d'obtenir des résultats satisfaisants. pensez à vous pouvez garantir de trouver l'optimum (juste une bonne solution).

Answer 5

À première vue, je dirais une solution à quatre arbres.

Il existe également une méthode de visualisation de l'information et d'extraction de données appelée K-means, qui permet de regrouper des données données. Elle peut être utilisée avec des fonctionnalités supplémentaires pour répondre à vos besoins.

L'algorithme de base de K-Means est le suivant :

1. Placez K points dans l'espace représenté par les éléments à regrouper. qui sont regroupés - Ces points représentent les centroïdes du groupe initial.
2. Affectez chaque élément de données au groupe dont le centroïde est le plus proche. centroïde
3. Lorsque tous les éléments ont été assignés, recalculez les positions des K centroïdes en calculant la position moyenne de vos points
4. Répétez les étapes 2 et 3 jusqu'à ce que les centroïdes ne bougent plus, ou très peu.

La fonctionnalité ajoutée serait alors :

5. Calculez le nombre de points dans votre cercle positionnés aux centroïdes K
6. Choisissez celui qui vous convient le mieux ;)

Sources :
Algorithme K-means - Université de Linköping
Quadtree - fr.wikipedia.org/wiki/Quadtree

Une recherche rapide sur wikipedia et vous trouvez le code source : fr.wikipedia.org/wiki/K-means_clustering