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

C'est le "problème de couverture partielle du disque" dans la littérature -- qui devrait vous donner un bon endroit pour commencer à googler. Voici un papier couvrant une solution possible, mais il est un peu intense mathématiquement: http://www.utdallas.edu / ~edsha / papers/bin / ISPAN04_cover.

en fait, cela tombe dans le domaine appelé géométrie computationnelle, qui est fascinant, mais peut être difficile à obtenir un tenure dans. Il ya un bon aperçu par deBerg sur divers les algorithmes liés à l'objet.

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

Pourquoi diable downvote? Vous connaissez les méthodes Monte Carlo? En fait pour une énorme quantité de points, algorithme déterministe peut ne pas finir dans un délai raisonnable.

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

Vous pouvez commencer par tester la fonction dans chaque point correspondant à un point dans l'ensemble, ordonnez les points en diminuant les valeurs de f, ensuite intensifier la recherche autour de ces points (par exemple déplacer le long d'une spirale).

une Autre option est de considérer points d'intersection de segments reliant toute paire de points dans l'ensemble. Votre optimal point sera à l'une de ces intersections je pense, mais leur nombre est probablement trop grand pour considérer.

Vous pouvez également hybrider les options 1 et 2, et considérer les intersections des segments générés à partir de points autour de 'good set' point.'

de toute façon, sauf si le nombre de points de consigne est faible( vous permettant de vérifier toutes les intersections), Je ne penser vous pouvez vous garantissons de trouver l'optimum (juste une bonne solution).

a première vue, je dirais une solution d'arbre quadruple.

il y a aussi une méthode de visualisation de l'information/extraction de données appelée k-means qui fait des amas de DONNÉES DONNÉES DONNÉES. Il peut être utilisé avec des fonctionnalités ajoutées à la fin pour s'adapter à votre but.

l'algorithme de base pour K-Means est:

1. placer K points dans l'espace représenté par les éléments qui sont regroupés Ces points représentent groupe initial centroïdes
2. attribuer chaque élément de données au groupe le plus proche centroïde
3. lorsque tous les éléments ont été attribués, recalculer le positions des centroïdes K en calculant la position moyenne de vos points
4. répéter les étapes 2 et 3 jusqu'à ce que les centroïdes ne bougent plus, ou bougent très peu

la fonctionnalité ajoutée serait alors:

5. calculez le nombre de points dans votre cercle positionné au K centroïdes
6. Choisir celui qui vous convient le mieux ;)

Sources:

K-signifie algorithme -De L'Université De Linköping

Quadtree -en.wikipedia.org/wiki/Quadtree

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

voici deux idées: un algorithme d'approximation O(n) et un algorithme d'approximation O(N^2 log n):

rapprochement rapide

utiliser un hachage sensible à la localité. Fondamentalement, hachez chaque point à un seau de hachage qui contient tous les points à proximité. Les seaux sont configurés de façon à ce que les collisions ne se produisent qu'entre des points voisins - contrairement aux tables de hachage nommées de la même façon, les collisions sont utiles ici. Compter le nombre de collisions dans un seau, et puis utiliser le centre de seau comme le centre de votre cercle.

j'avoue que c'est une rapide explication d'un concept qui n'est pas super évident la première fois que vous entendez parler d'elle. Une analogie serait de demander à un groupe de personnes ce qu'est leur code postal, et d'utiliser le code postal le plus commun pour déterminer le cercle le plus populeux. Il n'est pas parfait, mais un bon vite heuristique.

c'est essentiellement du temps linéaire en termes de nombre de points, et vous pouvez mettre à jour vos données la mouche pour obtenir progressivement de nouvelles réponses en temps constant par point (constant par rapport à n = nombre de points).

en savoir Plus sur hashes sensibles à la localisation en général ou sur ma préférée est la version qui serait à l'œuvre dans ce cas.

approche déterministe de la force supérieure à la brute

l'idée est: pour chaque point, placer le bord d'un cercle sur ce point et balayer le cercle autour pour voir lequel direction contient le plus de points. Faites ceci pour tous les points et nous trouvons le max global.

le balayage autour d'un point p peut être fait en n log n Temps en: (a) trouvant l'intervalle d'angle par un autre point q tel que lorsque nous plaçons le cercle à l'angle theta, alors il contient q; et (B) en triant les intervalles de sorte que nous pouvons marcher/balayer autour de p en temps linéaire.

il faut donc du temps O(N log n) pour trouver le meilleur cercle en touchant un point fixe p, puis multiplier ce temps par O (n) pour effectuer la vérification pour tous les points. Le temps total est O (N^2 log n).

S'il est vrai que la précision n'est pas importante et l'algorithme peut faire de petites erreurs alors je pense que le suivant.

Let f(x,y) est une fonction qui a un maximum au point (0,0) et n'est significative qu'aux points à l'intérieur du cercle de rayon R. par exemple, f(x,y) = e^{(x^2 + y^2)/ (2 * R^2)}.

Let (x_i,y_i) sont des points et E_i(x,y) = f(x - x_i, y - y_i).

Votre problème est de trouver le maximum de \sum_i E_i(x,y).

vous pouvez utiliser une descente en pente à partir de chaque point.

puis-je Suggérer une carte de densité? Trouvez les limites min et max pour les x et Y. Divisez la gamme des limites x et y en bacs ayant des largeurs égales au diamètre de votre cercle. Compter le nombre de points dans chaque bac pour les x et y séparément. Maintenant, trouvez l'intersection sur votre carte de densité entre le bin x le mieux classé et le bin Y.

il s'agit D'un algorithme très rapide pour généraliser rapidement de grands ensembles de données, mais il n'est pas toujours précis, pour améliorer précision vous pouvez découper les bacs en morceaux de plus en plus petits ou déplacer les positions des bacs vers la gauche ou la droite n fois et utiliser un système de vote pour sélectionner la réponse qui se produit le plus souvent entre les essais.

vous pouvez pixeliser toute la zone, puis aller à chaque point et augmenter la valeur de tous les pixels dans le cercle du rayon autour de ce point. Les pixels avec la somme la plus élevée sont de bons candidats.

bien sûr, vous pourriez perdre de bonnes zones ou "halluciner" de bonnes zones en raison d'erreurs d'arrondissement. Peut-être que vous pourriez essayer de faire une pixellisation rugueuse d'abord, puis raffiner les zones prometteuses.

c'est le fameux algorithme du point K le plus proche. Décrit ici:http://www.cs.ucsb.edu / ~suri / cs235 / ClosestPair.